在C中快速排序

Question

我正在尝试对我的项目使用快速排序,但它不起作用.我无法弄清楚bug的位置.有谁可以帮我搞清楚吗？谢谢.

void quicksort(int arr[],int a, int b){
    if(a<=b){
        int key=arr[a];
        int index=a;
        int i=a, j=b;
        while(i<=j){
            for(;arr[j]>key;--j);
            int temp=arr[j];
            arr[j]=key;
            arr[index]=temp;
            index=j;
            for(;arr[i]<key;++i);
            temp=arr[i];
            arr[i]=key;
            arr[index]=temp;
            index=i;
            }
        quicksort(arr,a,index);
        quicksort(arr,index,b);
        }
    else return;
} 

Answer 1

你的内循环这样做:

• 从数组的右侧检查以找到应该位于左侧的元素key.
• 将所有找到的元素交换key,位于index并更新index到key新位置
• 从数组的左侧检查以找到应该位于右侧的元素key.
• 将所有找到的元素交换key,位于index并更新index到key新位置

你想在世上为什么要这样做？你应该做这个:

• 从数组的右侧检查以找到应该位于左侧的元素key.
• 从数组的左侧检查以找到应该位于右侧的元素key.
• 如果找到,交换它们.如果没有,将枢轴放在正确的位置并退出循环

我不是百分百肯定,但我认为key在你的快速排序版本中改变可能是你问题的罪魁祸首.找出答案的最佳方法是逐步调试代码,看看它出错的地方.

这是根据我上面的建议实现的,以及一些测试用例:

void swap(int arr[], int i, int j) {
    int temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
}

void quicksort0(int arr[], int a, int b) {
    if (a >= b)
        return;

    int key = arr[a];
    int i = a + 1, j = b;
    while (i < j) {
        while (i < j && arr[j] >= key)
            --j;
        while (i < j && arr[i] <= key)
            ++i;
        if (i < j)
            swap(arr, i, j);
    }
    if (arr[a] > arr[i]) {
        swap(arr, a, i);
        quicksort0(arr, a, i - 1);
        quicksort0(arr, i + 1, b);
    } else { // there is no left-hand-side
        quicksort0(arr, a + 1, b);
    }
}

void quicksort(int arr[], int len) {
    quicksort0(arr, 0, len - 1);
}

int main() {
    int a1[] = { };
    int a2[] = { 1 };
    int a3[] = { 1, 1 };
    int a4[] = { 1, 2, 3, 4, 5 };
    int a5[] = { 5, 4, 3, 2, 1 };
    int a6[] = { 9, 2, 6, 7, 5, 4, 0, 2, 7, 5 };

    quicksort(a1, 0);
    quicksort(a2, 1);
    quicksort(a3, 2);
    quicksort(a4, 5);
    quicksort(a5, 5);
    quicksort(a6, 10);
    quicksort(a6, 10);
}