实现常用排序算法（一）快速排序

今天来徒手造轮子了，这次是快排！

简介

快速排序(Quick Sort)是非常常用的排序算法，平均时间复杂度为$O(n \log n)$，最坏复杂度$O(n^2)$，是一种不稳定排序。虽然有$O(n^2)$的最坏复杂度，但是快排在实践中的效率通常优于其他算法，这也是c++中的std::sort主要使用快排进行排序的原因（std::sort是混合排序算法，并非单一的快排，有空会出一篇文章解析一下其源码）

快排是典型的分治算法，快排选取一个基准值将数组按大小分成两份，一份大于基准值，一份小于基准值，然后对这两份分别递归地进行排序。

在具体实现中，通常用双指针完成这个划分操作，维护两个指针i、j，1到i-1储存$\leq$pivot的数，j+1到n储存$\geq$pivot的数，然后让i往前，j往后，如果i、j指向的两个元素都不符合条件只需要让两个元素交换就行了，一直移动i、j指针直到两个指针相遇，即完成了划分，然后再递归地进行。

实现

void quickSort(int *begin, int *end){
    if(end - begin < 2) return;
    int pivot = *(begin + (end - begin) / 2); //取中间元素的值为基准值，也可以选取首元素或尾元素等。
    int *i = begin, *j = end - 1;
    while(true){
        while(*i < pivot) ++i; //i递增时无需判断i < j，因为选取的pivot在原数组中，而且j右边的元素都大于等于pivot。
        while(pivot < *j) --j; //只要遇到pivot或者j右边的元素，i就会停下来。反之，j递减时同理。
        if(!(i < j)){ //递归地排序
            quickSort(begin, i); //1 ~ i-1 的元素都满足小于等于pivot
            quickSort(j+1, end); //j+1 ~ n 的元素都满足大于等于pivot
            return;
        }
        std::iter_swap(i, j); //相当于swap(*i, *j)
        ++i; --j; //交换后一定满足*i <= pivot，*j  >= pivot，因此移动指针。
    }
}