1. 简述
快速排序算法是电子信息技术中最基础的优化算法，很多繁杂优化算法都是会采用排列。虽然各种各样快速排序算法早已被封裝成函数库供程序猿应用，但掌握快速排序算法的观念和基本原理，针对撰写高品质的手机软件，看起来十分关键。
文中详细介绍了普遍的快速排序算法，从优化算法观念，复杂性和应用情景等层面干了小结。
2. 好多个定义
（1）排列平稳：假如两个数同样，对她们开展的排列結果为她们的相对性次序不会改变。比如A={1,2,1,2,1}这儿排列以后是A = {1,1,1,2,2} 平稳便是排列后第一个1便是排列前的第一个1，第二个1便是排列前第二个1，第三个1便是排列前的第三个1。同样2也是一样。不稳定便是她们的次序与逐渐次序不一致。
（2）原地不动排列：指不申请办理不必要的室内空间开展的排列，便是在原先的排列数据信息中较为和互换的排列。比如快速排序，堆排序等全是原地不动排列，合拼排列，计数排序等并不是原地不动排列。
整体上说，快速排序算法有二种设计理念，一种是根据较为，另一种并不是根据较为。《算法导论》一书得出了那样一个证实：“根据较为的优化算法的最优化算法复杂度是O（N lg N）”。针对根据较为的优化算法，有三种设计理念，各自为：插入排序，互换排列和选择排序。非根据较为的快速排序算法算法复杂度为O(lg N)，往往复杂性这般低，是由于他们一般对排列数据信息有特别要求。如计数排序规定数据信息范畴不容易很大，基数排序规定数据信息能够转化成好几个特性等。
3. 根据较为的快速排序算法
如同前一节详细介绍的，根据较为的快速排序算法有三种设计理念，各自为插进，互换和挑选。针对插入排序，关键有立即插入排序，希尔排序；针对互换排列，关键有冒泡排序，快速排序；针对选择排序，关键有简易选择排序，堆排序；其他排列：归并排序。
3.1 插入排序
（1） 立即插入排序
特性：平稳排列，原地不动排列，算法复杂度O(N*N)
观念：将全部待排列数据信息分为2个编码序列，一个是井然有序编码序列S，另一个是待排列编码序列U，原始时，S为空，U为全部数据信息构成的数列，随后先后将U中的数据信息插到井然有序编码序列S中，直至U变成空。
可用情景：当数据信息早已基础井然有序时，选用插入排序能够显著降低数据传输和数据信息挪动频次，从而提高排列高效率。
（2）希尔排序
特性：非平稳排列，原地不动排列，算法复杂度O(n^lamda)(1 < lamda < 2), lamda和每一次步幅挑选相关。
观念：增加量变小排列。先将编码序列按增加量区划为原素数量类似的若干组，应用立即插入排序法对每一组开展排列，随后持续变小增加量直到为1，最终应用立即插入排序进行排列。
可用情景：由于增加量初值不易挑选，因此该优化算法不常见。
3.2 互换排列
（1）冒泡排序
特性：平稳排列，原地不动排列，算法复杂度O(N*N)
观念：将全部编码序列分成混乱和井然有序2个子序列，持续根据互换很大原素至混乱子序列首进行排列。
可用情景：同立即插入排序相近
（2）快速排序
特性：不稳定排列，原地不动排列，算法复杂度O(N*lg N)
观念：持续找寻一个编码序列的枢轴点，随后各自把低于和超过枢轴点的数据信息移到枢轴点两侧，随后在两侧数列中再次那样的实际操作，直到所有编码序列排列进行。
可用情景：运用很普遍，类似各种各样语言表达均出示了灭火吹API
3.3 选择排序
（1）简易选择排序
特性：不稳定排列（例如对3 3 2三个数开展排列，第一个3会与2互换），原地不动排列，算法复杂度O(N*N)
观念：将编码序列区划为混乱和井然有序2个子序列，找寻混乱编码序列中的最少（大）值和混乱编码序列的首原素互换，井然有序区扩张一个，循环系统下来，最后进行所有排列。
可用情景：互换少
（2） 堆排序
特性：非平稳排列，原地不动排列，算法复杂度O(N*lg N)
观念：小顶堆或是大顶堆
可用情景：比不上灭火吹普遍
3.4 其他排列
（1） 归并排序
特性：平稳排列，非原地不动排列，算法复杂度O(N*N)
观念：最先，将全部编码序列（共N个原素）当做N个井然有序子序列，随后先后合拼邻近的2个子序列，那样一直下来，直到变为一个总体井然有序的编码序列。
可用情景：外界排列
4. 非根据较为的快速排序算法
非根据较为的快速排序算法关键有三种，各自为：基数排序，桶排序和计数排序。这种优化算法均是对于独特数据信息的，比不上规定数据分布匀称，数据信息误差不容易很大。选用的观念均是运行内存换時间，因此全是是非非原地不动排列。
4.1 基数排序
特性：平稳排列，非原地不动排列，算法复杂度O(N)
观念：把每一个数据信息当做d个特性构成，先后依照d个特性对数据信息排列（每场排列可选用计数排序），复杂性为O(d*N)
可用情景：数据信息显著几个关键词或是好多个特性构成
4.2 桶排序
特性：平稳排列，非原地不动排列，算法复杂度O(N)
观念：将数据信息按尺寸分到数个桶（例如链表）里边，每一个桶內部选用简易快速排序算法开展排列。
可用情景：0
4.3 计数排序
特性：平稳排列，非原地不动排列，算法复杂度O(N)
观念：对每一个数据信息出現频次开展技术性（用hash方式记数，非常简单的hash是二维数组！），随后从大到小或是由小到大輸出每一个数据信息。
应用情景：比基数排序和桶排序普遍得多。
5. 小结
针对根据较为的快速排序算法，绝大多数简易排列(立即插入排序，选择排序和冒泡排序)全是平稳排列，选择排序以外；绝大多数高級排列（除简易排列之外的）全是不稳定排列，归并排序以外，但归并排序必须附加的储存空间。针对非根据较为的快速排序算法，他们都对数据信息规律性有特别要求 ，且选用了运行内存换時间的观念。快速排序算法这般之多，通常必须依据具体运用挑选最合适的快速排序算法。
6. 参考文献
（1）博闻《排序算法总结》：
http://www.cppblog.com/shongbee2/archive/2009/04/25/81058.html
（2）博闻：《八大排序算法》：
http://blog.csdn.net/yexinghai/archive/2009/10/10/4649923.aspx
