数据结构0409归并排序课件

归并排序归并排序归并排序“归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序“归并”的含义是将两个或两个以上的有序表合并成一个新利用归并的思想实现排序假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到⌈n/2⌉个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。利用归并的思想实现排序假设初始序列含有n个记录，则可看成是n例题初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]例题初始关键字：[49][38][65][97]算法思想2-路归并排序将R[low..high]中的记录归并排序后放入T[low..high]中。当序列长度等于1时，递归结束，否则：（1）将当前序列一分为二，求出分裂点mid=⌊(low+high)/2⌋;（2）对子序列R[low..mid]递归，进行归并排序，结果放入S[low..mid]中；算法思想2-路归并排序将R[low..high]中的记录归并算法思想（3）对子序列R[mid+1..high]递归，进行归并排序，结果放入S[mid+1..high]中；（4）调用算法Merge，将有序的两个子序列S[low..mid]和S[mid+1..high]归并为一个有序的序列T[low..high]。算法思想（3）对子序列R[mid+1..high]递归，进行算法描述voidMsort(RedTypeR[],RedType&T[],ints,intt){

//将R[s..t]归并排序为T[s..t]if(s==t)T[s]=R[s];else{m=(s+t)/2;//将R[s..t]平分为R[s..m]和R[m+1..t]Msort(R,TR2,s,m);//递归地将R[s..m]归并为有序的TR2[s..m]

Msort(R,TR2,m+1,t);//递归地R[m+1..t]归并为有序的TR2[m+1..t]Merge(TR2,T,s,m,t);}//将TR2[s..m]和TR2[m+1..t]归并到T[s..t]

}//Msort

算法描述voidMsort(RedTypeR[],算法描述

voidMergeSort(SqList&L){//对顺序表L作2-路归并排序

MSort(L.r,L.r,1,L.length);}//MergeSort算法描述

将两个有序表归并为一个新的有序表的算法

voidMerge(RedTypeR[],RedType&T[],inti,intm,intn){

//将有序的记录序列R[i..m]和R[m+1..n]归并为有序的记录序列T[i..n]

intj,k;for(j=m+1,k=i;i<=m&&j<=n;++k){//将SR中记录由小到大地并入TRifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)//TR[k..n]=SR[i..m];将剩余的SR[i..m]复制到TRwhile(k<=n&&i<=m)TR[k++]=SR[i++];if(j<=n)//将剩余的SR[j..n]复制到TRwhile(k<=n&&j<=n)TR[k++]=SR[j++];}//Merge将两个有序表归并为一个新的有序表的算法

voidMerge例题52,23,80,36,68,14(s=1,t=6)[52,23,80][36,68,14][52,23][80][52][23,52][23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]例题52,23,80,36,68,算法的效率时间复杂度方面，由于每趟归并的时间复杂度O(n)，而对于有n个记录的序列来说，一共需要进行⌈log2n⌉趟归并。因此归并排序的时间复杂度是O(nlog2n)。空间复杂度方面，用顺序表实现归并排序时，需要和待排序记录个数相等的辅助存储空间，所以空间复杂度为O(n)。算法的效率时间复杂度方面，由于每趟归并的时间复杂度O(n)，总结归并排序很显然是一种稳定的排序方法。它也可用于链式存储结构存储的记录序列，并且不需要辅助的记录存储空间，但递归实现时仍然需要开辟相应的递归工作栈。总结归并排序很显然是一种稳定的排序方法。归并排序归并排序归并排序“归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序“归并”的含义是将两个或两个以上的有序表合并成一个新利用归并的思想实现排序假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到⌈n/2⌉个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。利用归并的思想实现排序假设初始序列含有n个记录，则可看成是n例题初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]例题初始关键字：[49][38][65][97]算法思想2-路归并排序将R[low..high]中的记录归并排序后放入T[low..high]中。当序列长度等于1时，递归结束，否则：（1）将当前序列一分为二，求出分裂点mid=⌊(low+high)/2⌋;（2）对子序列R[low..mid]递归，进行归并排序，结果放入S[low..mid]中；算法思想2-路归并排序将R[low..high]中的记录归并算法思想（3）对子序列R[mid+1..high]递归，进行归并排序，结果放入S[mid+1..high]中；（4）调用算法Merge，将有序的两个子序列S[low..mid]和S[mid+1..high]归并为一个有序的序列T[low..high]。算法思想（3）对子序列R[mid+1..high]递归，进行算法描述voidMsort(RedTypeR[],RedType&T[],ints,intt){

//将R[s..t]归并排序为T[s..t]if(s==t)T[s]=R[s];else{m=(s+t)/2;//将R[s..t]平分为R[s..m]和R[m+1..t]Msort(R,TR2,s,m);//递归地将R[s..m]归并为有序的TR2[s..m]

Msort(R,TR2,m+1,t);//递归地R[m+1..t]归并为有序的TR2[m+1..t]Merge(TR2,T,s,m,t);}//将TR2[s..m]和TR2[m+1..t]归并到T[s..t]

}//Msort

算法描述voidMsort(RedTypeR[],算法描述

voidMergeSort(SqList&L){//对顺序表L作2-路归并排序

MSort(L.r,L.r,1,L.length);}//MergeSort算法描述

将两个有序表归并为一个新的有序表的算法

voidMerge(RedTypeR[],RedType&T[],inti,intm,intn){

//将有序的记录序列R[i..m]和R[m+1..n]归并为有序的记录序列T[i..n]

intj,k;for(j=m+1,k=i;i<=m&&j<=n;++k){//将SR中记录由小到大地并入TRifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)//TR[k..n]=SR[i..m];将剩余的SR[i..m]复制到TRwhile(k<=n&&i<=m)TR[k++]=SR[i++];if(j<=n)//将剩余的SR[j..n]复制到TRwhile(k<=n&&j<=n)TR[k++]=SR[j++];}//Merge将两个有序表归并为一个新的有序表的算法

voidMerge例题52,23,80,36,68,14(s=1,t=6)[52,23,80][36,68,14][52,23][80][52][23,52][23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]例题52,23,80,36,68,算法的效率时间复杂度方面，由于每趟归并的时间复杂度O(n)，