c - 快速排序 - 不同的实现不起作用

Question

所以我尝试实现一个quicksort算法，但我没有将i, j两者都设置为start，而是设置j为end - 1（因为end我有pivot）。我也用3-median来选择pivot. 基本上，我做与平均算法相同的事情quicksort，除了反转，我返回pivotat ioncei和j cross。但它不起作用，为什么？

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

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

int median(int arr[], int left, int right) {
    int center = (left + right) / 2;

    if (arr[left] > arr[center]) {
        swap(&arr[left], &arr[center]);
    }
    if (arr[left] > arr[right]) {
        swap(&arr[left], &arr[right]);
    }
    if (arr[center] > arr[right]) {
        swap(&arr[center], &arr[right]);
    }
    swap(&arr[center], &arr[right]);

    return arr[right];
}

int partition(int arr[], int left, int right) {
    int pivot = median(arr, left, right);
    int i = left; int j = right - 1;
    for (;;) {
        while (arr[i++] < pivot);
        while (arr[j--] > pivot);
        if (i < j) {
            swap(&arr[i], &arr[j]);
        } else {
            break;
        }
    }
    
    swap(&arr[i], &arr[right]);
    return i;
}

void quicksort(int arr[], int left, int right) {
    if (left < right) {
        int piv_pos = partition(arr, left, right);
        quicksort(arr, left, piv_pos - 1);
        quicksort(arr, piv_pos + 1, right);
    }
}

int main() {
    int test[] = { 2, 7, 1, 4, 10, 6, 12, 19, 26, 0, 40, 5, 39, 16, 0, 3, 4, 12, 2, 8 };
    int size = sizeof(test) / sizeof(test[0]);
    quicksort(test, 0, size - 1);
    for (int i = 0; i < size; i++) {
        printf("%d\n", test[i]);
    }
    return 0;
}

输出：

16
0
7
12
4
2
19
3
5
39
8
10
6
40
0
1
26
4
12
2

标签： calgorithmsortingdata-structuresquicksort