java - 快速排序Java中的无限循环

Question

我尝试实现一种快速排序算法，但是当我运行我的代码时，它给了我一个无限循环，我不明白，我在代码中的分区方法哪里出错了:

public static int partition(int[] a, int p, int r)
{
    int x = a[p];
    int i = p;
    int j = r + 1;
    while(true)
    {
        while(a[i] < x) 
        {
            i++;
            if (i == r) break;
        }
        while(x > a[j]) 
        {
            j--;
            if (j == p) break;
        }
        if (i >= j) break;

        int tmp = a[i];
        a[i] = a[j];
        tmp = a[i];
    }

    int exch = a[p];
    a[p] = a[j];
    exch = a[p];

    return j;
}

此代码的输入数据:

private static int[] array;
private static Scanner sc = new Scanner(System.in);
public static void main(String[] args){
    int n, m;
    n = sc.nextInt();
    array = new int[n+1];
    int i,j;
    for (i = 0; i != array.length-1; i++)
        array[i] = sc.nextInt();


    for (j = 0; j !=array.length-1; i++)
        System.out.print(array[j]);
    quickSort(array,0,array.length);

}

Answer 1

尝试

a[j] = exch;

代替

exch = a[p];

和相同的错误——感谢@Namer 和@Zhuinden——在你的代码中:

int tmp = a[i];
a[i] = a[j];
tmp = a[i];

感谢@DeepanshuBedi，Quicksort in Java - Tutorial有算法的描述。它有

i++;
j--;

在循环交换之后。

另外，函数应该是递归的:

if (low < j)
  quicksort(low, j);
if (i < high)
  quicksort(i, high); 

而不是你的第二次交换。

我建议您从该页面复制代码——您的代码在我看来不是快速排序。