C语言快速排序（Quicksort）实现问题：单个元素未完成排序

嘿，我瞅了下你的代码，找到了两个导致最后那个元素没排好序的关键问题，咱们一步步来捋：

1. 全局变量踩的坑 #

你把i、j、x、y都声明成了全局变量，但快速排序是递归算法啊！每次递归调用qs函数时，这些全局变量会被新的调用直接覆盖，上层递归的指针位置直接乱掉，排序逻辑自然会出问题。

解决办法：把这些变量改成qs函数的局部变量，这样每次递归调用都会有自己独立的变量副本，互相不会干扰。

2. 递归调用的参数写错了 #

在qs函数末尾的递归部分，你写了这样的代码：

if (start<j) {
    qs(vect,start,j);
} else{
    if (i<end) {
        qs(vect,end,i);
    }
}

这里有俩问题：

• 右半部分的递归不该放在else里：不管左半部分是否需要递归，只要i < end，就该处理右半区间，用else会直接漏掉某些场景；
• 参数顺序完全写反了！右半部分的递归应该是qs(vect, i, end)，而不是qs(vect, end, i)，参数颠倒后区间范围直接错了，肯定排不对。

修正后的完整代码 #

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

void qs(int *vect,int start, int end); 

int main() { 
    int arr[] = {0,4,5,6,9,3,2,1}; 
    int amount = sizeof(arr)/sizeof(arr[0]); 

    // 打印排序前的数组
    for (int i = 0; i < amount; i++) { 
        printf("before = [%d]\n",arr[i]); 
    } 

    qs(arr,0,amount-1); 

    // 打印排序后的数组
    for (int i = 0; i < amount; i++) { 
        printf("after: [%d]\n",arr[i]); 
    } 

    return 0; 
} 

void qs(int *vect,int start, int end){
    // 改为局部变量，避免递归时互相干扰
    int i = start; 
    int j = end; 
    int x = vect[(start + end)/2]; 
    int y;

    do { 
        while(vect[i] < x && i < end){ 
            i++; 
        } 
        while (vect[j] > x && j > start){ 
            j--; 
        } 
        if (i<=j) { 
            y = vect[i]; 
            vect[i] = vect[j]; 
            vect[j] = y; 
            i++; 
            j--; 
        } 
    } while(i<=j); 

    // 左半区间递归，无需else包裹
    if (start < j) { 
        qs(vect, start, j); 
    } 
    // 右半区间递归，修正参数顺序
    if (i < end) { 
        qs(vect, i, end); 
    } 
    return ; 
}

验证结果 #

修正后运行代码，输出会变成：

before = [0]
before = [4]
before = [5]
before = [6]
before = [9]
before = [3]
before = [2]
before = [1]
after: [0]
after: [1]
after: [2]
after: [3]
after: [4]
after: [5]
after: [6]
after: [9]

所有元素都能正确排序啦～

内容的提问来源于stack exchange，提问作者Louis