一篇文章理解快排

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