快速排序

导语

快排的重要性不必多说，面试最容易碰到的，这里以一种易于理解的代码来展示出来。快排采用的是分治策略，每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程递归进行，以此达到整个数据变成有序。

算法

1. 从数列中选取一个基准数(一般选用第一个);

• 设置两个变量，i = left, j = right;
• 从 right 开始往前找(从后往前，j--)，找一个比基准数小的数，找到后放置到a[i]位置；
• 从 left 开始往后找(从前往后， i++)，找一个比基准数大的数，找到后放置到a[j]位置；
• 重复第3、4步，直到 i = j ，将基准数填入 a[i] 中。

跟着上面思想一步一步写出代码：

void quickSort(int *a, int left, int right) {
    if(left < right) {
        int temp = a[left], i = left, j = right;
        while(i < j) {
            while(j > i && a[j] > temp) {   //从后往前找，找一个比temp小的数
                j--;
            }
            if(j > i) { //如果找到
                a[i] = a[j];    //放置到a[i]位置
                i++;
            }
            while(j > i && a[i] < temp) {   //从前往后找，找一个比temp大的数
                i++;
            }
            if(j > i){  //如果找到
                a[j] = a[i];    //放置到a[j]位置
                j--;
            }
        }
        a[i] = temp;    //i = j ，将基准数填入 a[i] 中
        quickSort(a, left, i);
        quickSort(a, i + 1, right);
    }
}