排序算法总结（一）
On September 25, 2015, in 数据结构, 笔试面试, 算法, by sponge
本文是为了加深自己对各种算法的理解，部分摘自维基百科，这里主要介绍较为常用的排序方法，一些生僻的算法不做介绍。
.
总结各种算法之前，现介绍下几个概念：
1、稳定度：稳定排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串行中R出现在S之前，在排序过的串行中R也将会是在S之前。
2、计算的复杂度(最差、平均、和最好表现)，依据串行(list)的大小(n)。一般而言，好的表现是O(n log n)，且坏的行为是O(n2)。对于一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(n log n)。
.
稳定排序：
* 泡沫排序(bubble sort) — O(n²)
* 插入排序 (insertion sort)— O(n²)
* 桶排序 (bucket sort)— O(n); 需要 O(k) 额外空间
* 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外空间
* 合并排序 (merge sort)— O(n log n); 需要 O(n) 额外空间
* 二叉排序树排序 (Binary tree sort) — O(n log n)期望时间; O(n²)最坏时间; 需要 O(n)额外空间
* 基数排序 (radix sort)— O(n·k); 需要 O(n) 额外空间
.
不稳定排序
* 选择排序 (selection sort)— O(n²)
* 希尔排序 (shell sort)— O(n log n) 如果使用最佳的现在版本
* 堆排序 (heapsort)— O(n log n)
* 快速排序 (quicksort)— O(n log n) 期望时间, O(n2) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序
.
排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。
.
这篇文章里，将对几种基础排序介绍，包括冒泡排序、插入排序、选择排序、快速排序。稍微复杂些的排序留在二中介绍。
.
<<<<<<<<<<<<<<<<<<<<<<<分割线>>>>>>>>>>>>>>>>>>>>>>>>>>>>
.
1、冒泡排序
冒泡排序是一种简单的排序方法，算法如下：
1. 首先将所有待排序的数字放入工作列表中。
2. 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
3. 重复2号步骤(倒数的数字加1。例如：第一次到倒数第二个数字，第二次到倒数第三个数字，依此类推...)，直至再也不能交换。
用C语言实现如下：
int BubbleSort(int *a, int b){ //a是待排序的整型数组
//b是待排序数组的元素个数
int i;
int temp;
for(i = b-1; i>=0; i++){
if(a[i]>a[i+1]){
temp = a[i+1];
a[i+1] = a[i];
a[i] = temp; //交换元素
}
}
｝
最差时间复杂度 O(n²)
最优时间复杂度 O(n)
平均时间复杂度 O(n²)
最差空间复杂度 O(n) total, O(1) auxiliary
.
2、插入排序
插入排序也是一种简单排序方法，算法如下：
1. 从第一个元素开始，认为该元素已经是排好序的。
2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。
3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
4. 重复步骤3，直到已排好序的元素小于或等于新元素。
5. 在当前位置插入新元素。
6. 重复步骤2。
用C实现如下：
int InsertSort(int *a, int b){
int i,j;
int temp;
for(i = 0; i< b; i++){
temp = a[i];
for(j = i-1; j>=0; j--){
if(a[j] > temp)
a[j+1] = a[j]; //将元素往右移动
else{
a[j+1]=temp;
break;
}
}
}
｝
最差时间复杂度 O(n²)
最优时间复杂度 O(n)
平均时间复杂度 O(n²)
最差空间复杂度 O(n) total, O(1) auxiliary
.
3、选择排序
选择排序的思想如下：
1. 设数组内存放了n个待排数字，数组下标从1开始，到n结束。
2. i=1
3. 从数组的第i个元素开始到第n个元素，寻找最小的元素。(具体过程为:先设arr[i]为最小，逐一比较，若遇到比之小的则交换)
4. 将上一步找到的最小元素和第i位元素交换。
5. 如果i=n-1算法结束，否则回到第3步
用C语言实现如下：
int SelectSort(int *a, int b){
int i,j;
int flag; //用于记录哪个元素最小
int temp;
for(i = 0; i< b; i++){
flag = i;
for(j = i+1; j a[j]){
flag = j;
} //选出从i开始最小的元素
}
temp = a[flag];
a[flag] = a[i];
a[i] = temp; //交换元素
}
｝
最差时间复杂度 О(n²)
最优时间复杂度 О(n²)
平均时间复杂度 О(n²)
最差空间复杂度 О(n) total, O(1) auxiliary
.
以上三种排序的时间复杂度都是O(n²)。
.
4、快速排序
实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。
快速排序的基本算法是：
1. 从数列中挑出一个元素，称为 "基准"(pivot)，
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后，该基准是它的最后位置。这个称为分割(partition)操作。
3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代(iteration)中，它至少会把一个元素摆到它最后的位置去。
用C语言实现如下：
void swap(int *a, int *b)
{
int t=*a; *a=*b; *b=t;
}
int QuickSort(int *a, int b){
int i, j;
int base;
if(b>1){
base = a[0]; //设第一个元素为基准
i = 1; j = b-1;
while(i<j){
if(a[i]<base)
i++;
else
swap(&a[i],&a[j--]);//如果i位置的数大于基准，则往后移
}
if(a[i]<base){ //将基准插入到中间
swap(&a[0], &a[i]);
QuickSort(a, i+1);
QuickSort(&a[i+1], b-i-1);
}
else{
swap(&a[0], &a[i+1]);
QuickSort(a, i);
QuictSort(&a[i],b-i);
}
}
}
快速排序的时间复杂度是O(nlogn)，但是最坏情况下复杂度是O(n²)。
最差时间复杂度 Θ(n²)
最优时间复杂度 Θ(nlogn)
平均时间复杂度 Θ(nlogn) comparisons
最差空间复杂度 根据实现的方式不同而不同
几种常见排序算法的介绍及复杂度分析
相关概念
1、稳定排序(stable sort)和非稳定排序
稳定排序是指所有相等的数经过某种排序算法操作后仍然能保持它们在排序之前的相对次序。反之就是非稳定排序。
2、内排序(internal sorting)和外排序(external sorting)
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序;在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。
排序算法
【冒泡排序】(Bubble Sort)
冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置;处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。
冒泡排序是稳定的。算法时间复杂度是O(n2)。
【选择排序】(Selection Sort)
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第 i 遍处理是将[i..n]中最小者与位置 i 交换位置。这样，经过 i 遍处理之后，前 i 个记录的位置已经是正确的了。
选择排序是不稳定的。算法复杂度是O(n2 )。
【插入排序】(Insertion Sort)
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L和L[i-1]，如果L[i-1]≤ L，则L[1..i]已排好序，第i遍处理就结束了;否则交换L与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。
直接插入排序是稳定的。算法时间复杂度是O(n2)
【堆排序】(Heap Sort)
堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
堆排序是不稳定的。算法时间复杂度O(nlog2n)。
【归并排序】(Merge Sort)
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是稳定的。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。
【快速排序】(Quick Sort)
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数(以它为基准点吧)的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。
快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。
各排序方法对比
冒泡排序算法时间复杂度是O(n^2)
选择排序算法时间复杂度是O(n^2)
插入排序算法时间复杂度是O(n^2)
快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n^2)。
堆排序算法时间复杂度是O(nlogn)
归并排序算法时间复杂度是O(nlogn)
1.基本概念
1.1稳定排序(stable sort)和非稳定排序
稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，。反之，就是非稳定的排序。
比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，
则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。
1.2内排序( internal sorting )和外排序( external sorting)
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序;在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。
1.3算法的时间复杂度和空间复杂度
所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
2.几种常见算法
2.1冒泡排序 (Bubble Sort)
冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置;处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。
冒泡排序是稳定的。算法时间复杂度是O(n2)。
2.2选择排序 (Selection Sort)
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
选择排序是不稳定的。算法复杂度是O(n2 )。
2.3插入排序 (Insertion Sort)
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L和L[i-1]，如果L[i-1]≤ L，则L[1..i]已排好序，第i遍处理就结束了;否则交换L与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。
直接插入排序是稳定的。算法时间复杂度是O(n2)
2.4堆排序
堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
堆排序是不稳定的。算法时间复杂度O(nlog n)。
2.5归并排序
设有两个有序(升序)序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。
归并排序是稳定的。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。
2.6快速排序
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数(以它为基准点吧)的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。
快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。
排序算法总结（二）
所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。当待排序记录的关键字都不相同时，排序结果是惟一的，否则排序结果不惟一。
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。
要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
一.插入排序
插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。
①.直接插入排序(稳定)
接插入排序的过程为：在插入第i个记录时，R1,R2,..Ri-1已经排好序，将第i个记录的排序码Ki依次和R1,R2,..,Ri-1的排序码逐个进行比较，找到适当的位置。使用直接插入排序，对于具有n个记录的文件，要进行n-1趟排序。
代码如下:
[cpp] view plaincopyvoid Dir_Insert(int A[],int N) //直接插入排序
{
int j,t;
for(int i=1;i
{
t=A[i];
j=i-1;
while(A[j]>t)
{
A[j+1]=A[j];
j--;
}
A[j+1]=t;
}
}
②.希尔排序(不稳定)：
希尔(Shell)排序的基本思想是：先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后，取得第二个增量d2
一般取d1=n/2，di+1=di/2。如果结果为偶数，则加1，保证di为奇数。
希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，其平均时间复杂度为O(n^1.3).
代码如下:[cpp] view plaincopyvoid Shell(int A[],int n) //Shell排序
{
int i,j,k,t;
(n/2)%2 == 0 ? k = n/2+1 : k = n/2; //保证增量为奇数
while(k > 0)
{
for(j=k;j
{
t = A[j];
i = j - k;
while(i>=0 && A[i]>t)( 万业宝 www.WANYEBAO.cOM )
{
A[i+k]=A[i];
i=i-k;
}
A[i+k]=t;
}
if(k == 1) break;
(k/2)%2 ==0 ? k=k/2+1 : k=k/2;
}
}
二.选择排序
选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。选择排序中主要使用直接选择排序和堆排序。
①.直接选择排序(不稳定)
直接选择排序的过程是：首先在所有记录中选出序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换......依次类推，直到所有记录排完为止。
无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需要做n-i次比较，因此，总的比较次数为n(n-1)/2=O(n^2)。当初始文件为正序时，移动次数为0;文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为O(n^2)。直接选择排序是不稳定的。
代码如下:
[cpp] view plaincopyvoid Dir_Choose(int A[],int n) //直接选择排序
{
int k,t;
for(int i=0;i
{
k=i;
for(int j=i+1;j
{
if(A[j]
}
if(k!=i)
{
t=A[i];
A[i]=A[k];
A[k]=t;
}
}
}
②.堆排序(不稳定)
堆排序是一种树形选择排序，是对直接选择排序的有效改进。n个关键字序列
K1,K2,...,Kn称为堆，当且仅当该序列满足(Ki<=K2i且Ki<=K2i+1)或(Ki>=K2i且Ki>=K2i+1),(1<=i<=n/2)。根结点(堆顶)的关键字是堆里所有结点关键字中最小者，称为小根堆;根结点的关键字是堆里所有结点关键字中最大者，称为大根堆。
若将此序列所存储的向量R[1..n]看作是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
堆排序的关键步骤有两个：一是如何建立初始堆;二是当堆的根结点与堆的最后一个结点交换后，如何对少了一个结点后的结点序列做调整，使之重新成为堆。堆排序的最坏时间复杂度为O(nlog2n),堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较 次数较多，所以堆排序不适宜于记录较少的文件。堆排序是就地排序，辅助空间为O(1)，它是不稳定的排序方法。
代码略..
三.交换排序
交换排序的基本思想是：两两比较待排序记录的排序码，并交换不满足顺序要求的那写偶对，直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序.
①.冒泡排序(稳定的)
冒泡排序将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R;凡扫描到违反本原则的轻气泡，就使其向上"漂浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
冒泡排序的具体过程如下：
第一步，先比较k1和k2，若k1>k2，则交换k1和k2所在的记录，否则不交换。继续对k2和k3重复上述过程，直到处理完kn-1和kn。这时最大的排序码记录转到了最后位置，称第1次起泡，共执行n-1次比较。
与第一步类似，从k1和k2开始比较，到kn-2和kn-1为止，共执行n-2次比较。
依次类推，共做n-1次起泡，完成整个排序过程。
若文件的初始状态是正序的，一趟扫描即可完成排序。所需关键字比较次数为n-1次，记录移动次数为0。因此，冒泡排序最好的时间复杂度为O(n)。
若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1<=i<=n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较次数达到最大值n(n-1)/2=O(n^2),移动次数也达到最大值3n(n-1)/2=O(n^2)。因此，冒泡排序的最坏时间复杂度为O(n^2)。
虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均性能比直接插入排序要差得多。冒泡排序是就地排序，且它是稳定的。
代码如下:
[cpp] view plaincopyvoid QP(int A[],int n) //优化的冒泡排序
{
int count=0,t,flag;
for(int i=0;i
{
flag=0;
for(int j=0;j
{
if(A[j+1]
{
t=A[j];
A[j]=A[j+1];
A[j+1]=t;
flag=1;
count+=3;
}
}
if(flag==0) break;
}
}
②.快速排序：(不稳定的)
快速排序采用了一种分治的策略，通常称其为分治法，其基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
快速排序的具体过程如下：
第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。
第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。
代码如下:
[cpp] view plaincopy void swap(int *a, int *b) //交换函数
{
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int *array, int low, int high)
{
int middle = (low+high)/2, temp, pivot,i,j;
//选择第一个元素，最后一个元素，中间元素中的中间值作为支点
if (array[middle] < array[low])
swap(&array[middle], &array[low]);
if (array[high] < array[low])
swap(&array[high], &array[low]);
if (array[high] < array[middle])
swap(&array[high], &array[middle]);
pivot = array[middle]; // 选中支点
swap(&array[middle], &array[high-1]);//将支点值换到倒数第二个位置
for (i=low, j=high-1; ;) {
while (array[++i]
while (pivot
if (i < j) { //交换两个元素
temp = array[j];
array[j]=array[i];
array[i]=temp;
} else
break;
}
swap(&array[i], &array[high-1]); //将支点换回i点, 第一次分组结结束
return i;
}
给出一种比较简洁的写法：
[cpp] view plaincopyvoid Quick_Sort(int A[],int low,int high) //low和high是数组的下标
{
if(low
{
int temp,t=A[low];
int l=low,h=high;
while(l
{
while(A[l]
while(A[h]>=t) h--;
if(h>l)
{
temp=A[l];
A[l]=A[h];
A[h]=temp;
}
}
Quick_Sort(A,low,l-1);
Quick_Sort(A,l+1,high);
}
}
四.归并排序
归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并。直到得到长度为n的有序表，排序结束。
归并排序是一种稳定的排序，可用顺序存储结构，也易于在链表上实现，对长度为n的文件，需进行log2n趟二路归并，每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。归并排序需要一个辅助向量来暂存两个有序子文件归并的结果，故其辅助空间复杂度为O(n),显然它不是就地排序。
[cpp] view plaincopyvoid merge(int *array, int *temp_array, int left, int right, int right_end)
{
int left_end = right - 1, i;
int tmp = left;
int num = right_end - left+1;
while (left <= left_end && right <= right_end)
if (array[left] <= array[right])
temp_array[tmp++] = array[left++];
else
temp_array[tmp++] = array[right++];
while (left <= left_end)
temp_array[tmp++] = array[left++];
while (right <= right_end)
temp_array[tmp++] = array[right++];
for (i=0; i
array[right_end] = temp_array[right_end];
}
void m_sort(int *array, int *temp_array, int left, int right)
{
int center;
if (left < right) {
center = (left+right)/2;
m_sort(array, temp_array, left, center);
m_sort(array, temp_array, center+1, right);
merge(array, temp_array, left, center+1, right);
}
}
void merge_sort(int *array, int size)
{
int *temp = (int*)malloc(size);
memset(temp, 0, size);
m_sort(array, temp, 0, size-1);
free(temp);
}
五.基数排序
设单关键字的每个分量的取值范围均是C0<=Kj<=Crd-1(0<=j<=rd),可能的取值个数rd称为基数.基数的选择和关键字的分解因关键字的类型而异.
(1).若关键字是十进制整数，则按个、十等位进行分解，基数rd=10,C0=0,C9=9,d为最长整数的位数.
(2).若关键字是小写的英文字符串，则rd=26,C0='a',C25='z',d为最长字符串的长度.
基数排序的基本思想是：从低位到高位依次对待排序的关键码进行分配和收集，经过d趟分配和收集，就可以得到一个有序序列.