Java 中的快速排序（中间枢轴）不起作用

Question

我最近开始学习快速排序。教科书展示了一个递归快速排序的例子。但是，即使照搬了课本（数组名和方法名不妥之处还请见谅），结果还是不太好

算法似乎无法到达数组的第二个分区。

下面是教科书中的例子：

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

请让我知道哪一部分是错误的，我该如何解决。谢谢。

Answer 1

罪魁祸首是：

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("");

Java 中的快速排序（中间枢轴）不起作用

Quicksort (middle pivot) in Java not working

java

quicksort