排序算法大杂烩
欢迎到原文地址阅读本文，效果更佳哦！
引言：学习数据结构之后那么算法也是必须需要了解的，甚至对于某些开发人员来说算法是他们开发工作中最为重要的一部分。数据结构和算法又是密不可分的，特定的算法需要特定的数据结构才能发挥出应有的效率。其中，熟悉各种基本的排序算法是程序猿的基本技能之一
引子
“算法+数据结构=程序”，这是一名瑞士的计算机科学家 Nicklaus Wirth 提出的著名公式，而他本人也凭借这一句话获得了图灵奖。百科百科上有这么一句评价“**这个公式对计算机科学的影响程度足以类似物理学中爱因斯坦的 $E=MC^2$ **” 。而排序算法又是各类算法中最为基础但也较为有用的算法之一，因此对它的了解也显得十分必要和重要。为了叙述方便，本文随后讨论的排序问题都约定为从小到大的排序。
选择排序
简单选择排序
简单选择排序（Simple Selection Sort）是一种直观的排序算法，其思想是在未排序的序列中选出最小的元素和序列的首位元素交换，接下来在剩下的未排序序列中再选出最小元素与序列的第二位元素交换，以此类推，最后形成从小到大的已排序序列。
下列给出 C 语言实现：
void Swap(ElementType *a,ElementType *b){
ElementType t=*a; *a = *b; *b=t;
}
void SimpleSelectionSort(ElementType A[], int N){
int i,j,min;
for(i=0;i<N-1;i++){
min=i;
for(j=i+1;j<N;j++){
if(A[j]<A[min]){
min=j; //min记录最小元素位置
}
Swap(&A[i],&A[min]); //将第 i 个元素与最小元素交换
}
}
}
可以看出，因为循环中嵌套循环，故其时间复杂度为 $O(N^2)$ 。最好情况下移动元素的次数为 0 次，这时序列已有序。最坏的情况下为 $3(N-1)$ 次（除了最后一个元素外，每个元素都要经过 3 步交换位置）。
堆排序
堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。我们知道堆是一种特殊的二叉树，每个子结点的值总是小于（或者大于）它的父结点，相应地分为最大堆和最小堆。由于堆是一个完全二叉树，一般情况下堆排序都是用数组的方式来实现。
堆排序的核心思想是：利用最大堆（或者最小堆）输出堆顶元素，即最大值（或最小值），将剩余元素重新生成最大堆（或者最小堆），继续输出堆顶元素，重复此过程，直到全部元素都已输出，得到的输出元素序列即为有序序列。
实现堆排序方法一种简单的做法是额外开辟一个辅助的数组空间，将堆顶元素逐一放入辅助数组里，最后再把辅助数组的内容复制回原始的数组。这种方法的额外空间复杂度是 $O(N)$ 。下面我们讨论一种更聪明的方法，只用 $O(1)$ 的额外空间即可。
如下图所示，首先将一个无序的序列生成一个最大堆，如图（a）所示。接下来我们不需要将堆顶元素输出，只要将它与堆的最后一个元素对换位置即可，如图（b）所示。这时我们确知最后一个元素 99 一定是递增序列的最后一个元素，而且已经在正确的位置上。 现在问题变成了如何将剩余的元素重新生成一个最大堆——也很简单，只要依次自上而下进行过滤，使其符合最大堆的性质。图（c）是调整后形成的新的最大堆。要注意的是，99 已经被排除在最大堆之外，即在调整的时候，堆中元素的个数应该减 1 。结束第 1 轮调整后，再次将当前堆中的最后一个元素 22 与堆顶元素换位，如图（d）所示，再继续调整成新的最大堆……如此循环，直到堆中只剩 1 个元素，即可停止，得到一个从小到大排列的有序序列。
插入排序
简单插入排序
简单插入排序的核心思想就是：将待排序的一组序列分为已排好序的和未排好序的两个部分；初始状态时，已排序序列仅包含第一个元素，为排序序列中的元素为除去第一个以外 $N-1$ 个元素；此后将为排序序列中的元素逐一插入到已排序的序列中。如此往复，经过 $N-1$ 次插入后，未排序序列中元素个数为 0，则排序完成。
具体到第 $k-1$ 次插入，对应待插入元素应为第 $k$ 个元素，也就是未排序序列中的第一个元素，插入的基本过程是：将它和第 $k-1$ 个元素（也就是已排序序列的最后一个元素）进行比较，若 大于第 $k-1$ 个记录，则该次循环结束；否则，将两个元素交换，再比较该数和第 $k-2$ 个元素之间 的大小，依此往复，直到该数比它当前位置的前一个元素大，或该数已交换到了第 1 个位置，则第 $k-1$次循环结束。
下面我们来看一个例子。下表显示了对 {44，12，59，36，62，43，94，7，35，52，85} 进行简单插入排序的前 3 次循环的情况。在第 2 次循环结束后，已排序序列中有 3 个记录。第 3 次循环第 1 步，将未排序序列中的第一个记录 36 和已排序组中的最后一个记录59进行比较，因满足 $36<59$ ，因此交换这两个记录；第 2 步，36仍然小于一个记录 44 ，则继续交换；直到大于前一个记录 12 ，则停止交换，第 3 次循环结束。已排序序列中新增记录 36，未排序序列中删除该记录，记录数量减 1 。
下面给出代码实现：
void InsertionSort(ElementType A[],int N){
int P,i;
ElementType temp;
for(P=1;P<N;P++){
temp=A[P]; //取出未排序序列中的第一个元素
for(i=P;i>0&&A[i-1]>temp;i--){
A[i]=A[i-1]; //依次与已排序序列中元素比较并右移
}
A[i]=temp; //放进合适的位置
}
}
由该算法代码可以看出，空间复杂度上，简单插入排序仅需要常数个额外空间；时间复杂度上，函数中有 2 个嵌套的循环，每个循环进行 $O(N)$ 次比较和交换，因此整个简单插入排序的平均时间复杂度为 $O(N^2)$ 。在最坏的情况下，对应每一个 P ,要进行P- 1 次比较和交换，总共要花费 $O(N^2)$ 次操作；在最好的情况下，也就是对已经排好序的序列进行排序，第二个循环在第一个$(A[i-1]>temp)$ 比较时就跳出，因此总共花费 $O(N)$ 次操作。此外，简单插入排序是稳定的排序，我们发现，数值相同的两个记录不会发生相对位置上的改变。
希尔排序
简单插入排序效率不高的一个重要原因是每次只交换相邻的两个元素，这样只能消去一对错位的元素。希尔排序对插人排序进行改进，试图通过每次交换相隔一定距离的元素，达到排序效率上的提升。
希尔排序的基本原理是，将待排序的一组元素按一定间隔分为若干个序列，分别进行插入排序。开始时设置的“间隔”较大，在每轮排序中将间隔逐步减小，直到“间隔”为 1 ，也就是最后一步是进行简单插入排序。
希尔排序将“间隔”定义为一组增量序列，用来分割待排序列，即将位置之差等于当前增量的元素归属于同一个子序列，并分别进行插入排序；排好后再选取下一个增量，划分子序列再次排序，直到最后一个增量（一般为1)。
【例子】对于待排序列 {44，12，59，36，62，43，94，7，35，52，85}，我们可设定增量序列为 {5，3，1}。
【解析】第一个增量为 5，因此 {44，43，85}、{12，94}、{59，7}、{36，35}、{62，52} 分别隶属于同一个子序列，子序列内部进行插入排序；然后选取第二个增量3，因此 {43，35，94，62}、{12，52，59，85}、{7，44，36} 分别隶属于同一个子序列；最后一个增量为 1，这一次排序相当于简单插入排序，但是经过前两次排序，序列已经基本有序，因此此次排序时间效率就提高了很多。希尔排序过程如下：
希尔排序算法的整体时间复杂度和增量序列的选取有关，目前并没有统一的最优增量序列。但使用增量序列 {[$N/2$]，[$N/2^2$]，...，1} 进行希尔排序时，最差情况下时间复杂度为 $O(N^2)$ ；而当使用增量序列 {$2^k-1$，...，7，3，1} 时，最差情况下时间复杂度为 $O(N^{3/2})$ ，其平均时间复杂度尚无定论，猜想结果为 $O(N^{5/4})$ 。除此之外，还有不少其他的增量序列选取方法，在各自特定的排序对象中有较好的时间复杂度的表现。
交换排序
冒泡排序
冒泡排序估计是很多非计算机相关专业学生都知道的排序算法，这也是交换排序中比较简单的方式。对元素个数为$N$的待排序序列进行排序时， 共进行 $N-1$ 次循环。在第 $k$ 次循环中，对从第 1 到第 $N-k$ 个元素从前往后进行比较，每次比较相邻的两个元素，若前一个元素大于后一个元素，则两者互换位置，否则保持位置不变。这样一次循环下来 ， 就把第 $k$ 大的元素移动到第 $N-k$ 个位置上，称为第 $k$ 趟的冒泡。整个过程一共进行 $N-1$ 趟冒泡 ，直到第 1 个和第 2 个元素比较完成 ，最终剩余最小的元素 ，留在第 1 个位置上，排序结束。
我们来看下例中对给定初始序列的冒泡排序过程，会有十分直观的理解：第 1 趟冒泡后,最大的记录 94 被移动到了第 $N$ 个位置上，它将不参与接下来的冒泡；第 2 趟冒泡后，剩余 $N-1$ 个记录中最大的记录 85 被移动到了第 $N-1$ 个位置上；经过 $N-1$ 趟冒泡后，剩余的最小记录 7 留在第 1 个位置上，排序结束，如下表所示。
快速排序
快速排序也是交换排序的一种，但和冒泡排序不同的是，冒泡排序只比较相邻两个记录 的顺序，而快速排序的原理是：将未排序元素根据一个作为基准的“主元”（Pivot）分为两个子序列，其中一个子序列的记录均大于主元，而另一个子序列均小于主元，然后递归地对这两个 子序列用类似的方法进行排序。本质上，快速排序使用分治法，将问题的规模减小，然后再分别进行处理。
首先，子序列的划分方法我们可以参考利用函数递归求取集合的中位数问题的解答。求得中位数后，将该中位数设置为待排序序列的主元，将比主元大的元素从右向左放置，而比主元小的元素从左向右放置。
下表给出了进行一趟主元调整的过程，具体步骤为：
- 选择一个主元，并与最后一个元素交换。
- 设置两个指针 Low 和 High ，初值分别指向第一和倒数第二个元素。
- Low 从左向右扫描，其位置左侧为已遍历或交换过的比主元小的元素；High从右往左扫描 ， 其位置右侧为已遍历或交换过的比主元大的元素。首先从 Low 指向的位置向右扫描，若遇到比主元大的元素，则停止；然后从 High 指向的位置向左搜索，若遇到比主元小的元素，则停止。
- 若 Low 和 High 没有错位（即Low<High)，则 High 和 Low 指向的元素互换位置。
- 重复3、4直至 High 和 Low 错位，将基准与 A[Low] 对换位置。这就完成了一次划分，以
主元为边界分别划分成大于和小于主元的两个子序列。 - 递归地对两个子序列用同样方法进行快排直至当前子序列只有一个元素时结束递归，这样就达到了分而治之的算法目的。
归并排序
归并排序是建立在归并操作基础上的一种排序方法。归并操作，是指将两个已排序的子序列合并成一个有序序列的过程。
归并排序的基本原理是：将大小为 $N$ 的序列看成 $N$ 个长度为 1 的子序列，接下来将相邻子序两两进行归并操作，形成$N/2(+1)$ 个长度为 2（或1）的有序子序列；然后再继续进行相邻子序列两两归并操作，如此一直循环，直到剩下 1 个长度为 $N$的序列，则该序列为原序列完成排序后的结果，如下图所示。
归并排序的核心在于归并操作的实现。归并操作的过程如下：首先申请额外的空间用于放置两个子序列归并后的结果，接着设置两个指针分别指向两个已排序子序列的第一个位置，然后比较两个指针指向的元素，将较小的元素放置到已申请的额外空间内，并将当前位置向后移动一格，重复以上过程，直到某一个子序列的指针指向该序列的结尾。这时候将另一个指针所指向序列的剩余元素全部放置到额外空间内，归并操作结束。
下面举个栗子
其实从相反的角度来看，归并排序可以看成是分治法的逆向过程。
基数排序
桶排序
如果已知 $N$ 个关键字的取值范围是在0到 $M-1$ 之间，而$M$比$N$小得多，则桶排序算法将为关键字的每个可能取值建立一个“桶”，即建立$M$个桶；在扫描$N$个关键字时，将每个关键字放入相应的桶中，然后按桶的顺序收集一遍就自然有序了。所以桶排序效率比一般的排序算法高——当然需要的额外条件是已知关键字的范围，并且关键字在此范围内是可列的，个数还不能超过内存空间所能承受的限度。
【例子】已知某门公共选修课有1500学生选修，其成绩为分布于[0，100]之间的整数。现需要将学生名单按其成绩从低到高顺序打印出来。
【分析】若将学生名单按成绩排序再打印，则至少需要 $O(NlogN)$ 的时间，这里 $N=1500$ 。而用桶排序的方法，可为每一个分数建立一个“桶”，共建101个桶——具体实现时可定义一个链表指针数组 Bucket[101]。顺序扫描学生名单，若当前这个学生的成绩是$i$分，则将他的记录插入 Bucket[ i] 所指的链表头部，这一操作只需2步。整个扫描的过程用去 $O(N)$ 的时间。然后顺序扫描每个Bucket[i]，将链表中的学生名单逐一打印，该过程用$O(N+M)$的时间，其中$M=101$是桶的个数。可见桶排序只需要$O(N+M)$的时间就可以完成名单的顺序打印，特别当$M=O(N)$时，这个时间复杂度是线性的。
基数排序
基数排序是桶排序的一种推广，它所考虑的待排记录包含不止一个关键字。例如对一副牌的整理，可将每张牌看作一个记录，包含两个关键字：花色、面值。一般我们可以将一个有序列是先按花色划分为四大块，每一块中又再按面值大小排序。这时“花色”就是一张牌的“最主位关键字”，而“面值”是“最次位关键字”。
对于一般有 $K$ 个关键字的情况，基数排序通常有两种方法：主位优先法（ Most Significant Digit Sort，简称 MSD）和次位优先法（ Least Significant Digit Sort，简称 LSD）。
仍以整理扑克牌为例，顾名思义，新谓主位优先法，是先为最主位关键字（花色）建立桶，将牌按花色分别装进4个桶里；然后对每个桶中的牌，再按其次位关键字（面值）进行排序，最后将4个桶中的牌收集，顺序叠放在一起。
而次位优先法，是先为最次位关键字建立桶，即按面值建立13个桶，将牌按面值分别放于13个桶中；然后将所有桶中的牌收集，顺序叠放在一起；再为主位关键字花色建立4个桶，顺序将每张牌放人对应的花色桶中，则4个花色桶中的牌必是有序的，最后只要将它们收集，顺序叠放即可。
从上述例子可见，两种方法具有不同的特点。主位优先法基本上是分治法的思路，将序列分割成子列后，分别排序再合并结果。而次位优先法是将“排序”过程分解成“分配“和“收集”这两个相对简单的步骤，并不需要分割子列排序，故一般情况下次位优先法的效率更高一些。
单关键字的基数分解
从上面可以看到，基数排序主要是对有多关键字的对象进行排序。其实可以将单个整型关键字按某种基数分解为多关键字，再进行排序。这也是“基数排序”名称的由来。例如 826 可以根据基数 10 分解为 8、2、6 这三个关键字，其中 8 是最主位关键字，6是最次位关键字；还可以根据基数 16 分解为 3、3、A 这 3 个关键字，其中第一个3是最主位关键字，A 是最次位关键字。
典型问题是给定 $N$ 个记录，每个记录的关键字为一整数，其取值范围是 0 到 M 之间。若 M 比 N 大很多（例如 $M=N^K$），这时桶排序需要 M 个桶，会造成巨大的空间浪费；而以为基数对关键字进行分解后则只需要 $R$ 个桶就可以了。让我们通过一个具体的例子来理解什么是基数分解。
【例子】给定范围在 0 到 999 之间的 10 个关键字 164,8,216,512,27,729,0,1,343,125 现用基数排序算法进行递增排序。
【分析】我们可以将每个关键字看成一个 3 位的十进制整数（不足位的在左边补 0 )，从而将每个十进制整数关键字分解成 3 个关键字，其个位数为最次位关键字，百位数为最主位关键字。这就是以 10 为基数的分解。对给定的 10 个记录用次位优先法进行基数排序，首选对最次位（个位）关键字建立 10 个桶，将记录按其个位数字的大小放入相应的桶中，如下图（a）所示。此时 10 个数字恰好均匀分布于 10 个桶中，当然一般情况下不是总有这么好的运气。每个“桶”实际上是一个链表，一趟排序后，将桶中记录重新收集成为一个新的记录链 {0，1，512，343，64，125，216，27，8，729}。接下去按下一个次位关键字（十位）排序，所得结果如下图（b）所示。注意到此时桶中记录的分布不再均匀。向桶中插入的新记录需排在链表尾部。将桶中记录收集形成新的记录链 {00，01，08，512，216，125，27，729，343，64}。最后按最主位（百位）关键字排序，结果如下图（c）所示，再收集所得的记录链就是最终有序的 {000，001，008，027，064，125，216，343，515，729}。
外部排序
外部排序是指大文件排序，即待排序的数据记录以文件的形式存储在外存储器上。由于文件中的记录很多、信息容量庞大，所以整个文件所占据的存储单元往往会超过了计算机的内存量，因此，无法将整个文件调入内存中进行排序。于是，在排序过程中需进行多次的内外存之间的交换。在实际应用中，由于使用的外设不一致，通常可以分为磁盘文件排序和磁带文件排序两大类。
外部排序基本上由两个相对独立的阶段组成。首先，按可用内存大小，将外存上含 $N$ 个记录的文件分成若干长度为 $L(<N)$ 的子文件，依次读入内存，利用内部排序算法进行排序。然后，将排序后的文件写入外存，通常将这些文件称为归并段（Run）或“顺串”；对这些归并段进行逐步归并，最终得到整个有序文件。可见外部排序的基本方法是归并排序法，下面的例子给出了一个简单的外部排序解决过程。
【例子】给定磁盘上有6大块记录需要排序，而计算机内存最多只能对3个记录块进行内排序，则外部排序的过程如下图所示。
【解析】首先将连续的3大块记录读入内存，用任何一种内部排序算法完成排序，再写回磁盘。经过2次3大块记录的内部排序，得到上图（a）的结果。然后另用一个可容纳6大块记录的周转盘，辅助最后的归并。方法是将内存分成3块，其中2块用于输入，1块用于输出，指定一个输入块只负责读取一个归并段中的记录，如上图（b）所示。归并步骤为：
- 当任一输入块为空时，归并暂停，将相应归并段中的一块信息写入内存
- 将内存中2个输入块中的记录逐一归并入输出块
- 当输出块写满时，归并暂停，将输出块中的记录写入周转盘
如此可将2个归并段在周转盘上归并成一个有序的归并段。上例的解决方法是最简单的归并法，事实上外部排序的效率还可以进一步提高。要提高外排的效率，关键要解决以下4个问题：
- 如何减少归并轮数
- 如何有效安排内存中的输入、输出块，使得机器的并行处理能力被最大限度地利用
- 如何有效生成归并段
- 如何将归并段进行有效归并
针对这四大问题，人们设计了多种解决方案，例如釆用多路归并取代简单的二路归并，就可以减少归并轮数；例如在内存中划分出2个输出块，而不是只用一个，就可以设计算法使得归并排序不会因为磁盘的写操作而暂停，达到归并和写周转盘同时并行的效果；例如通过一种“败者树”的数据结构，可以一次生成2倍于内存容量的归并段；例如利用哈夫曼树的贪心策略选择归并次序，可以耗费最少的磁盘读写时间等。
最后是广告时间，我的原创博文将同步更新在三大平台上，欢迎大家点击阅读！谢谢
