-1

我正在做一些练习题来刷新我的旧算法课程，并且我正在尝试实现快速排序。是的，我知道我们应该在生产代码中使用std::sort，但这是出于教育目的:)

我有下面的代码。它在数组中的所有元素都是唯一的时候有效，但在有重复元素时无效。怎么会？我在哪里动摇了？

void quicksort(int arr[], int left, int right)
{
    // base case:
    if (left >= right)
        return;

    // alternative case:
    int pivot_index = (left + right)/2;
    int pivot = arr[pivot_index];

    int i = left, j = right;
    int tmp;

    while (i < j)
    {
        // scan from left until elem > pivot or left == right, 
        while (arr[i] < pivot)
            ++i;

        // scan from right until elem < pivot or right == left.
        while (arr[j] > pivot)
            --j;

        if (i < j)
        {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            ++i;
            --j;
        }
    }
    // recurse on left and right.
    if (i > left)
        quicksort(arr, left, i);
    if (i < right)
        quicksort(arr, i + 1, right);
}

void main()
{
    const int arr_size = 7;
    int arr[arr_size] = {1,2,4,3,9,5,2};
    quicksort(arr, 0, arr_size - 1);

    for (int i = 0; i < arr_size; ++i)
    {
        std::cout << arr[i] << ", ";
    }
}
4

2 回答 2

4 
if (i > left)
    quicksort(arr, left, i);
if (i < right)
    quicksort(arr, i + 1, right);

假设您有一个包含两个相等元素的数组。然后i == right，你一次又一次地对完全相同的数组进行排序，一次又一次......

当您的数组包含多个元素时，这很可能在某个时候发生。

重复元素的另一个故障点示例如下

int arr[5] = { 4, 8, 4, 5, 6 };

枢轴是索引 2 处的 4，在第一次扫描i == 0和之后j == 2，两个 4 被交换，i递增，j递减，所以现在i == j == 1，循环停止。

然后递归调用排序{ 4, 8 }resp { 4, 5, 6}，结果排序不正确。

您可以通过分别替换至少一个扫描条件来避免该问题arr[i] <= pivot。arr[j] >= pivot，但是您需要防止超出数组（当枢轴是最大或最小元素时），最好在其中包含条件i < j。

如果您响应。交换时减少索引，

if (i < j)
{
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    ++i;
    --j;
}

你总是有最后一次交换可能发生在某种情况下的问题

... x y z ...
    ^   ^
    i   j

导致i == j指向y，并且您没有关于如何y与枢轴进行比较的信息。

因此，您需要检查y和处理不同的可能性。

但是如果没有重复的元素，您的实现也是不正确的；考虑

{ 1, 4, 5, 6, 9, 3, 2 }
           ^
         pivot

首先，i是递增的，直到它指向枢轴，j一直指向 2。这两个被交换，i递增，j递减，所以现在情况变成了

{ 1, 4, 5, 2, 9, 3, 6 }
              ^  ^
              i  j

arr[i] > pivot, 和arr[j] < pivot, 所以交换、递增i、递减j：

{ 1, 4, 5, 2, 3, 9, 6 }
              ^  ^
              j  i

现在j < i，所以循环停止，但递归调用是quicksort(arr, 0, 5);和quicksort(arr, 6, 6);，所以“排序”数组中的最后一个元素不是数组中的最大元素。

于 2013-01-03T22:21:48.403 回答
0

如果 left == right，你没有后备。如果您没有捕获，则代码将不会执行任何操作。

于 2013-01-03T22:19:28.697 回答