c - 快速排序不适用于大输入

Question

有人能发现我下面的快速排序实现有问题吗？它似乎在元素超过 10 个左右的数组上失败。

void swap(int *p1, int *p2)
{
    int temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

void generateRandom(int arr[], int size)
{
    srand(time(NULL));
    int i;

    for (i = 0; i < size; i++)
    {
        arr[i] = rand() % 100;
    }
}

int partition(int arr[], int start, int end)
{
    int i = start, j = end;
    int pivot = arr[start];

    for (;;)
    {
        for (; arr[i] < pivot; i++);
        for (; arr[j] > pivot; j--);

        if (i < j)
        {
            swap(&arr[i], &arr[j]);
        }
        else
        {
            return j;
        }
    }
}

void quickSort(int arr[], int start, int end)
{
    int part;

    if (start < end)
    {
        part = partition(arr, start, end);
        quickSort(arr, start, part);
        quickSort(arr, part + 1, end);
    }
}

int main()
{
    generateRandom(arr, 100);
    for (i = 0; i < 100; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    quickSort(arr, 0, 99);
    for (i = 0; i < 100; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    return 0;
}

Answer 1

首先，您的代码无法编译。当我进行更正以使其编译时(添加 stdio.h，以及在 main 中对 arr 和 i 的定义)它无限循环，如果分区以枢轴开始和结束，它将执行此操作。您需要在比较之前而不是之后递增和递减。您可以通过从 i = start-1 和 j = end+1 开始并将内部循环更改为先递增或递减来做到这一点，或者您可以保持原样并在交换后执行 i++ 和 j--我这样做了，排序成功了。

请注意，对于已经排序的数组，您的枢轴选择很差；你真的应该选择 3 个甚至 9 个值的中位数。

附言其他理想的优化:1)切换到小分区的插入排序——最佳截止点是机器相关的。另一种方法是不对小于一定大小的分区进行排序，然后在快速排序完成后对整个数组进行插入排序。如果仔细操作，也可以使用堆排序代替插入排序；谷歌介绍。 2) quicksort 做两次递归调用；通过设置 start = part + 1 和循环来消除第二个。 3) 通过先对较大的分区进行快速排序来避免堆栈溢出的可能性。 4) 通过使用显式堆栈消除第一次递归调用。 5) 内联 swap() 和 partition()。 6) 不要理会这些，只需调用 qsort 库例程即可。 :-)