C 快速排序函数不断崩溃

Question

我正在为学校做的作业的一部分涉及构建快速排序来对数组进行排序。我很确定我已经关闭了它，但是每当我调用它时，它就会崩溃

void quickSort(double * array, unsigned int size, int start, int stop)
{
    int swapIndex = start;
    int pivot = start;
    double temp;
    if (size > 1)
    {
        for (int i = pivot + 1; i < stop; ++i)
        {
            if (array[pivot] > array[i])
            {
                ++swapIndex;
                temp = array[i];
                array[i] = array[swapIndex];
                array[swapIndex] = temp;
            }
        }
        temp = array[swapIndex];
        array[swapIndex] = array[pivot];
        array[pivot] = temp;
        quickSort(array, size, start, swapIndex);
        quickSort(array, size, swapIndex, size);
    }
}

http://pastebin.com/Ccv4KP3j

Answer 1

注意此答案基于截至 2016 年 2 月 27 日的 Pastebin 链接

首先，您的函数的返回类型错误 - 快速排序就地工作，这意味着它不会创建任何新数组；它对您传递给它的数组进行排序。它将作为 void 函数完美运行。

请记住，在 C 中，数组只能通过引用传递，即对 quicksort 的每个递归调用都处理完全相同的数组。

你的快速排序应该像这样工作:

double arr[] = {12, -2, 4, 5, 2, 1};
quicksort(arr, 0, 5);
// arr is now sorted

int i;
for (i=0; i<6; i++){
    printf("%f, ", arr[i]);
}
printf("\n");
// prints "-2, 1, 2, 4, 5, 12"

为了清楚起见，我建议编写一个函数 void doubleSwap(double *a, double* b) 来处理所有元素交换，而不会使代码变得困惑。

您的代码导致堆栈溢出的原因有两个:

1. 初始 if 防护需要检查启动和停止是否不同 不止一个，而不仅仅是它们不同。

2. “swapIndex”变量始终与数据透视单元重叠，从而导致 困惑，因为主元值在之前发生了变异 处理整个数组。可以通过将pivot设置为来修复它 停止 - 1。

这是一个pastebin我的代码版本，但在查看它之前，请尝试使用一堆 printf 自行调试它。

另请注意，您不必将整个数组传递给 qsort - 您可以将 quickSort(array, swapIndex, stop) 替换为 quickSort(array + swapIndex, 0, stop) - swapIndex)，允许您完全摆脱 start，因为它始终为零。

void doubleSwap(double *a, double*b){
    double temp = *a;
    *a = *b;
    *b = temp;
}

void quickSort(double * array, int start, int stop)
{
    int pivot = stop - 1;
    int swapIndex = start;
    int i;

    if (start < stop - 1) {
        for (i = start; i < stop; i++) {
            if (array[i] < array[pivot]){
                doubleSwap(array + swapIndex, array + i);
                swapIndex++;
            }
        }

        // Note that `array + swapIndex` is equivalent to `&(array[swapIndex])`
        doubleSwap(array + swapIndex, array + pivot);

        fprintf(stderr, "swapIndex = %d start = %d stop = %d\n", swapIndex, start, stop);
        for (i = 0; i< NELEMS; i++){
            fprintf(stderr, "%3f, ", array[i]);
        }
        fprintf(stderr, "\n");

        quickSort(array, start, swapIndex);
        quickSort(array, swapIndex, stop);
    }
}