快速排序的C语言实现

Question

我正在尝试用 C 语言实现快速排序，但排序没有按预期进行。

#include <stdio.h>

void quickSort(int arr[], int length);
void qSrtRec(int arr[], int low, int high);
void swap(int* x, int* y);
int partition(int arr[], int low, int high);

int main() {
    int arr[] = { 5,3,7,0,1,4,8,9,6,2 }; // test array

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

    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        printf("%d, ", arr[i]);
    printf("\n");

    return 0;
}

void swap(int* x, int* y) {
    *x += *y;
    *y = *x - *y;
    *x -= *y;
}

void quickSort(int arr[], int length) {
    qSrtRec(arr, 0, length - 1);
}

void qSrtRec(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        qSrtRec(arr, low, pivot - 1);
        qSrtRec(arr, pivot + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int i = low, pivotValue = arr[high];

    for (int j = low; j < high; j++)
        if (arr[j] <= pivotValue) {
            swap(&arr[i], &arr[j]);
            i++;
        }

    swap(&arr[high], &arr[i]);

    return i;
}

与测试数组相比，我得到的输出为 0, 0, 2, 0, 0, 0, 0, 7, 0, 0。交换函数工作正常，但我不确定分区函数。

Answer 1

功能Swap就是问题。如果你将其替换为：

void swap(int* x, int* y) {
    int t = *y;
    *y = *x;
    *x = t;
}

程序现在输出0, 1, 2, 3, 4, 5, 6, 7, 8, 9,