6

我观看了快速排序算法的精彩可视化：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 和 right 的值如下：

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。由于下面的答案中解释的原因，这当然是错误的。

4

4 回答 4

4

我不得不摆脱分区，因为你需要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]
于 2013-02-23T21:47:23.170 回答
2

很明显，你已经得到了你接受的答案。但是我会提到，您的分区逻辑可以更容易地实现，只有一个 for（或 while）循环，也没有嵌套循环：

int partition(final int[] a, final int left, final int right) {
        // set the last element as pivot
        final int pivot = a[right];
        int i = left - 1, j = left;
        for (; j < right; j++) 
            if (a[j] < pivot) {
                i++;
                swap(a, i, j);
            }       
        // swap a[i+1] and pivot
        swap(a, i + 1, right);
        return i + 1;
    }

并在您的快速排序方法中：

if (left < index)
  quickSort(a, left, index-1);
if (index < right)
  quickSort(a, index + 1, right);

希望能帮助到你

于 2013-02-23T22:07:15.587 回答
2 
int pivot = a[0];

应该

int pivot = a[left];

那，随着更改swap (a, i, j);为swap (a, i--, j++);，一切似乎都工作正常。

为什么上述变化：

枢轴应该是范围中的第一个元素，而不是第一个元素。

也不应该在这个中间，就像这里：

int pivot = a[(left + right) / 2];

您希望枢轴成为哪个元素并不重要，最简单的方法是始终将所选元素与第一个元素交换，然后照常继续。可能还有其他的做事方式，但这些方式可能会更复杂。

所以你可以说：

swap(left, (left + right) / 2);
int pivot = a[left];

这与上述非常相似（不完全相同），只是更容易处理。

于 2013-02-23T22:16:03.770 回答
1

我认为该partition方法应该返回j而不是i.

您的代码中的另一个问题是您的停止条件：

而不是两个单独的条件，我将其更改为单个条件：

if (left < right)  {

  do partition & recursive calls

}

完整代码：

public void quickSort(int[] a, int left, int right) {
    if (left < right) {
      int index = partition(a, left, right);
      quickSort(a, left, index);
      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[(left+right)/2];

    while (i < j) {

        i++;

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

        j--;

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

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

private void swap (int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
于 2013-02-23T21:36:13.290 回答