QuickSort C 实现未按预期工作

Question

我正在尝试在 C 中实现 QuickSort 算法，但是它给我带来了相当困难的时间，我不知道我做错了什么，但有时输出不是我预期的那样：

#include <stdio.h>
#include <stdlib.h>

void printArray(int array[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", array[i]);
    printf("\n");
}

void swap(int *a, int *b) {
    int aux;
    aux = *a;
    *a = *b;
    *b = aux;
}

int partition(int array[], int l, int r, int size) {
    int pivot_index = (l + r) / 2;
    int pivot = array[pivot_index];
    while (l < r) {
        while (l < size && pivot >= array[l])
            l++;
        while (r >= 0 && pivot < array[r])
            r--;
        if (l < r)
            swap(&array[l], &array[r]);
    }
    swap(&array[pivot_index], &array[r]);
    return r;
}

void quickSort(int array[], int start, int end, int size) {
    int pivot;
    if (end > start) {
        pivot = partition(array, start, end, size);
        quickSort(array, start, pivot - 1, size);
        quickSort(array, pivot + 1, end, size);
    }
}

int main() {
    int array_test[] = { 948, 4, 0, 89, 7, 34, 1, 3 };
    printArray(array_test, (sizeof(array_test) / sizeof(array_test[0])));
    quickSort(array_test, 0,
              (sizeof(array_test) / sizeof(array_test[0])),
              (sizeof(array_test) / sizeof(array_test[0])));
    printArray(array_test, (sizeof(array_test) / sizeof(array_test[0])));
    return 0;
}

输入array/Output数组：

948 4 0 89 7 34 1 3 -> 3 1 4 0 7 34 89 948

9 8 7 6 5 4 3 2 1 0 -> 0 1 2 4 3 5 6 7 8 9

9 8 7 59 6 5 4 6 3 0 2 1 0 -> 0 0 1 2 3 5 4 6 6 9 7 8 59

954 485 0 345 1 36 -> 954 36 0 1 345 485

如您所见，一些数组给我一些非常奇怪的结果，我真的不知道为什么，所以如果有人能帮我解决这个问题，我将不胜感激。

Answer 1

你的主要错误在这里

quickSort(array_test, 0, (sizeof(array_test) / sizeof(array_test[0])) , (sizeof(array_test) / sizeof(array_test[0])));

您传递的大小和结尾值相同。你需要

quickSort(array_test, 0, (sizeof(array_test) / sizeof(array_test[0])) - 1 , (sizeof(array_test) / sizeof(array_test[0])));

此外，当你像那样做很多索引杂耍时，你也可以这样做

int partition(int array[], int l, int r, int size) {
    assert(r > -1 && r < size);
    assert(l > -1 && l < size);

如果您使用无效索引，这将在您的调试器中立即停止。这会发现你的错误

Answer 2

您的代码中存在多个问题：

在 main() 中，您为 r 传递的初始值太大：您应该传递 (sizeof(array_test) / sizeof(array_test[0])) - 1.
用 int pivot_index = (l + r) / 2; 计算中间索引是不正确的：它可能会在非常大的数组上溢出。使用 int pivot_index = l + (r - l) / 2;
在 partition() 函数中，循环测试 l < size 和 r >= 0 不正确：您应该比较 l 和 r 到切片的边界而不是整个数组的边界。
最后一个陈述 swap(&array[pivot_index], &array[r]); 不正确，因为枢轴可能已经移动。
事实上，r可能不是枢轴值的最终索引，因此递归调用不应省略此索引。消除枢轴索引的经典技巧涉及将枢轴交换到切片的开头或结尾，并将其交换回 r.
的最终值

这是修改后的版本：

#include <stdio.h>

void printArray(const int array[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", array[i]);
    printf("\n");
}

void swap(int *a, int *b) {
    int aux;
    aux = *a;
    *a = *b;
    *b = aux;
}

int partition(int array[], int l, int r, int size) {
    int first = l;
    int last = r;
    int pivot_index = l + (r - l) / 2;
    int pivot = array[pivot_index];
    swap(&array[first], &array[pivot_index]);
    while (l < r) {
        while (l < last && pivot >= array[l])
            l++;
        while (r > first && pivot < array[r])
            r--;
        if (l < r)
            swap(&array[l], &array[r]);
    }
    swap(&array[first], &array[r]);
    return r;
}

void quickSort(int array[], int start, int end, int size) {
    if (start < end) {
        int pivot = partition(array, start, end, size);
        quickSort(array, start, pivot - 1, size);
        quickSort(array, pivot + 1, end, size);
    }
}

int main() {
    int array_test[] = { 948, 4, 0, 89, 7, 34, 1, 3 };
    int array_length = sizeof(array_test) / sizeof(array_test[0]);
    printArray(array_test, array_length);
    quickSort(array_test, 0, array_length - 1, array_length);
    printArray(array_test, array_length);
    return 0;
}

请注意，最后一个参数 size 未在 partition() 函数中使用，在 quickSort 函数中也不需要。将元素的数量传递给两个函数并在递归时调整数组指针实际上会减少混淆。

这是一个简化版本：

#include <stdio.h>

void printArray(const int array[], int length) {
    for (int i = 0; i < length; i++)
        printf("%d ", array[i]);
    printf("\n");
}

void swap(int *a, int *b) {
    int aux = *a;
    *a = *b;
    *b = aux;
}

int partition(int array[], int length) {
    int l = 1;
    int r = length - 1;
    int pivot_index = length / 2;
    int pivot = array[pivot_index];
    swap(&array[0], &array[pivot_index]);
    for (;;) {
        while (l < length - 1 && pivot >= array[l])
            l++;
        while (r > 0 && pivot < array[r])
            r--;
        if (l < r)
            swap(&array[l], &array[r]);
        else
            break;
    }
    swap(&array[0], &array[r]);
    return r;
}

void quickSort(int array[], int length) {
    if (length > 1) {
        int pivot = partition(array, length);
        quickSort(array, pivot);
        quickSort(&array[pivot + 1], length - pivot - 1);
    }
}

int main() {
    int array_test[] = { 948, 4, 0, 89, 7, 34, 1, 3 };
    int array_length = sizeof(array_test) / sizeof(array_test[0]);
    printArray(array_test, array_length);
    quickSort(array_test, array_length);
    printArray(array_test, array_length);
    return 0;
}

最后一个改进：在较小的一半上递归限制堆栈深度并避免 堆栈溢出 在病态情况下：

void quickSort(int array[], int length) {
    while (length > 1) {
        int pivot = partition(array, length);
        if (pivot < length - pivot) {
            quickSort(array, pivot);
            array += pivot + 1;
            length -= pivot + 1;
        } else {
            quickSort(&array[pivot + 1], length - pivot - 1);
            length = pivot;
        }
    }
}

QuickSort C 实现未按预期工作

QuickSort C implementation not working as expected

c

arrays

sorting

quicksort