DS14-排序b-陈越主编-数据结构

第7章排序§7.5归并排序

归并排序

将两个已排序的子序列合并成一个有序序列。11324262152738AptrBptrCptrCptr

T

(N)=O(

)，

N

是元素个数.N12

S

(N)=O(

)。N

方法是稳定的。二路归并。也可以使用多路归并。voidMerge(ElementTypeA[],ElementTypeTmpA[],intLeft,intMid,intRight){/*将有序的A[Left]~A[Mid-1]和A[Mid]~A[Right]归并成一个有序序列*/intTp,LeftEnd,i;

Tp=Left;/*有序序列的起始位置*/LeftEnd=Mid–1;/*左边序列终止的位置*/while((Left<LeftEnd)&&(Mid<Right))

if(A[Left]<=A[Mid])TmpA[Tp++]=A[Left++];/*将左边元素复制到TmpA*/

elseTmpA[Tp++]=A[Mid++];/*将右边元素复制到TmpA*/while(Left<=LeftEnd)/*如果左边有元素剩下而右边已经结束*/TmpA[Tp++]=A[Left++];/*将左边剩余元素复制到TmpA*/while(Mid<=Right)/*如果右边有元素剩下而左边已经结束*/TmpA[Tp++]=A[Mid++];/*将右边剩余元素复制到TmpA*/for(i=Right-Left;i>=0;i--,Right--)A[Right]=TmpA[Right];/*将有序的TmpA[]复制回A[]*/}第7章排序§7.5归并排序voidMSort(ElementTypeA[],ElementTypeTmpA[],

intLeft,intRight){intCenter;/*递归地将A[Left]~A[Right]排序*/

if(Left<Right){/*如果还有元素要排序*/ Center=(Left+Right)/2; MSort(A,TmpA,Left,Center);/*递归排左半边T(N/2)*/ MSort(A,TmpA,Center+1,Right);/*递归排右半边T(N/2)*/ Merge(A,TmpA,Left,Center+1,Right);/*归并，O(N)*/}}voidMergesort(ElementTypeA[],intN){ElementType*TmpArray;/*需要O(N)辅助空间*/TmpArray=malloc(N*sizeof(ElementType));MSort(A,TmpArray,0,N-1);free(TmpA);}如果TmpA定义成Merge的局部变量，那么每次调用Merge都需要开辟不同的空间,那么S(N)=O()NlogN第7章排序§7.5归并排序

时间复杂性分析：T

(1

)=1T

(N)=2T(N/2

)+O(N)=2k

T(N/2k

)+k*O(N)=N*T(1

)+logN*O(N)=O(N+NlogN)

非递归的算法思想:A0123…………n4n3n2n1…………………………注意:

归并排序需要线性的额外存储,并且经常复制临时数组导致效率降低。

它很少用于内部排序，然而在外部排序中非常常用。第7章排序§7.5归并排序

桶排序〖例〗假设有N个学生，每个人的成绩分布在0到100(令M=101种可能的成绩).如何在线性的时间内按照成绩给他们排序?count0110088算法思想：{

初始化链表头数组count[];

while(读一个学生的成绩)

把它插入链表count[stdnt.grade];

for(i=0;i<M;i++){

if(count[i])

输出链表count[i];}}T(N,M)=O(M+N)M>>N

将会怎样?第7章排序§7.6基数排序

“基数排序

(RadixSort)”是“桶排序

(BucketSort)”的推广。

基数排序

基数排序：一般用于多关键字的排序第7章排序§7.6基数排序〖例〗

一叠牌的排序要基于两个关键字。第一关键字[花色]<

<

<第一关键字[面值]2<3<4<5<6<7<8<9<10<J<Q<K<A排序结果应该是:2...A2...A2...A2...A

基数排序的方法一般采用“主位优先法”(MostSignificantDigitFirst,MSD)或者“次位优先法”(LeastSignificantDigitFirst,LSD)相当于“分治法”“分配-收集”法

主位优先法(MSD)排序先排花色:比方,建立4个花色的“桶”3

3

5

5

A

A

4

4

再排面值:每个桶分别独立排序(可以采用以前介绍的任何排序方法)

第7章排序§7.6基数排序先排面值:建立13个面值的“桶”，把牌放入相应的桶中〔这叫“分配”〕；2

2

3

3

4

4

5

5

A

A

...

依次“收集”它们成为一叠牌；A

A

3

3

2

2

再排花色:建立4个桶进行再“分配”；

次位优先法(LSD)排序④

再次“收集”它们成为一叠牌即告完成。第7章排序§7.6基数排序还不赶紧拿一副牌出来试试？〖例〗给定

N=10个整数，范围介于0到999(M

=1000)之间。是否可以在线性的时间内把它们排序?

单关键字的基数排序输入:64,8,216,512,27,729,0,1,343,1250桶：123456789〔3位数可以看成个3关键字，再按“次位优先法”排序〕0轮次1151234364125216278729轮次20151234364125216278729轮次30185122161252772934364输出:0,1,8,27,64,125,216,343,512,729时间复杂性：T=O(D(N+R))其中D是轮次,N

是元素个数,R

是桶的数量.按“主位优先法”排序将会怎样?第7章排序§7.6基数排序空间复杂性：S=O(N+R),N

是元素个数,R

是桶的数量.稳定性：稳定用链式储存更便于分配与收集？typedefstructNode*PtrToNode;typedefPtrToNodeList;structNode{

intKey[MaxDigit];/*MaxDigit是关键字个数,Key可以定义成char类型数组*/PtrToNodeNext;};ListRadixSort(ListA)/*基数排序*/{ListBucket[Radix]；/*建立Radix个桶*/ListRear[Radix];/*需要记录每个桶链表的尾元素位置*/inti,j,Digit;for(i=MaxDigit-1;i>=0;i--){/*从最次位关键字开始*/

for(j=0;j<Radix;j++)Bucket[j]=Rear[j]=NULL;/*初始化*/

while(A){/*将关键字逐一分配到桶*/Digit=A->Key[i];/*取出当前关键字位*/

if(!Bucket[Digit])/*若对应的桶是空的*/Bucket[Digit]=A;/*放入空桶*/

elseRear[Digit]->Next=A;/*否则放入桶尾*/Rear[Digit]=A;/*更新尾指针*/A=A->Next;}/*结束while分配过程*/

for(j=Radix-1;i>=0;j--){/*将所有桶中元素收集串联*/

if(Bucket[j]){Rear[j]->Next=A;A=Bucket[j];}}/*结束for收集过程*/}returnA;}第7章排序§7.7外部排序*

外部排序*(ExternalSort)

内部排序和外部排序分两个步实施：(a)分段内排序(b)归并〔二路或多路〕磁盘内存有序有序磁盘内存有序有序周转盘输入块输出块

要提高外排的效率，关键要解决以下4个问题：

如何减少归并轮数；

如何有效安排内存中的输入、输出块，使得机器的并行处理能力被最大限度地利用；

如何有效生成归并段；

如何将归并段进行有效归并。第7章排序§7.8排序总结排序方法平均时间复杂度最坏情况下时间复杂度额外空间复杂度稳定性简单选择排序O(N2)O(N2)O(1)不稳定直接插入排序O(N2)O(N2)O(1)稳定冒泡排序O(N2)O(N2)O(1)稳