一篇文章理解快排

　　一 前言
　　算法对于程序员来说，是一个不得不去过的门槛，除了面试，工作中用到的机会却很少，偶尔用到的算法都有封装好的库调用下，就可以了，少有机会去写一个，偶尔有机会写个和算法相关的函数，可能心中也有几分忐忑，没有充分测试，总是怀疑其中隐藏什么大bug，在不该爆发的场合突然爆发，留下的一地的尴尬。
　　更可气的是，算法学起来的时候看起来都明白了，很简单嘛，真正动手去写的时候，却很难写出无bug的哪怕是简单的算法代码来，说起来还是没有深刻的理解，在一些细节上总是模糊不清，似是而非。所以学习算法这件事情来说，关键是要理解深刻的背后思想，不能是简单地过一遍，而是学一分就深刻理解一分，一分不理解就不要看其他的，揉碎了融入自己的思想里面，变成自己的内功，才算有收获。 二 为什么是快速排序
　　首先的问题是为什么要排序，除了一些我们想知道排名的场合，比如高考排名等？如果不是这些场合是不是就不要排序了，排序是计算机里面的最基本需求，排序的目的想想还是挺多的，比如我们需要知道Top K值，比如我们需要取一个城市工资的中位数，这个数值比所谓的平均值要靠谱的多，还比如有了排序，就可以做范围查询，有了排序就可以二分查找法，快速查到要搜索的数据，40亿的排序数据查找一个数，只需要最多32次，简直称得上魔法。
　　那为什么是快速排序那，其实也没啥特别的，就觉得快排的思想挺有意思的，二是性能也很优秀,时间复杂度为O(nlogn), 如果面试偶尔让现场手写个快排代码，也不至于没有啥准备。
　　虽然快排也有很多种实现，这篇是介绍的最简单的实现，没做什么优化，虽然不是最有用的，但是因为最简单，所以容易理解深刻，也容易写，也记得住。 三 快速排序3.1 快排具体过程
　　总体来说，快排就三步： 从数组中选择一个基准值； 以这个基准值为界，将大于这个基准值的数放在基准值的右边，将小于基准值的数放在基准值的左边； 对左右两个区间递归秩序是第一步和第二步。 3.1.1 基准分区
　　第一步和第三步都比较简单，关键是第二步，按照步骤说明下：
　　说明： 1) 对上述的数组选择一个基准值，最简单的办法选择第一个元素作为基准值，赋值给tmp。 选择基准值后，第一个元素相当于空出来了。
　　比较
　　说明：我们设置两个指针（其实这里面是下标），分别指向数组的头部和尾部，从尾部开始判断array[j]是不是大于基准值， 因为1<6,所以需要将array[i] = array[j] ，因为比基准值小，所以要移动到前面去，且把i指针向后移动一位，因为i指针原来值的位置已经被填了值，即是处理过了。
　　说明： 我们判断i处的值是否小于基准值，小于则继续对后移动，一直移动到了array[i] == 9的位置，这时候条件不满足了。
　　说明：因为array[i] > 基准值6，则需要将array[j] = array[i], 即将i索引处的值9 赋值到j索引指向的位置。
　　填上基准值
　　说明： i==j了，说明本轮结束了，将基准值回填，这样经过了一轮的比较，我们就得到了第一个元组的正确位置，通过6将整个集合分成了两个部分，一个是左边的子集，全部小于6，一个是右边的子集全部大于6，如下：
　　3.1.2 两个子集再递归
　　通过上图我们得到了 左边子集 + 基准元组+ 右边子集，然后我们分别对左边子集再执行类似的操作，右边子集再进行类似的操作，就完成了整个数组的排序。
　　左边子集的元素范围是 【 开始索引，i-1】 右边子集的范围是【i+1,结尾索引】 3.1.3 转成实际代码// 分区 int partion(int a[], int l, int r) {   int tmp = a[l];   while (l < r) {     // 从后对前判断元素是否大于基准值，大于则r 指针对前移动     while (a[r] > tmp && l < r) {       r--;     }     // 小于则赋值给首个元素，即将值移动到前面    // 如果l==r 则相当于a[0] = a[0] 无影响     a[l] = a[r];    // 从前对后判断是否小于基准值，小于等于对后移动     while (a[l] <= tmp && l < r) {       l++;     }     // 将值移动到后面     a[r] = a[l];   }   a[r] = tmp;   return r; }   void qsort(int a[], int left, int right) {   if (left < right) {     int mid = partion(a, left, right);     // 对前面的子集进行排序     qsort(a, left, mid - 1);    // 对右边的子集进行排序     qsort(a, mid + 1, right);   } }
　　虽然代码没做任何其他优化，好处是便于理解也足够简单。 3.2 快排的时间复杂度
　　复杂度重点在于按照基准值的分区，其他的只是递归计算而已，因为分区的时候我们用的两个指针的技术条件是i == j,扫描了整个数组空间，所以分区函数的时间复杂度是O(n),所以总的时间复杂度为： O(n) = n + T(L) + T(R) 然后T(L)和T(R) 又可以做递归分解,我们按照树的形式将时间分解如下：
　　如上图所示，整个算法的耗时，就是每层耗时，而每层耗时的时间即是分区函数的时间:
　　第一层: n个元素，分区所占时间为n;
　　第二层:L子集分区时间为L，R子集分区时间为R，那第二层整体的分区所占时间为L+R,而L+R = n- 1 所以第二层耗时看作是n-1.
　　第三层:LL +LR+RL+RR = L-1+R -1 即n-3， 依次类推： O(n) = n + n-1 + n-3 + ....看这个是不是等差数列，不，别上当，再计算一层看看：
　　第四层：LLL+ LLR+LRL+LRR +RLL+RLR+RRL+RRR = LL -1 + LR -1 + RL-1 +RR -1 = (LL+LR)-2 + (RL+RR)-2 = L -1 -2 + R-1 -2 = L+R -6 = n - 7 看到了吧，这种树如果是完全二叉树，每层耗时递减得很快，完全二叉树的数量： 2的h次方（h为树高度）减去1，指数级别的增加；
　　完全二叉树的高度最低为log2n ，n为节点数，按照刚刚每次计算的耗时，如果n很大，每层接近耗时为n，则总耗时为树的高度* 每层耗时 = n log2n，即时间复杂度为O(nlog2n)这是最好的情况，如果特殊情况，本身是倒序的，那么树就变成链表，就是n n最坏的时间复杂度为O(n^2)。 四 应用和优化4.1 快排找第k大元素
　　快速排序算法除了可以排序外，还可以方便找第k大的元素，因为我们每次快排都找到了第一个元组的正确位置index，如果我们要找的第k大元素的k 小于index，那么我们就在小于基准值的集合里面去继续找第k大元素，如果第k大元素大于index，那么第k大元素在大于基准值的集合去找，但是不是找第k元素了，而是找第k-index的元素，这样每次我们都能过滤掉一个集合，性能显然很快。 4.2 优化快排
　　单边递归优化  分区后，继续对左右两边排序，我们可以把一边在本轮直接处理了，所以叫单边优化： quick_sort(arr, l, x - 1); // 对左子集排序 quick_sort(arr, x + 1 , r); // 对右子集排序
　　可以做成： void quick_sort(int *arr, int l, int r) {     while (l < r) {         // 分区         int ind = partition(arr, l, r);         // 对大于基准值的右子集正常调用递归函数          quick_sort(arr, ind + 1, r);         // 用本层处理左侧的排序         r = ind - 1;     }     return ; }
　　减少了递归的层次，提升了性能。
　　三点取中法  如果基准值选择得好，那么整个递归排序展开就是完全二叉树，性能最好，所以基准值选择很重要，有种优化是选择开头元素，结束元素，中间元素三个元素中，中间那个，当然上面的代码就不适用了，很大程度上避免选择基准值的问题。
　　分区函数优化  分区的时候我们每次只是将其中i处和j处的值其中一个赋值给另外一个，如果我们只要满足条件就做移动，直到i和j都不满足的时候，交换两者的值，减少赋值过程，这样性能更快。