为什么我在 Java 中实现的快速排序不起作用？

Question

代码如下：

public class QuickSort {

    public static void sort(int[] a) {
        sort(a, 0, a.length-1);
    }

    private static void sort(int[] a, int lo, int hi) {
        if(hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }

    private static int partition(int[] a, int lo, int hi) {
        int v = a[0];
        int i = lo, j = hi+1;
        while(true) {
            while(a[++i] < v) {
                if(i == hi) {
                    break;
                }
            }
            while(a[--j] > v) {
                if(j == lo) {
                    break;
                }
            }
            if(i >= j) {
                break;
            } else {
                exch(a, i, j);
            }
        }
        exch(a, lo, j);    // <- exchange the value of a[lo] and a[j]
        return j;
    }
}

我的代码有什么问题？我知道这是一个非常简单的算法，但就是无法找出问题所在。

请提前帮帮我，谢谢。

Answer 1

我猜你的 partition 函数有错误。您选择的顶点（轴）v 每次都应设置为 a[lo] 而不是 a[0]。

然后设置i = lo + 1和j = hi

为什么我在 Java 中实现的快速排序不起作用？

Why doesn't my quicksort implemented in Java work?

java

sorting

algorithm

quicksort