我最近开始学习快速排序。教科书展示了递归快速排序的示例。然而,即使从课本上复制了所有内容(如果数组和方法的名称不合适,请原谅我),结果也不是很好。
算法似乎无法到达数组的第二个分区。
这是教科书上的例子:
1 class Quicksort {
2 static void qsort(int items[]) {
3 qs(items, 0, items.length-1);
4 }
5 }
6
7
8 private static void qs(int items[], int left, int right) {
9 int i, j;
10 int x, y;
11
12 i = left; j = right;
13 x = items[(left+right)/2];
14 System.out.println("Comparand is " + x);
15
16 do {
17 while((items[i] < x) && (i < right)) i++;
18 System.out.print(items[i]);
19 while((x < items[j]) && (j > left)) j--;
20 System.out.println(" and " + items[j]);
21
22 if(i <= j) {
23 y = items[i];
24 items[i] = items[j];
25 items[j] = y;
26 i++; j--;
27 }
28 } while (i <= j);
29
30 for(i = 0; i < items.length; i++)
31 System.out.print(items[i]);
32 System.out.println("");
33
34 if(left < j) qs(items, left, j);
35 if(i < right) qs(items, i, right);
36 }
37 }
...这是结果:
Original array: 3164597
Comparand is 4
6 and 4
3146597
Comparand is 1
3 and 1
1346597
Sorted array: 1346597
请让我知道哪一部分是错误的以及我应该如何修复它。谢谢你。
罪魁祸首是:
for(i = 0; i < items.length; i++) // line 30, i == 0
System.out.print(items[i]); // line 31
System.out.println(""); // line 32, i == items.length
您正在使用局部变量
i
来循环遍历数组。但这样做会覆盖上面分区循环设置的 i
的值。
使用另一个变量循环遍历数组:
for (int t = 0; t < items.length; t++)
System.out.print(items[t]);
System.out.println("");
或者更好的是,使用 foreach 循环来避免此类错误:
for (item : items)
System.out.print(item);
System.out.println("");