排序算法-归并排序

排序算法-归并排序

文章目录

​​基本思想​​​​2-路归并排序​​​​相邻两个有序子序列的归并​​​​归并排序​​

基本思想

归并排序：将两个或两个以上的有序子序列“归并”为一个有序序列。

在内部排序中，通常采用的是2-路归并排序。 即：将两个位置相邻的有序子序列R[/…m]和R[m+1…n]归并为一个有序序列R[/…n]。

2-路归并排序

2-路归并排序中的核心操作是，将待排序序列中前后相邻的两个有序序列归并为一个有序序列。

相邻两个有序子序列的归并

设两个有序表存放在同一数组中相邻的位置上： R[low … mid]和 R[mid + 1…high], 每次分别从两个表中取出一个记录进行关键字的比较，将较小者放入 T[low… high]中，重复此过程，直至其中一个表为空 ， 最后将另一非空表中余下的部分直接复制到T中。

void Merge{RedType R[],RedType &T[],int low,int mid,int high) { // 将有序表 R[low.. mid]和R[mid+1..high]归并为有序表 T[low.. high] i=low;j=mid+1;k=low; while(i<=mid&&j<=high) // 将R中记录由小到大地并入T中 { if(R[i].key<=R[j].key) T[k]=R[i++]; else T[k]=R[j++]; } while(i<=mid) T[k++]=R[i++]; // 将剩余的 R[low.. mid]复制到 T中 while (j<=high) T[k++]=R[j++]; // 将剩余的 R[j.high]复制到 T 中

归并排序

2-路归并排序将 R[low… high]中的记录归并排序后放入 T[low… high]中。 当序列长度等千 1 时，递归结束， 否则： ① 将当前序列一分为二， 求出分裂点 mid = (low+high)/2； ② 对子序列 R[low… mid]递归，进行归并排序，结果放入 S[low… mid]中； ③ 对子序列 R[mid + 1…high]递归，进行归并排序， 结果放入 S[mid + 1…high]中； ④ 调用算法 Merge, 将有序的两个子序列 S[low… mid]和 S[mid + 1… high]归并为一个有序的序列 T[low… high]。

void MSort(RedType R[],RedType &T[],int low,int high) { //R [low .. high]归并排序后放人 T[low.. high]中 if(low==high) T[low]=R[low]; else { mid=(low+high)/2; // 将当前序列一分为二， 求出分裂点 mid MSort(R,S,low,mid); // 对子序列 R[low.. mid]递归归并排序， 结果放入S[low .. mid] MSort(R,S,mid+1,high); // 对子序列 R[mid+1.. high]递归归并排序， 结果放人 S[mid+ 1. . high] Merge(S,T,low,mid,high); // 将S[low .. mid]和S[mid+1. .high]归并到 T[low .. high] }}void MergeSort(SqList &L) { // 对顺序表 L 做归并排序 MSort(L.r,L.r,1,L.length);}

时间复杂度： 当有n个记录时， 需进行log2n趟归并排序， 每一趟归并， 其关键字比较次数不超过n , 元素移动次数都是n, 因此， 归并排序的时间复杂度为O(nlog2n)。

空间复杂度： 用顺序表实现归并排序时， 需要和待排序记录个数相等的辅助存储空间， 所以空间复杂度为O(n)。

算法特点： (1)是稳定排序。 (2)可用于链式结构， 且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。