快速排序的实现与注意点

先上实现了的C++代码：

#include  
#include  
#include  
#include  
using namespace std;
const int maxn = 100;
int a[maxn], n;
void quick_sort(int left, int right) {
    if(left > right) {
        return;
    }
    int i = left, j = right, key = a[left];
    while(i != j) {
        while(i < j && a[j] >= key) {
            j--;
        }
        //寻找分界点右边比key小的数
        while(i < j && a[i] <= key) {
            i++;
        }
        //寻找分界点左边比key大的数
        if(i != j) {
            swap(a[i], a[j]);
        }
        //如果找到了，则交换
    }
    swap(a[left], a[i]);
    //将key放到分界点的位置上，之后进行递归处理分界点两侧的数据
    quick_sort(left, i - 1);
    quick_sort(i + 1, right);
}
int main() {
    scanf("%d", &n);
    srand((unsigned)time(NULL));
    for(int i = 0; i < n; i++) {
        a[i] = rand() % 1000;
    }
    quick_sort(0, n - 1);
    for(int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("
");
    return 0;
}

 

下边说说两个注意点：

（1）关于quick_sort函数第一句，为什么要判断left是否大于right？

考虑这样一组输入数据：

10

279 786 373 946 460 552 698 754 519 759

这组数据就是为什么要有if(left > right)的原因，因为第一轮下来以后，i、j均为0（279比其他所有数都小），之后递归处理的时候，左边的区间为(0, -1)，不合法！

（2）为什么每一轮查找左右两部分的时候，都要从右端开始（下标j）？

每一轮两边找的时候，都从右边开始的原因是为了保证最终a[i]和a[left]交换的时候，a[i]>=a[left]

比如考虑这样一组数据：

6

7 1 2 3 4 8

这样如果从左边先找，第一轮下来后，将会使得i为5，交换a[0]和a[5]，左边区间为0-4，右边没有，但是左边区间有一个8，比7大！