java - 实现快速排序

Question

我正在尝试实现快速排序，但没有得到正确的结果。这是我的代码:

public static void quickSort(Comparable[] a, int start, int stop) {
    if (start < stop) {
        int pivot = partition(a, start ,stop);
        System.out.print("Pivot: "+a[pivot]+" Array: ");
        printArray(a);
        quickSort(a,start,pivot-1);
        quickSort(a,pivot+1, stop);
    }       
}

public static int partition(Comparable[] a, int start, int stop) {
    Comparable pivot = a[stop];
    int i = start;
    int j = stop-1;


     while (i < j) {
            while( (isLess(a[i], pivot)|| isEqual(a[i], pivot)))
                i++;
            while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))
                j--;
            if(i < j)
                swap(a, i,j);
        } 

    swap(a,i, stop);

    return i;

}

对于输入:{51,17,82,10,97,6,23,45,6,73}，我得到的结果:6 6 10 17 23 45 51 73 97 82对于输入:{12,9,4,99,120,1,3,10}，我收到索引越界错误。希望能在我出错的地方提供一些帮助。

Answer 1

你的两个问题是不相关的。

{51,17,82,10,97,6,23,45,6,73} 的问题是 — 当 stop == start + 1 时会发生什么？然后i == start == stop - 1 == j ，所以你永远不会输入 while -loop，让你无条件swap(a, i, stop) — 即使a[i] 已经小于a[stop] .

{12,9,4,99,120,1,3,10} 的问题看来您没有阅读堆栈跟踪。 ;-) 假设您有一个不错的 Java 编译器和 JVM，它应该为您提供准确的行号和有问题的索引，因此您会发现问题出在这一行:

            while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))

一次j到达-1 。 (如果 pivot 是感兴趣范围内的最小值，就会发生这种情况。)您只需为此添加一个检查:

            while(j > start && (isGreater(a[j], pivot)|| isEqual(a[j], pivot)))

(就此而言，对于 i 的相应情况:

            while(i < stop && (isLess(a[i], pivot)|| isEqual(a[i], pivot)))

)

。 。 。并且您需要学习如何调试代码。 :-)