数据结构第25讲-归并排序和数排序-C.ppt

《数据结构第25讲-归并排序和数排序-C.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章内部排序10.1排序的基本概念10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.6基数排序10.7各种内部排序方法的比较10.5归并排序归并就是将两个或两个以上的有序数据序列合并成一个有序数据序列的过程。采用归并的思想进行排序—归并排序。假设初始序列含有n个记录，则可看成是n个有序的子序列；每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1有序的子序列，再两两归并，...如此重复，直至得到一个长度为n的有序序列为止。这种排序方法称为2-路归并。例：关键字序列T=（21，25，49，25*，93，62，72

2、，08，37，16，54），请给出归并排序的具体实现过程。212525*9362720837165449212525*4962930872163754163754212525*490862729308212525*496272930816212525*374954627293len=1len=2len=4len=8len=16163754整个归并排序仅需log2n趟voidMerge(RcdTypeSR[]，RcdType&TR[]，inti，intm，intn){//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n

3、]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]复制到TRif(j<=n)TR[k..n]=SR[j..n];//将剩余的SR[j..n]复制到TR}//merge2-路归并排序的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，其算法为：一趟归并排序的操作是，调用[n/2h]次算法merge将

4、SR[1..n]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，并存放在TR[1..n]中，整个归并排序需进行[log2n]趟。voidMSort(RcdTypeSR[]，RcdType&TR1[]，ints，intt){//将SR[s..t]归并排序为TR1[s..t]if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//将SR[s..t]平分为SR[s..m]SR[m+1..t]Msort(SR,TR2,s,m)//递归地将SR[s..m]归并为TR2[s..m]Msort(SR,TR2,m

5、+1,t)//递归地将SR[m+1..t]归并为TR2[m+1..t]Merge(TR2,TR1,s,m,t)//TR2[s..m]和TR2[m+1..t]归并为TR1[s..t]}}//Msort递归形式的2-路归并排序算法：voidMergeSort(SqList&L){//对顺序表L进行归并排序Msort(L.r，L.r，1，L.length)}//MergeSort归并排序分析在归并排序算法中，递归深度为O(log2n)，记录关键字的比较次数为O(nlog2n)。算法总的时间复杂度为O(nlog2n)。归并排序占用附加存储较多，需要另外

6、一个与原待排序记录数组同样大小的辅助数组。这是这个算法的缺点。与快速排序和堆排序相比，归并排序的最大特点是，它是一种稳定的排序方法。第10章内部排序10.1排序的基本概念10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.6基数排序10.7各种内部排序方法的比较10.6基数排序1.多关键字排序以扑克牌排序为例。每张扑克牌有两个“关键字”：花色和面值。其有序关系为：花色：面值：2<3<4<5<6<7<8<9<10

7、,A这就是多关键字排序。排序后形成的有序序列叫做词典有序序列。对于上例两关键字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情况下，假定有一个n个对象的序列{R1,R2,…,Rn}，且每个对象Ri中含d个关键字如果对序列中任意两个对象Ri和Rj(1≤i

8、nificantDigitfirst)最低位优先LSD(LeastSignificantDigitfirst)1）最高位优先法通常是一个