- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我已经编写了这段代码,但它会在控制台中打印这些堆栈跟踪,请帮助我,谢谢! (同样“p”和“q”分别是我们数组的第一个和最后一个索引)
public class JavaQuickSort {
public static void QuickSort(int A[], int p, int q) {
int i, last = 0;
Random rand = new Random();
if (q < 1) {
return;
}
**swap(A, p, rand.nextInt() % (q+1));**
for (i = p + 1; i <= q; i++) {
if (A[i] < A[p]) {
swap(A, ++last, i);
}
}
swap(A, p, last);
QuickSort(A, p, last - 1);
QuickSort(A, last + 1, q);
}
private static void swap(int[] A, int i, int j) {
int temp;
temp = A[i];
**A[i] = A[j];**
A[j] = temp;
}
public static void main(String[] args){
int[] A = {2,5,7,3,9,0,1,6,8};
**QuickSort(A, 0,8 );**
System.out.println(Arrays.toString(A));
}
}
run:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -3
at JavaQuickSort.swap(JavaQuickSort.java:38)
at JavaQuickSort.QuickSort(JavaQuickSort.java:22)
at JavaQuickSort.main(JavaQuickSort.java:45)
Java Result: 1
BUILD SUCCESSFUL (total time: 2 seconds)
public class JavaQuickSort {
public static void QuickSort(int arr[],int lo,int hi) {
int n = arr.length;
if(n<=1)
return;
**int r = partition(arr);**
**QuickSort(arr,lo , r-1);**
QuickSort(arr, r+1, hi);
}
private static void swap(int[] A, int i, int j) {
int temp;
temp = A[i];
**A[i] = A[j];**
A[j] = temp;
}
public static int partition(int arr[]){
int i, last = 0;
Random rand = new Random();
int n = arr.length;
if (n <= 1)
return arr[0];
**swap(arr, 0, rand.nextInt(n));**
for (i =1; i <n; i++) {
if (arr[i] < arr[0]) {
swap(arr, ++last, i);
}
}
swap(arr, 0, last);
return last;
}
public static void main(String[] args){
int[] A = {2,5,7,3,9,0,1,6,8};
**QuickSort(A, 0,8 );**
System.out.println(Arrays.toString(A));
}
}
run:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at JavaQuickSort.swap(JavaQuickSort.java:27)
at JavaQuickSort.partition(JavaQuickSort.java:39)
at JavaQuickSort.QuickSort(JavaQuickSort.java:19)
at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
at JavaQuickSort.main(JavaQuickSort.java:52)
Java Result: 1
BUILD SUCCESSFUL (total time: 2 seconds)
public class JavaQuickSort {
public static void QuickSort(int arr[], int lo, int hi) {
if (hi > lo) {
Random rand = new Random();
int pivotIndex = lo + rand.nextInt(hi-lo+1);
int pivotnewIndex = partition(arr, lo, hi,pivotIndex);
QuickSort(arr, lo, pivotnewIndex - 1);
QuickSort(arr, pivotnewIndex + 1, hi);
}
}
private static void swap(int[] A, int i, int j) {
int temp;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
public static int partition(int arr[],int lo,int hi,int pivotIndex)
{
int pivotValue = arr[pivotIndex];
swap(arr, hi, pivotIndex);
int storeIndex = lo;
for(int i = lo;i<hi;i++){
if (arr[i]<=pivotValue)
swap(arr, storeIndex, i);
storeIndex = storeIndex ++;
}
swap(arr, storeIndex, hi);
return storeIndex;
}
public static void main(String[] args) {
int[] A = {2, 5, 7, 3, 9, 0, 1, 6, 8};
QuickSort(A, 0, 8);
System.out.println(Arrays.toString(A));
}
}
run:
[2, 9, 3, 8, 0, 6, 7, 1, 5]
BUILD SUCCESSFUL (total time: 2 seconds)
最佳答案
您的代码的一些问题是:
Random
例如一次使用。只需创建一次,然后将其存储在 static
中字段,然后使用它为您的应用程序生成许多随机数。 p
之间和 q
包括的。 Random.nextInt(int n)
重载以生成给定范围内的随机数 lo
和 hi
而不是 p
和 q
, 和 int[] arr
而不是 int A[]
.length
得到一个数组的长度成员(member) function partition(array, left, right, pivotIndex)
pivotValue := array[pivotIndex]
swap array[pivotIndex] and array[right] // Move pivot to end
storeIndex := left
for i from left to right - 1 // left ≤ i < right
if array[i] ≤ pivotValue
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right] // Move pivot to its final place
return storeIndex
procedure quicksort(array, left, right)
if right > left
select a pivot index //(e.g. pivotIndex := left+(right-left)/2)
pivotNewIndex := partition(array, left, right, pivotIndex)
quicksort(array, left, pivotNewIndex - 1)
quicksort(array, pivotNewIndex + 1, right)
left
之间的子数组的中间元素和
right
对于枢轴索引。由于您想要随机快速排序,因此您希望在
left
之间选择一个随机索引。和
right
包括在内,所以公式需要修改如下:
pivotIndex := left + (random number between 0 and right-left inclusive)
left = 5
和
right = 7
,那么你想要
pivotIndex
成为
5 + x
哪里
x
是
0
之间的随机数和
7-5=2
包括的。
Random.nextInt(n)
有一个唯一的上限,将其转换为 Java 将类似于:
int pivotIndex = lo + rand.nextInt(hi - lo + 1);
// HORRIBLE FORMATTING! Don't do this!
if (arr[i]<=pivotValue)
swap(arr, storeIndex, i);
storeIndex = storeIndex ++;
if
的一部分。正文,但是上面的代码,当正确缩进并添加大括号时,实际上是这样的:
// PROPER FORMATTING! Reveals bug instantly!
if (arr[i]<=pivotValue) {
swap(arr, storeIndex, i);
}
storeIndex = storeIndex ++;
storeIndex
增加到
if
body 是这样的:
// Corrected according to pseudocode!
if (arr[i]<=pivotValue) {
swap(arr, storeIndex, i);
storeIndex = storeIndex ++;
}
// Nice and clear!
if (arr[i]<=pivotValue) {
swap(arr, storeIndex++, i);
}
if
声明,即使它们不是绝对必要的.length
数组,我的意思是,而不是这个:
int[] A = {2, 5, 7, 3, 9, 0, 1, 6, 8};
QuickSort(A, 0, 8); // BAD! Don't hardcode array length!
int[] arr = {2, 5, 7, 3, 9, 0, 1, 6, 8};
QuickSort(arr, 0, arr.length - 1); // GOOD!
关于java - 关于快速排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2995535/
我正在编写一个具有以下签名的 Java 方法。 void Logger(Method method, Object[] args); 如果一个方法(例如 ABC() )调用此方法 Logger,它应该
我是 Java 新手。 我的问题是我的 Java 程序找不到我试图用作的图像文件一个 JButton。 (目前这段代码什么也没做,因为我只是得到了想要的外观第一的)。这是我的主课 代码: packag
好的,今天我在接受采访,我已经编写 Java 代码多年了。采访中说“Java 垃圾收集是一个棘手的问题,我有几个 friend 一直在努力弄清楚。你在这方面做得怎么样?”。她是想骗我吗?还是我的一生都
我的 friend 给了我一个谜语让我解开。它是这样的: There are 100 people. Each one of them, in his turn, does the following
如果我将使用 Java 5 代码的应用程序编译成字节码,生成的 .class 文件是否能够在 Java 1.4 下运行? 如果后者可以工作并且我正在尝试在我的 Java 1.4 应用程序中使用 Jav
有关于why Java doesn't support unsigned types的问题以及一些关于处理无符号类型的问题。我做了一些搜索,似乎 Scala 也不支持无符号数据类型。限制是Java和S
我只是想知道在一个 java 版本中生成的字节码是否可以在其他 java 版本上运行 最佳答案 通常,字节码无需修改即可在 较新 版本的 Java 上运行。它不会在旧版本上运行,除非您使用特殊参数 (
我有一个关于在命令提示符下执行 java 程序的基本问题。 在某些机器上我们需要指定 -cp 。 (类路径)同时执行java程序 (test为java文件名与.class文件存在于同一目录下) jav
我已经阅读 StackOverflow 有一段时间了,现在我才鼓起勇气提出问题。我今年 20 岁,目前在我的家乡(罗马尼亚克卢日-纳波卡)就读 IT 大学。足以介绍:D。 基本上,我有一家提供簿记应用
我有 public JSONObject parseXML(String xml) { JSONObject jsonObject = XML.toJSONObject(xml); r
我已经在 Java 中实现了带有动态类型的简单解释语言。不幸的是我遇到了以下问题。测试时如下代码: def main() { def ks = Map[[1, 2]].keySet()
一直提示输入 1 到 10 的数字 - 结果应将 st、rd、th 和 nd 添加到数字中。编写一个程序,提示用户输入 1 到 10 之间的任意整数,然后以序数形式显示该整数并附加后缀。 public
我有这个 DownloadFile.java 并按预期下载该文件: import java.io.*; import java.net.URL; public class DownloadFile {
我想在 GUI 上添加延迟。我放置了 2 个 for 循环,然后重新绘制了一个标签,但这 2 个 for 循环一个接一个地执行,并且标签被重新绘制到最后一个。 我能做什么? for(int i=0;
我正在对对象 Student 的列表项进行一些测试,但是我更喜欢在 java 类对象中创建硬编码列表,然后从那里提取数据,而不是连接到数据库并在结果集中选择记录。然而,自从我这样做以来已经很长时间了,
我知道对象创建分为三个部分: 声明 实例化 初始化 classA{} classB extends classA{} classA obj = new classB(1,1); 实例化 它必须使用
我有兴趣使用 GPRS 构建车辆跟踪系统。但是,我有一些问题要问以前做过此操作的人: GPRS 是最好的技术吗?人们意识到任何问题吗? 我计划使用 Java/Java EE - 有更好的技术吗? 如果
我可以通过递归方法反转数组,例如:数组={1,2,3,4,5} 数组结果={5,4,3,2,1}但我的结果是相同的数组,我不知道为什么,请帮助我。 public class Recursion { p
有这样的标准方式吗? 包括 Java源代码-测试代码- Ant 或 Maven联合单元持续集成(可能是巡航控制)ClearCase 版本控制工具部署到应用服务器 最后我希望有一个自动构建和集成环境。
我什至不知道这是否可能,我非常怀疑它是否可能,但如果可以,您能告诉我怎么做吗?我只是想知道如何从打印机打印一些文本。 有什么想法吗? 最佳答案 这里有更简单的事情。 import javax.swin
我是一名优秀的程序员,十分优秀!