算法导论学习笔记(2)－归并排序
今天学习了算法导论上的归并排序算法，并且完成了在纸上写出伪代码，以前就学过归并但是理解的不够透彻，以
前还一直困惑：为什么明明归并排序比快排的时间复杂度更稳定，为什么库函数不用归并而用快排，现在知道原因了，因为归并排序必须开额外的空间，而且空间开销还比较大，下面介绍算法：
首先，归并排序用到了分治的思想，把大数据分成若干个小数据，然后再分别对小数据进行处理，最后把小数据
合并成大数据。
其次，归并排序用到了一个最重要的特点，就是把两组已经排序的数据合并成一组有序数据，并且该过程的时间复
杂度为O(n)。
最后，算法便出来了，对于一个数组A[n]来说，我们要对他进行排序，首先，我们假设A[0~n/2]和A[n/2+1,n-1]为
有序序列,那么，我们就可以在O(n)的时间内排好序，可是，问题是，A[0~n/2]和A[n/2+1,n-1]并不是有序序列，于是我们就要将他们都变成有序序列，如何变呢？我们再分别对A[0~n/2]和A[n/2+1,n-1]进行排序即可，对于A[0~n/2]来说，我们运用和以上相同的方法，把他分成A[0~n/2/2]和A[n/2+1,n/2]，然后如果这两个数组均为有序序列的话，那么就可以把它们合并起来，然后在返回到上一层了，那么如何才能判断他们为有序呢？当只有一个元素的时候这个元素便是有序的，所以，只需要递归到元素个数为1，然后再返回合并即可。
下面是对以下下代码中的merge()（合并)函数正确性的证明:
1.当第一次循环迭代的时候，i = L, A[L, i-1]为空，是有序的序列（空也算有序序列），并且含有i-L=0个LA[n1],RA[n2]的最小的数，这时c1 = c2 = 0, LA[c1]和RA[c2]均为彼此数组中的最小的元素。
2.假设第i次迭代的时候LA[c1] &= RA[c2], 这时LA[c1]便是还没有被复制到A中的最小的元素，此时A中含有i-L个最小的元素，当执行A[i] = LA[c1]时，A中便含有i-L+1个最小的元素，然后增加c1和i进行下一次迭代，如果第一次时LA[c1] & RA[c2]，执行相似的过程。
3.循环结束后，i = r+1, 此时A中含有i-L = r-L+1个最小的元素，恰好是l~r所有的元素，并且已排好序，证毕。
//insertion_sort
const int inf = (1&&28);
void print(int* A, int n)
for (int i = 0; i & i++) {
cout && A[i] && & &;
void merge(int *A, int l, int m, int r)
int n1 = m-l+1, n2 = r-m;
int lA[(const int)(n1+1)], rA[(const int)(n2+1)];
for (int i = 0; i & n1; i++) {
lA[i] = A[i+l];
for (int i = 0; i & n2; i++) {
rA[i] = A[m+1+i];
lA[n1] = rA[n2] =
int c1 = 0, c2 = 0;
for (int i = i &= i++)
if (lA[c1] &= rA[c2]) {
A[i] = lA[c1++];
A[i] = rA[c2++];
void merge_sort(int *A, int l, int r)
if (l & r)
int m = (l + r) / 2;
merge_sort(A, l, m);
merge_sort(A, m+1, r);
merge(A, l, m, r);
int main()
int A[10] = {43,2,53,1,8,29,52,4,8,10};
cout && &before sorted: &;
print(A, 10);
merge_sort(A, 0, 10);
cout && &after sorted: &;
print(A, 10);
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'21253人阅读
数据结构（22）
将两个按值有序序列合并成一个按值有序序列，则称之为二路归并排序，下面有自底向上和自顶向下的两种排序算法，自顶向下的排序在本文末讲述，使用递归实现，代码较简洁，经供参考。
1. 归并子算法：把位置相邻的两个按值有序序列合并成一个按值有序序列。例如把序列 X[s..u] = {3, 12, 23, 32}和 序列 X[u+1..v] = {2, 5, 8, 99} 合并成序列&
Z[s..v] = {2, 3, 5, 8, 12, 23, 32, 99}, 注意合并前的元素都位于同一个有序序列的相邻位置，合并后的有序序列的下标与合并前的序列总的起始下标相同。
算法过程中需要三个整型变量，i 用来遍历归并的前一个有序序列，其初始位置是s；j 用来遍历归并的后一个有序序列，其初始值是u+1；q 用来指出归并后得到的有序序列的末尾元素的位置，其初始值是s。当遍历完成其中的一个有序序列之后，只需把另一个未结束有序序列的剩余元素复制到合并后的有序序列的末尾。
//将有序的X[s..u]和X[u+1..v]归并为有序的Z[s..v]
void merge(int X[], int Z[], int s, int u, int v)
j = u + 1;
while( i &= u && j&= v )
if( X[i] &= X[j] )
Z[q++] = X[i++];
Z[q++] = X[j++];
while( i &= u )
//将X中剩余元素X[i..u]复制到Z
Z[q++] = X[i++];
while( j &= v )
//将X中剩余元素X[j..v]复制到Z
Z[q++] = X[j++];
2. 一趟归并扫描子算法：将参加排序的序列分成若干个长度为 t 的，且各自按值有序的子序列，然后多次调用归并子算法merge将所有两两相邻成对的子序列合并成若干个长度为
2t 的，且各自按值有序的子序列。
若某一趟归并扫描到最后，剩下的元素个数不足两个子序列的长度时：
若剩下的元素个数大于一个子序列的长度 t 时，则再调用一次归并子算法 merge 将剩下的两个不等长的子序列合并成一个有序子序列若剩下的元素个数小于或者等于一个子序列的长度 t 时，只须将剩下的元素依次复制到前一个子序列后面。
/* X[0..n-1]表示参加排序的初始序列
* t为某一趟归并时子序列的长度
* 整型变量i指出当前归并的两个子序列中第1个子序列的第1个元素的位置
* Y[0..n-1]表示这一趟归并后的结果
void mergePass(int X[], int Y[], int n, int t)
int i = 0,
while( n - i &= 2 * t )
//将相邻的两个长度为t的各自有序的子序列合并成一个长度为2t的子序列
merge(X, Y, i, i + t - 1, i + 2 * t - 1);
i = i + 2 *
if( n - i & t )
//若最后剩下的元素个数大于一个子序列的长度t时
merge(X, Y, i, i + t - 1, n - 1);
//n-i &= t时，相当于只是把X[i..n-1]序列中的数据赋值给Y[i..n-1]
for( j = j & ++j )
Y[j] = X[j];
3. 二路归并排序算法：将参加排序的初始序列分成长度为1的子序列使用mergePass函数进行第一趟排序，得到 n / 2 个长度为 2 的各自有序的子序列（若n为奇数，还会存在一个最后元素的子序列），再一次调用mergePass函数进行第二趟排序，得到 n / 4 个长度为 4 的各自有序的子序列， 第 i 趟排序就是两两归并长度为 2^(i-1) 的子序列得到 n / (2^i) 长度为 2^i 的子序列，直到最后只剩一个长度为n的子序列。由此看出，一共需要
log2n 趟排序，每一趟排序的时间复杂度是 O(n), 由此可知
该算法的总的时间复杂度是是 O(n log2n)，但是该算法需要 O(n) 的辅助空间，空间复杂度很大，是 O(n).
void mergeSort(int X[], int n)
int t = 1;
int *Y = (int *)malloc(sizeof(int) * n);
while( t & n )
mergePass(X, Y, n, t);
mergePass(Y, X, n, t);
程序总的代码汇总：
#include &stdlib.h&
#include &stdio.h&
//将有序的X[s..u]和X[u+1..v]归并为有序的Z[s..v]
void merge(int X[], int Z[], int s, int u, int v)
j = u + 1;
while( i &= u && j&= v )
if( X[i] &= X[j] )
Z[q++] = X[i++];
Z[q++] = X[j++];
while( i &= u )
//将X中剩余元素X[i..u]复制到Z
Z[q++] = X[i++];
while( j &= v )
//将X中剩余元素X[j..v]复制到Z
Z[q++] = X[j++];
/* X[0..n-1]表示参加排序的初始序列
* t为某一趟归并时子序列的长度
* 整型变量i指出当前归并的两个子序列中第1个子序列的第1个元素的位置
* Y[0..n-1]表示这一趟归并后的结果
void mergePass(int X[], int Y[], int n, int t)
int i = 0,
while( n - i &= 2 * t )
//将相邻的两个长度为t的各自有序的子序列合并成一个长度为2t的子序列
merge(X, Y, i, i + t - 1, i + 2 * t - 1);
i = i + 2 *
if( n - i & t )
//若最后剩下的元素个数大于一个子序列的长度t时
merge(X, Y, i, i + t - 1, n - 1);
//n-i &= t时，相当于只是把X[i..n-1]序列中的数据赋值给Y[i..n-1]
for( j = j & ++j )
Y[j] = X[j];
void mergeSort(int X[], int n)
int t = 1;
int *Y = (int *)malloc(sizeof(int) * n);
while( t & n )
mergePass(X, Y, n, t);
mergePass(Y, X, n, t);
void print_array(int array[], int n)
for( i = 0 ; i & ++i )
printf(&%d &, array[i]);
printf(&\n&);
int main()
int array[] = {65, 2, 6, 1, 90, 78, 105, 67, 35, 23, 3, 88, -22};
int size = sizeof(array) / sizeof(int);
mergeSort(array, size);
print_array(array, size);
归并排序自顶向下排序，仅供参考：
void merge2(int *data, int start, int mid, int end)
int *temp = (int *)malloc((end-start+1)*sizeof(int));
int j = mid + 1;
int k = 0;
while(i &= mid && j &= end)
temp[k++] = data[i] &= data[j] ? data[i++] : data[j++];
while(i &= mid)
temp[k++] = data[i++];
while(j &= end)
temp[k++] = data[j++];
for(i = i &= ++i)
data[i] = temp[k++];
free(temp);
//从顶往下
void mergeSort2(int *data, int start, int end, int *des)
if(start == end)
int mid = (end + start)/2;
mergeSort2(data, start, mid, des);
mergeSort2(data, mid+1, end, des);
merge2(data, start, mid, end);
个人新博客，欢迎关注：
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：341622次
积分：4159
积分：4159
排名：第5198名
原创：86篇
转载：19篇
译文：10篇
评论：54条
(1)(1)(13)(5)(1)(1)(5)(7)(4)(10)(3)(11)(3)(9)(8)(11)(1)(18)(3)&&&&&&&&&&&&&&&
C语言实例编程:C语言二路归并排序算法
file:quick.cpp
author:
#include&iostream&
void Merge(int a[],int low,int mid,int high,int b[]);
void MSort(int a[],int low,int high,int b[]);
void main()
int a[]={4,5,9,10,51,6,46,36,6,56,67,45,36};
int b[13];
MSort(a,0,12,b);
for(int i=0;i&13;i++)
cout&&b[i]&&" ";
cout&&
for(int j=0;j&13;j++)
cout&&a[j]&&" ";
cout&&
void Merge(int a[],int low,int mid,int high,int b[])
int i=low,j=mid+1,k=
while((i&=mid)&&(j&=high))
if(a[i]&=a[j])
b[k]=a[i];
b[k]=a[j];
while(i&=mid)
a[k]=a[i];
while(j&=high)
a[k]=a[j];
k++;j++;
void MSort(int a[],int low,int high,int b[])
if(low==high)
b[low]=a[low];
int mid=(low+high)/2;
MSort(a,low,mid,b);
MSort(a,mid+1,high,b);
Merge(a,low,mid,high,b);
博客推荐
计算机等级考试图书推荐
免责声明：
① 凡本站注明“稿件来源：中国教育在线”的所有文字、图片和音视频稿件，版权均属本网所有，任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发表。已经本站协议授权的媒体、网站，在下载使用时必须注明“稿件来源：中国教育在线”，违者本站将依法追究责任。
② 本站注明稿件来源为其他媒体的文/图等稿件均为转载稿，本站转载出于非商业性的教育和科研之目的，并不意味着赞同其观点或证实其内容的真实性。如转载稿涉及版权等问题，请作者在两周内速来电或来函联系。
| 京ICP备号 |
CERNET Corporation博客访问： 560896
博文数量： 149
博客积分： 1823
博客等级： 上尉
技术积分： 3188
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
&排序算法经过了很长时间的演变，产生了很多种不同的方法。对于初学者来说，对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合，很难通用。因此，我们很有必要对所有常见的排序算法进行归纳。
&&&& 我不喜欢死记硬背，我更偏向于弄清来龙去脉，理解性地记忆。比如下面这张图，我们将围绕这张图来思考几个问题。
&&&& 上面的这张图来自一个PPT。它概括了数据结构中的所有常见的排序算法。现在有以下几个问题：
&&&& 1、每个算法的思想是什么？ &&&& 2、每个算法的稳定性怎样？时间复杂度是多少？ &&&& 3、在什么情况下，算法出现最好情况 or 最坏情况？ &&&& 4、每种算法的具体实现又是怎样的？
&&&& 这个是排序算法里面最基本，也是最常考的问题。下面是我的小结。
一、直接插入排序(插入排序)。
&&&& 1、算法的伪代码(这样便于理解)：&&&&
&&&& INSERTION-SORT (A, n)&&&&&&&&&&&& A[1 . . n] &&&& for j ←2 to n &&&&&&&&& do key ← A[ j] &&&&&&&&& i ← j – 1 &&&&&&&&& while i > 0 and A[i] > key &&&&&&&&&&&&&& do A[i+1] ← A[i] &&&&&&&&&&&&&&&&&&& i ← i – 1 &&&&&&&&& A[i+1] = key
&&&& 2、思想：如下图所示，每次选择一个元素K插入到之前已排好序的部分A[1…i]中，插入过程中K依次由后向前与A[1…i]中的元素进行比较。若发现发现A[x]>=K,则将K插入到A[x]的后面，插入前需要移动元素。
&&&& 3、算法时间复杂度。& &&&&&&& 最好的情况下：正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n)& &&&&&&& 最坏的情况下：逆序有序,这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n&2)& &&&&&&& 平均情况下：O(n&2)
&&&& 4、稳定性。& &&&& 理解性记忆比死记硬背要好。因此，我们来分析下。稳定性，就是有两个相同的元素，排序先后的相对位置是否变化，主要用在排序时有多个排序规则的情况下。在插入排序中，K1是已排序部分中的元素，当K2和K1比较时，直接插到K1的后面(没有必要插到K1的前面，这样做还需要移动！！)，因此，插入排序是稳定的。
&&&& 5、代码(c版) /whuslei &&&&&&&&&
.csharpcode, .csharpcode pre
font-size:
font-family: consolas, "Courier New", courier,
background-color: #ffaa44;
/*white-space:*/
.csharpcode pre { margin: 0 }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000 }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
background-color: #f4f4f4;
width: 100%;
.csharpcode .lnum { color: #606060; }
二、希尔排序(插入排序)
&&&& 1、思想：希尔排序也是一种插入排序方法,实际上是一种分组插入方法。先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量d2(＜d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。&&&&
&&&& 例如：将 n 个记录分成 d 个子序列： &&&&&& { R[0]，&& R[d]，&&&& R[2d]，…，&&&& R[kd] } &&&&&& { R[1]，&& R[1+d]， R[1+2d]，…，R[1+kd] } &&&&&&&& … &&&&&& { R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1] }
&&&& 说明：d=5 时，先从A[d]开始向前插入，判断A[d-d]，然后A[d+1]与A[(d+1)-d]比较，如此类推，这一回合后将原序列分为d个组。
&&&& 2、时间复杂度。& &&&& 最好情况：由于希尔排序的好坏和步长d的选择有很多关系，因此，目前还没有得出最好的步长如何选择(现在有些比较好的选择了，但不确定是否是最好的)。所以，不知道最好的情况下的算法时间复杂度。& &&&& 最坏情况下：O(N*logN)，最坏的情况下和平均情况下差不多。& &&&& 平均情况下：O(N*logN)
&&&& 3、稳定性。& &&&& 由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。(有个猜测，方便记忆：一般来说，若存在不相邻元素间交换，则很可能是不稳定的排序。)
&&&& 4、代码(c版) /whuslei &&&&&&&&& &
三、冒泡排序(交换排序)
&&&&&& 1、基本思想：通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。 &&&&&&& &&&&& 2、时间复杂度& &&&& 最好情况下：正序有序，则只需要比较n次。故，为O(n)& &&&&& 最坏情况下:& 逆序有序，则需要比较(n-1)+(n-2)+……+1，故，为O(N*N)
&&&&& 3、稳定性& &&&&& 排序过程中只交换相邻两个元素的位置。因此，当两个数相等时，是没必要交换两个数的位置的。所以，它们的相对位置并没有改变，冒泡排序算法是稳定的！
&&&&& 4、代码(c版) /whuslei &&&&&&&&&
四、快速排序(交换排序)
&&&& 1、思想：它是由冒泡排序改进而来的。在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。
&&&&&&&&&& 说明：最核心的思想是将小的部分放在左边，大的部分放到右边，实现分割。&&&&& && &&&& 2、算法复杂度& &&&&& 最好的情况下：因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关)，故为 O(N*logN)& &&&&& 最坏的情况下：基本有序时，退化为冒泡排序，几乎要比较N*N次，故为O(N*N)
&&&&& 3、稳定性& &&&&& 由于每次都需要和中轴元素交换，因此原来的顺序就可能被打乱。如序列为 5 3 3 4 3 8 9 10 11会将3的顺序打乱。所以说，快速排序是不稳定的！
&&&&& 4、代码(c版) &&&&&&&&&&
五、直接选择排序(选择排序)
&&&&& 1、思想：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。具体做法是：选择最小的元素与未排序部分的首部交换，使得序列的前面为有序。& &&&&& 2、时间复杂度。 &&&&& 最好情况下：交换0次，但是每次都要找到最小的元素，因此大约必须遍历N*N次，因此为O(N*N)。减少了交换次数！ &&&&& 最坏情况下，平均情况下：O(N*N)
&&&&& 3、稳定性 &&&&& 由于每次都是选取未排序序列A中的最小元素x与A中的第一个元素交换，因此跨距离了，很可能破坏了元素间的相对位置，因此选择排序是不稳定的！
&&&&& 4、代码(c版)/whuslei &&&&&&&&&
六、堆排序
&&&& 1、思想：利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或者最小)的记录。也就是说，以最小堆为例，根节点为最小元素，较大的节点偏向于分布在堆底附近。 &&&&& 2、算法复杂度 &&&&&&&& 最坏情况下，接近于最差情况下：O(N*logN)，因此它是一种效果不错的排序算法。
&&&&& 3、稳定性 &&&&&&&& 堆排序需要不断地调整堆，因此它是一种不稳定的排序！
&&&&& 4、代码(c版，看代码后更容易理解！)&&&&& &&&&&&&&&
七、归并排序
&&&&& 1、思想：多次将两个或两个以上的有序表合并成一个新的有序表。 &&&&&& 2、算法时间复杂度 &&&&&&&&& 最好的情况下：一趟归并需要n次，总共需要logN次，因此为O(N*logN) &&&&&&&&& 最坏的情况下，接近于平均情况下，为O(N*logN) &&&&&&&&& 说明：对长度为n的文件，需进行logN 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
&&&&& 3、稳定性 &&&&&&&& 归并排序最大的特色就是它是一种稳定的排序算法。归并过程中是不会改变元素的相对位置的。 &&&&& 4、缺点是，它需要O(n)的额外空间。但是很适合于多链表排序。 &&&&& 5、代码(略)/whuslei
八、基数排序
&&&&& 1、思想：它是一种非比较排序。它是根据位的高低进行排序的，也就是先按个位排序，然后依据十位排序……以此类推。示例如下：
&&&&&&& 2、算法的时间复杂度 &&&&&& 分配需要O(n),收集为O(r),其中r为分配后链表的个数，以r=10为例，则有0～9这样10个链表来将原来的序列分类。而d，也就是位数(如最大的数是1234，位数是4，则d=4)，即"分配-收集"的趟数。因此时间复杂度为O(d*(n+r))。
&&&&&& 3、稳定性 &&&&&&&&& 基数排序过程中不改变元素的相对位置，因此是稳定的！
&&&&&& 4、适用情况：如果有一个序列，知道数的范围(比如1～1000)，用快速排序或者堆排序，需要O(N*logN)，但是如果采用基数排序，则可以达到O(4*(n+10))=O(n)的时间复杂度。算是这种情况下排序最快的！！
&&&&&& 5、代码(略)
&&&& 总结： 每种算法都要它适用的条件，本文也仅仅是回顾了下基础。如有不懂的地方请参考课本。 &&&& 如有转载，请注明:/whuslei
阅读(16705) | 评论(0) | 转发(4) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。
