快速排序的C语言实现

li9yvcax  于 2023-01-16  发布在  其他
关注(0)|答案(1)|浏览(131)

我试图在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。交换函数工作正常,但我不确定分区函数。

t3psigkw

t3psigkw1#

Swap函数是问题所在。如果将其替换为以下内容,它将工作:

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

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

相关问题