Quicksort算法无法正确分配枢轴

Question

我观看了这种快速排序算法的精彩可视化:http://www.youtube.com/watch？v = Z5nSXTnD1I4

我觉得我真的理解快速排序背后的原则,并且在一些在线指南的帮助下,着手创建我自己的快速排序.
这就是我想出的:

public void quickSort(int[] a, int left, int right) {

    int index = partition(a, left, right);
    if (left < index - 1)
      quickSort(a, left, index);
    if (index < right)
      quickSort(a, index + 1, right);
}

private int partition (int[] a, int left, int right) {
    int i = left - 1;
    int j = right + 1;
    int pivot = a[0];

    while (i < j) {

        i++;

        while (a[i] < pivot)
            i++;

        j--;

        while (a[j] > pivot)
            j--;

        if (i < j)
            swap (a, i, j);
    }
return i;
}   

private void swap (int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

左侧和右侧的值如下:

left = 0
right = array size - 1

不幸的是输出不正确.问题似乎在于我对枢轴的处理.在我观察的可视化中,教师物理地移除了枢轴并使指针指向任何东西.他继续学习教程,当他到达i和j(我称之为左右)两者都指向同一个空位时,他插入了枢轴并继续前进.

由于我在物理上保持枢轴,我发现很难对其进行适当的排序.

在这段代码中,我正在使用输入:

4 8 1 6 3 7 2 5

我得到输出:

1 3 2 6 8 7 4 5

一旦在算法的最开始对"4"值(即枢轴)进行排序,我就不会使用它,这会抛弃一切.另外,我认为quickSort方法有问题.

有人可以给我一些指示吗？谢谢.

编辑:此处的两个编辑已被删除,因为它们包含不必要和不正确的信息.其中一个将枢轴改为:(左+右)/ 2.由于下面答案中解释的原因,这当然是错误的.

Answer 1

我必须摆脱分区，因为你需要i和j。它应该看起来像这样：

public void quickSort(int[] a, int left, int right) {

    int i = left; // Was -1 
    int j = right; // Was +1
    int pivot = a[left + (right - left) / 2]; // Pivot is the value of the middle index, not the index itself
    while (i <= j) { // Changed terminating condition
        //   i++;  Not needed
        while (a[i] < pivot) { 
            i++;
        }
        //    j++; Not needed
        while (a[j] > pivot) {
            j--;
        }
        if (i <= j) {  // Changed terminating condition
            swap(a, i, j);
            i++;  // You need to progress the indexes after the swap
            j--;
        }
    }

    System.out.println(Arrays.toString(a));
    if (left < j) {  // Changed condition
        quickSort(a, left, j);
    }
    if (i < right) { 
        quickSort(a, i, right); // was i + 1
    }
}

输出：

[4, 5, 1, 2, 3, 7, 6, 8]
[1, 5, 4, 2, 3, 7, 6, 8]
[1, 3, 2, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]