C 中带有霍尔分区的快速排序算法

Question

我对这个快速排序算法有疑问：

void swap(int *x, int *y){
    int tmp;

    tmp = *x;
    *x = *y;
    *y = tmp;
}

int partition (int *arr,int min, int max){
    int x=arr[min];
    int i=min-1;
    int j=max+1;

    while (1) {
        do {
            j--;
        } while (i < j && arr[j] < x);
        do {
            i++;
        } while (arr[i] > x);
        if  (i < j)
            swap(&arr[i],&arr[j]);
        else
            return j+1;
    }
}

void quickSort(int *arr, int inf, int sup){

    if(arr){
        if(inf < sup){
            int pivot = partition(arr, inf, sup);
            //printf("pivot = %d", pivot);
            quickSort(arr, inf, pivot-1);
            quickSort(arr, pivot+1, sup);
        }
    }
}

int main() {
    int array[] = {151, 153, 134, 137, -1, -1, -1, -1, -1, 158, 158, -1, -1, 133, 127, 158, 158};

    int dim = sizeof(array)/ sizeof(int);
    quickSort(array, 0, dim-1);

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

它应该返回一个降序排序的数组，但由于某些原因它没有返回。

//The input:(the rest of the 512 elements-long array is made of -1)
/*
151 153 134 137 -1 -1 -1 -1 -1 158 158 -1 -1 133 127 158 158

The output:
158 158 158 153 158 -1 151 134 137 133 127 -1 -1 -1 -1 -1 -1
*/

我期望算法返回一个降序排序的数组。 我尝试过切换输入，但似乎没有任何效果。

Answer 1

首先，你需要仔细调试你的分区函数。返回值应该是

j

int partition (int *arr,int min, int max){
    int x=arr[min];
    int i=min-1;
    int j=max+1;

    while (1) {
        do {
            j--;
        } while (i < j && arr[j] < x);
        do {
            i++;
        } while (arr[i] > x);
        if  (i < j)
            swap(&arr[i],&arr[j]);
        else
            return j;
    }
}

可以使用gdb或者任何ide来调试主流程，就可以得到逻辑。 对于quickSort函数，你应该使用inf->pivot,pivot + 1 ->sup;而不是忽略数组的主元索引。

void quickSort(int *arr, int inf, int sup){
    if(arr){
        if(inf < sup){
            int pivot = partition(arr, inf, sup);
            //printf("pivot = %d", pivot);
            quickSort(arr, inf, pivot);
            quickSort(arr, pivot+1, sup);
        }
    }
}

希望能有所帮助。 谢谢