分享
 
 
 

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

王朝vc·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

【5】归并排序

当初学习链表的时候,我们都曾经做过将两个有序链表合成一个有序链表的练习。那时我们就知道了归并的特点就是,将分段有序的序列合成整体有序的序列。在内部排序中,归并的地位并不十分重要,主要是因为附加的O(n)的储存空间;但是,归并却是外部排序的不二法门——我们只能用内排得到分段有序的序列,为了得到最后的有序序列,必须使用归并的方法。

迭代的2路归并排序

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[i] > S[j]) { D[k] = S[j]; j++; } else { D[k] = S[i]; i++; }

if (i < m)

for (; i < m; i++, k++, RMN++) D[k] = S[i];

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[i] = S[i];//少于等于一个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[i]; 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,应该说是比较满意的。

递归的2路表归并排序

很自然的,除了从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[i] > a[j]) { head = j; k = j; j = link[j]; }

else { head = i; k = i; i = link[i]; }

while (i != -1 && j != -1)

{

if (++KCN && a[i] > a[j]) { link[k] = j; k = j; j = link[j]; }

else { link[k] = i; k = i; i = link[i]; }

}

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[i] = -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[i], a[cur]); RMN += 3;

link[cur] = link[i]; link[i] = 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

少有的在正序和逆序都有上佳表现的排序方法,但就其平均性能来说,并不十分优秀。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有