归并排序-ppt课件

10.5归并排序基本思想将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列归并为一个有序序列。r[i]r[m]r[m+1]r[n]有序有序有序r[i]r[n]10.5归并排序如何进行两路归并？将两个有序表的元素进行比较，小者复制到目标表中。（5，24，35，74，222）（19，23，30）()5243574222()192330()ij()k5192324303574222两路归并动画演示ikjkjkikjk[s][m][t][m+1]10.5归并排序voidMerge(intr[],intr1[],ints,intm,intt){/***将有序列r[s..m]和r[m+1..t]两路归并为r1[]***/i=s;j=m+1;k=s;while(i=m&&j=t){//两表中元素比较if(r[i]=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}while(i=m)r1[k++]=r[i++];//前一个子序列剩下的while(j=t)r1[k++]=r[j++];//后一个子序列剩下的}10.5归并排序原理假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……如此重复，直至得到一个长度为n的有序序列为止。初始时：[49][38][65][97][76][13][27]初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]voidMsort(ElemSR[],ElemTR1[],ints,intt){/****将SR[s..t]进行归并排序为TR1[s..t]****/if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//将SR[s..t]分割Msort(SR,TR1,s,m);//递归地排序子序列SR[s..m]Msort(SR,TR2,m+1,t);//递归地排序子序列SR[m+1..t]Merge(TR2,TR1,s,m,t);//归并}}10.5归并排序10.5归并排序性能分析一趟归并操作是将r[1]~r[n]中相邻的长度为h的有序序列进行两两归并，这需要O(n)时间。整个归并排序需要进行log2n趟，因此，总的时间代价是O(nlog2n)。10.5归并排序性能分析算法在执行时，需要占用与原始记录序列同样数量的存储空间，因此空间复杂度为O(n)。10.5归并排序总结最好、最坏、平均时间复杂度均为O(nlogn);空间复杂度高，为O(n);是高效算法中唯一“稳定”的排序方法；较少用于内部排序，多用于外部排序。10.6基数排序基本思想基数排序是采用“分配”与“收集”的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。10.6基数排序多关键码排序问题以扑克牌排序为例。每张扑克牌有两个“关键码”：花色和面值。其有序关系为：花色：面值：2345678910JQKA10.6基数排序“花色”优先先分成4堆；然后，每堆再按“面值”排；最后，收成一堆。扑克牌“排序”为例10.6基数排序“面值”优先先分成13堆；每堆再按“花色”排；扑克牌“排序”为例10.6基数排序多关键码排序假设有n个记录……的序列{R1,R2,…，Rn}每个记录Ri中含有d个关键字(Ki0,Ki1,…,Kid-1)。则有序是指：对于序列中任意两个记录Ri和Rj(1≤ij≤n)都满足下列(词典)有序关系：(Ki0,Ki1,…,Kid-1)(Kj0,Kj1,…,Kjd-1)其中K0被称为“最高”位关键字，Kd-1被称为“最低”位关键字。10.6基数排序多关键码排序实现多关键码排序通常有两种方法：低位码优先LSD高位码优先MSD(3J899317)先按花色：8137J939再按面值：18379J3910.6.2链式基数排序对于单关键字，可以看成是由多个数位构成的多关键字；基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键码进行排序。例如：对下列这组关键字（每个关键字有3位）{209,386,768,185,247,606,230,834,539}10.6.2链式基数排序基本思想从关键字的最“低位”开始，将关键字分配到r(基数）个堆（桶）中；按桶的编号将关键字收集起来；然后，以“次低位”将关键字又分配到r个桶中；再收集，……，重复直到“最高位”为止，这时，以按关键字有序。例如：对下列这组关键字进行基数排序{209,386,768,185,247,606,230,834,539}基数为10分别按“个位”、“十位”、“百位”进行3趟分配与收集012345678910.6.2链式基数排序实现思想为了便于分配与收集，采用链表为存储结构r个桶用r个链式队列表示；收集的时候直接将队列的头尾指针连接实现；例初始状态：278109063930589184505269008083109589269278063930083184505008r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589第二趟收集：083184589063505269930r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269第一趟收集：例008063083109184269278505589930第三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589第二趟收集：例有序10.6.2链式基数排序//分配//收集基数排序算法10.6.2链式基数排序分配算法10.6.2链式基数排序收集算法10.6.2链式基数排序性能分析若每个关键码有d位，需要重复执行d趟“分配”与“收集”。而每趟对n个对象进行“分配”，对r个队列进行“收集”。总时间复杂度为O(d(n+r))。若基数r相同，对于数据个数较多而关键码位数较少的情况，使用链式基数排序较好。需要增加n+2r个附加链接指针。稳定的排序方法10.6内部排序方法的比较讨论对排序算法应该从以下几个方面综合考虑：⑴时间复杂性；⑵空间复杂性；⑶稳定性；⑷算法简单性；⑸待排序记录个数n的大小；⑹记录本身信息量的大小；⑺关键码的分布情况排序方法平均情况最好情况最坏情况直接插入排序O(n2)O(n)O(n2)希尔排序O(nlog2n)O(n1.3)O(n2)冒泡排序O(n2)O(n)O(n2)快速排序O(nlog2n)O(nlog2n)O(n2)简单选择排序O(n2)O(n2)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)归并排序O(nlog2n)O(nlog2n)O(nlog2n)时间复杂度排序方法辅助空间直接插入排序O(1)希尔排序O(1)冒泡排序O(1)快速排序O(log2n)~O(n)简单选择排序O(1)堆排序O(1)归并排序O(n)空间复杂度排序方法辅助空间直接插入排序稳定希尔排序不稳定冒泡排序稳定快速排序不稳定简单选择排序稳定堆排序不稳定归并排序稳定算法稳定性简单性一类是简单算法，包括直接插入排序、直接选择排序和冒泡排序，另一类是改进后的算法，包括希尔排序、堆排序、快速排序和归并排序，这些算法较复杂10.6内部排序方法的比较讨论10.6内部排序方法的比较讨论待排序记录个数比较n越小，采用简单排序方法越合适。n越大，采用改进的排序方法越合适。因为n越小，O(n2)同O(nlog2n)的差距越小，并且输入和调试简单算法比高效算法要容易10.6内部排序方法的比较讨论数据的信息量比较信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。排序方法最好情况最坏情况平均情况直接插入排序O(n)O(n2)O(n2)冒泡排序0O(n2)O(n2)直接选择排序0O(n)O(n)10.6内部排序方法的比较讨论数据的分布情况比较当待排序数据初始有序时，插入排序和冒泡排序能达到O(n)的时间复杂度；对于快速排序而言，这是最坏的情况，此时性能蜕化为O(n2)；选择排序、堆排序和归并排序的性能不受影响。结束，谢谢！