数据结构学习（C++）续——排序【5】归并排序

楼主^#

更多发布于：2004-05-10 22:15

<H2 >【5】归并排序</H2>
当初学习链表的时候，我们都曾经做过将两个有序链表合成一个有序链表的练习。那时我们就知道了归并的特点就是，将分段有序的序列合成整体有序的序列。在内部排序中，归并的地位并不十分重要，主要是因为附加的O(n)的储存空间；但是，归并却是外部排序的不二法门——我们只能用内排得到分段有序的序列，为了得到最后的有序序列，必须使用归并的方法。
<H3 >迭代的2路归并排序</H3>
2路归并是最简单的，并且单纯对内存中数据操作2路的往往是最好的（比如平衡树，AVL树经常优于m叉的平衡树）。所谓的迭代就是先归并len＝1的N个序列，然后是len＝2的N/2个序列，len＝4的N/4个序列……最后归并2个序列就完成了。实际写的时候，需要一个和原来序列一样大小的临时数组。执行偶数次“一趟归并”能够使得最后的结果保存在原来的数组中。
//迭代2路归并排序及其所需的子程序
template <class T>
void Merge(T S[], T D[], int l, int m, int n, int; KCN, int; RMN)
{
 //S[]源表，D[]归并后的表，l源表第一个段的起始序号，m源表第二个段的起始序号，n源表的长度
 int i = l, j = m, k = l;//i第一段的指针，j第二段的指针，k目的表指针
 for (; i < m ;; j < n; RMN++, k++)
 if (++KCN ;; S > S[j]) { D[k] = S[j]; j++; } else { D[k] = S; i++; }
 if (i < m)
 for (; i < m; i++, k++, RMN++) D[k] = S;
 else
 for (; j < n; j++, k++, RMN++) D[k] = S[j];
}
template <class T>
void MergePass(T S[], T D[], int len, int N, int; KCN, int; RMN)
{
 int i = 0;
 for (; i+2*len < N; i += 2*len) Merge(S, D, i, i+len, i+2*len, KCN, RMN);
 if (i+len < N) Merge(S, D, i, i+len, N, KCN, RMN);//剩余多于一个len，再做一次归并
 else for (; i < N; i++, RMN++) D = S;//少于等于一个len，直接复制
}
template <class T>
void MergeSort(T a[], int N, int; KCN, int; RMN)
{
 KCN = 0; RMN = 0;
 T* temp = new T[N]; int len = 1;
 while (len < N)//固定执行偶数次MergePass，最后的结果在原来的数组里
 {
 MergePass(a, temp, len, N, KCN, RMN); len *= 2;
 MergePass(temp, a, len, N, KCN, RMN); len *= 2;
 }
 delete []temp;
}
测试结果，直接取N＝100000：
Sort ascending N=100000 TimeSpared: 210ms
KCN=877968 KCN/N=8.77968 KCN/N^2=8.77968e-005KCN/NlogN=0.528589
RMN=1800000 RMN/N=18 RMN/N^2=0.00018 RMN/NlogN=1.08371
Sort randomness N=100000 TimeSpared: 230ms
KCN=1529317 KCN/N=15.2932 KCN/N^2=0.000152932KCN/NlogN=0.920741
RMN=1800000 RMN/N=18 RMN/N^2=0.00018 RMN/NlogN=1.08371
Sort descending N=100000 TimeSpared: 201ms
KCN=815024 KCN/N=8.15024 KCN/N^2=8.15024e-005KCN/NlogN=0.490693
RMN=1800000 RMN/N=18 RMN/N^2=0.00018 RMN/NlogN=1.08371
可以看到RMN是个定值，RMN/N的值是不小于log2N的最小偶数，有兴趣比较一下N＝1和N＝2的差异就明白了。和快排（N＝100000，乱序）相比，虽然归并的KCN和RMN都要少一些，但快排的速度还是要比归并排序快一倍（说明归并的额外动作多了一些），这个现象的确值得我们思考，这也是我加上KCN和RMN统计的一个意外收获——归并比快排慢不是因为KCN和RMN比快排多，而是一些额外的东西。
仔细分析就会发现，归并的多余时耗主要在小段归并上，如果我们用在N非常小的时候最为高效的直插来代替此时的归并，应该能带来效率的提升。如下面的例程，首先用直插来产生len＝32的初始归并段，然后再归并：
template <class T>
void MergeSort(T a[], int N, int; KCN, int; RMN)
{
 KCN = 0; RMN = 0;
 T* temp = new T[N]; int len = 32, i, j, k;
//分段进行直插排序，生成初始为len长的归并段
 
 for (k = 1; k < N; k += len)
 {
 for (i = k; i < k+len-1 ;; i < N; i++)//为了避免i<N这个判断，可以对原序列剩余小于len的序列另写一个直插
 {
 T temp = a; RMN++;
 for (j = i; j >= k ;; ++KCN ;; temp < a[j - 1]; j--) { a[j] = a[j - 1]; RMN++; }
 a[j] = temp; RMN++;
 }
 }
 
 while (len < N)//固定执行偶数次MergePass，最后的结果在原来的数组里
 {
 MergePass(a, temp, len, N, KCN, RMN); len *= 2;
 MergePass(temp, a, len, N, KCN, RMN); len *= 2;
 }
 delete []temp;
}
测试结果：
Sort ascending N=100000 TimeSpared: 160ms
KCN=724843 KCN/N=7.24843 KCN/N^2=7.24843e-005KCN/NlogN=0.436399
RMN=1393750 RMN/N=13.9375 RMN/N^2=0.000139375RMN/NlogN=0.839121
Sort randomness N=100000 TimeSpared: 160ms
KCN=2009896 KCN/N=20.099 KCN/N^2=0.00020099 KCN/NlogN=1.21008
RMN=2166630 RMN/N=21.6663 RMN/N^2=0.000216663RMN/NlogN=1.30444
Sort descending N=100000 TimeSpared: 170ms
KCN=2115024 KCN/N=21.1502 KCN/N^2=0.000211502KCN/NlogN=1.27337
RMN=2943750 RMN/N=29.4375 RMN/N^2=0.000294375RMN/NlogN=1.77231
对于N=100000乱序排序减少了70ms，应该说是比较满意的。
<H3 >递归的2路表归并排序</H3>
很自然的，除了从len＝1开始两两归并外，还可以从len＝N开始，1/2分裂成左右序列分别归并排序，这是一个递归过程。如果我们仔细的观察这个递归，会发现这和前面的迭代是一样的（N＝2k的情况）。递归带来的好处是可以方便的使用静态链表（非常容易实现表头的动态产生和消亡），如果我们不使用链表，研究递归的归并也没什么意思。
//递归的2路表归并排序及其所需子程序
template <class T>
int ListMerge(T a[], int link[], int head1, int head2, int; KCN)
{
 int k, head, i = head1, j = head2;//i,j为两个链表的游标，k为结果链表游标，结果链表的表头为head
 //因为没有表头节点，表头需单独处理
if (++KCN ;; a > a[j]) { head = j; k = j; j = link[j]; }
 else { head = i; k = i; i = link; }
 while (i != -1 ;; j != -1)
 {
 if (++KCN ;; a > a[j]) { link[k] = j; k = j; j = link[j]; }
 else { link[k] = i; k = i; i = link; }
 }
 if (i == -1) link[k] = j;//i链检测完，j链接上
 else link[k] = i;//否则，i链接上
 return head;//返回头指针
}
template <class T>
int rMergeSort(T a[], int link[], int low, int high, int; KCN)
{
 if (low >= high) return low;
 int mid = (low + high)/2;
 return ListMerge(a, link, rMergeSort(a, link, low, mid, KCN), rMergeSort(a, link, mid+1, high, KCN), KCN);
}
template <class T>
void ListMergeSort(T a[], int N, int; KCN, int; RMN)
{
 KCN = 0; RMN = 0; int i, cur, pre;
 int* link = new int[N];
 for (i = 0; i < N; i++) link = -1;
 cur = rMergeSort(a, link, 0, N - 1, KCN);
 for (i = 0; i < N; i++)//重排
 {
 while (cur < i) cur = link[cur];
 pre = link[cur];
 if (cur != i)
 {
 swap(a, a[cur]); RMN += 3;
 link[cur] = link; link = cur;
 }
 cur = pre;
 }
 delete []link;
}
这里的rMergeSort可以算是个间接递归的例子，注意递归是如何自动完成表头的创建与回收的——的确是个很精巧的实现，如果反过来用迭代来实现，将会很麻烦。
测试结果：
Sort ascending N=100000 TimeSpared: 50ms
KCN=853904 KCN/N=8.53904 KCN/N^2=8.53904e-005KCN/NlogN=0.514101
RMN=0 RMN/N=0 RMN/N^2=0 RMN/NlogN=0
Sort randomness N=100000 TimeSpared: 350ms
KCN=1509031 KCN/N=15.0903 KCN/N^2=0.000150903KCN/NlogN=0.908527
RMN=299973 RMN/N=2.99973 RMN/N^2=2.99973e-005RMN/NlogN=0.180602
Sort descending N=100000 TimeSpared: 70ms
KCN=815024 KCN/N=8.15024 KCN/N^2=8.15024e-005KCN/NlogN=0.490693
RMN=150000 RMN/N=1.5 RMN/N^2=1.5e-005 RMN/NlogN=0.090309
少有的在正序和逆序都有上佳表现的排序方法，但就其平均性能来说，并不十分优秀。

喜欢0 评分0

[color=blue][size=4][i][b][u] 【解决不了的事情，就不要想。世界不会因为我而改变。】 [/size][/u][/b][/i][/color]

举报回复

Samuel_na

路人甲

注册日期2004-04-18
发帖数49
QQ
铜币241枚
威望0点
贡献值0点
银元0个

加关注写私信

1楼^#

发布于：2004-05-11 12:20

你好强啊！

在教室睡觉，在图书馆吃东西，在食堂自习，在寝室读书……

举报回复喜欢评分

您需要登录后才可以回帖，登录或者注册

数据结构学习（C++）续——排序【5】归并排序

最新喜欢：