《图解数据结构---“内部排序”综述》
一、为什么我们要进行排序？
在当今社会里，我们经常面临要在浩如烟海的信息中查找某条信息。要使这种查找操作有效、快速，就必须按照某种合理的次序存储信息。例如，如图书馆的书籍及文献资料不是分门别类地存储，我们如何能迅速找到自己所需借阅的资料？又比如，英文字典若不是按照字母顺序排列词条，我们如何快速查找所需单词？
图书馆书籍按类存放
字典按字母顺序排列词条
二、我们什么情况下需要排序？
很多情况下，是否使用排序是一个重要的策略问题。《孙子兵法》阐述，战争的最高境界是：不战而屈人之兵；那么排序的最高境界就是：不排序。
1. 为了方便取得数据：那么Hash才是最佳的选择，因为如果使用好的解决Hash冲突方法，能够做到1+a/2 时间内取得数据，其中a为Hash表的填装因子。这远远好于二分查找带给你的logn时间复杂度。当然，你别想在Hash表找最大值，最小值，或者最大的10个数之类的问题，如果你需要这些操作，Hash不应该是你的选择。但通常情况下，人们存放用户数据的时候，往往关心的是如何取出而已。这种单纯的存取关系下，Hash绝对是最好的选择！
2. 非重复关键字数据：其实现实生活中这种情况是非常多见的，例如电话号码、身份证数据，他们往往可以成为关键字，而且排序往往是有意义的。如电话号码中0826可能是某个特定的地区，身份证511可能有特定的含义，对这些数据的如果是有序的，往往可以从中取得有用的信息。
3.大规模频繁变更数据排序：有时候我们存了相当大规模的数据， 而且随时可能有新的数据插入进来，或者旧的数据需要更新值，而我们又需要这个数据集是有序的，于是我们会经常调用排序算法来排序。这个大规模数据的情况下，性能往往是关键而敏感的，于是我们开始疯狂的优化排序算法。我们开始尝试各种混合优化排序方法，以期能够提升整个程序的性能。
三、排序的一些基本概念
1.排序：就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。
其确切定义：输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
因此，排序算法就是要确定1,2，…，n的一种排列i1,i2，…，in，使文件中的记录一次排列整理后按关键字有序。
2.稳定排序
假设待排序序列中有两个元素相等，而且在排序前和排序后两个相等的元素的相对位置不变，即有 a = b，排序前a在b前面，那么排序后，a还是要在b前面，则称这样的排序为稳定的。
排序算法的稳定性是要看具体的算法实现，比如一般情况下，直接选择排序，快速排序，希尔排序，堆排序都不是稳定排序算法，基数排序，计数排序，归并排序，插入排序，冒泡排序都是稳定排序算法。
快速排序：A = {2， 2， 1}，排序后A = {1，2，2}→不稳定
希尔排序：A = {1，2，5，4，4，7}，排序后（k = 2）；A = {1， 2， 4， 4， 5， 7} →不稳定
堆排序：A = {2，2，1}，排序后A = {1，2，2}→不稳定
直接选择排序： A = {4， 4， 2， 5},排序后 A = {2，4，4， 5}→不稳定
3.被排序对象--文件
被排序的对象--文件由一组记录组成。
记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字(Key)。
注意：在不易产生混淆时，将关键字项简称为关键字。
4.排序运算的依据--关键字
用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。
关键字的选取应根据问题的要求而定。
【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用"准考证号"作为关键字。若要按照考生的总分数排名次，则需用"总分数"作为关键字。
5.就地排序
若排序算法所需的辅助空间并不依赖于问题的规模n,也就是说辅助空间是O(1)，则称之为就地排序。
四、排序算法分析
1.排序算法的基本操作
大多数排序算法都有两个基本的操作：(1) 比较两个关键字的大小；
(2)改变指向记录的指针或移动记录本身。
注意：第(2)种基本操作的实现依赖于待排序记录的存储方式。
2. 排序算法性能评价
（1）评价排序算法好坏的标准
① 执行时间和所需的辅助空间
② 算法本身的复杂程度
（2） 排序算法的空间复杂度
若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。
非就地排序一般要求的辅助空间为O(n)。
（3） 排序算法的时间开销
大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。
五、常用排序算法汇聚
内部排序按照所使用的策略可以分为5大类，分别是
六、简述各类排序的特征
七、影响排序效果的因素
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：
①待排序的记录数目n；
②记录的大小(规模)；
③关键字的结构及其初始状态；
④对稳定性的要求；
⑤语言工具的条件；
⑥存储结构；
⑦时间和辅助空间复杂度等。
八、各类排序详述链接
《选择排序》：直接选择排序、堆排序
《插入排序》：直接插入排序、希尔排序
《交换排序》：冒泡排序、快速排序
《分配排序》：箱排序、基数排序
《归并排序》