第10章内排序-3（归并和基数排序）

归并排序是多次将相邻两个或两个以上的有序表合并成一个新有序表的排序方法。二路归并排序是多次将相邻两个的有序表合并成一个新有序表的排序方法，是最简单的归并排序。1、归并的思路10.5归并排序10.5归并排序1/38将两个位置相邻的元素有序子序列归并为一个元素的有序序列。有序序列R[low..high]有序子序列R[low..mid]有序子序列R[mid+1..high]R[low..high]2、二路归并排序算法

Merge()：一次二路归并，将两个相邻的有序子序列归并为一个有序序列10.5归并排序2/38voidMerge(RecTypeR[]，intlow，intmid，inthigh){RecType*R1;

inti=low，j=mid+1，k=0;

//k是R1的下标，i、j分别为第1、2段的下标

R1=(RecType*)malloc((high-low+1)*sizeof(RecType));

while(i<=mid&&j<=high)

{if(R[i].key<=R[j].key)

//将第1段中的元素放入R1中

{R1[k]=R[i];i++;k++;

}

else

//将第2段中的元素放入R1中

{R1[k]=R[j];j++;k++;

}}空间复杂度为O(high-low+1)10.5归并排序3/38while(i<=mid)

//将第1段余下部分复制到R1

{R1[k]=R[i];i++;k++;}while(j<=high)

//将第2段余下部分复制到R1

{R1[k]=R[j];j++;k++;}

for(k=0，i=low;i<=high;k++，i++) //将R1复制回R中

R[i]=R1[k];free(R1);}10.5归并排序4/38voidMergePass(RecTypeR[]，intlength，intn){inti;

for(i=0;i+2*length-1<n;i=i+2*length)//归并length长的两相邻子表

Merge(R，i，i+length-1，i+2*length-1);

MergePass()：一趟二路归并（段长度为length）0length-12length：满ii+length-1…<n2length：满10.5归并排序5/38if(i+length-1<n-1) //余下两个子表，后者长度小于length

Merge(R，i，i+length-1，n-1);//归并这两个子表}…ii+length-1lengthn-1<n-1表示存在第2个段10.5归并排序6/38

MergeSort()：二路归并排序算法voidMergeSort(RecTypeR[]，intn) {intlength;

for(length=1;length<n;length=2*length)

MergePass(R，length，n);}

log2n趟10.5归并排序7/38

【例9.7】设待排序的表有10个元素，其关键字分别为（6，8，7，9，0，1，3，2，4，5）。说明采用二路归并排序方法进行排序的过程。6

8

7

901

3

2

4

5初始：需要log210取上界即4趟68

79

01

23

45第1趟67890123

45第2趟01236789

45第3趟0123456789第4趟10.5归并排序8/386879012345678901236879013245012367890123456789更直观清楚的表示一颗归并树（倒过来）10.5归并排序9/38自底向上的过程底顶每一趟归并的时间复杂度为O(n)总共需进行

log2n

趟。二路归并排序的时间复杂度为Ο(nlog2n)。3、二路归并排序算法分析

时间复杂度分析10.5归并排序10/38所以空间复杂度为Ο(n)。每一次二路归并后临时空间都会释放。而最后的一次二路归需要全部元素参加归并：占用临时空间为全部元素个数n

空间复杂度分析4501236789012345678910.5归并排序11/38数据序列(5，4，15，10，3，2，9，6，8)是某排序方法第一趟后的结果，该排序算法可能是（）。A.冒泡排序 B.二路归并排序C.堆排序 D.简单选择排序10.5归并排序12/38第一趟：{5，4，15，10，3，2，9，6，8}相邻的两个元素都是递减的，符合二路归并排序特点。其他排序方法需要前面或者后面有一个元素归位：没有答案为B就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是（）。 A.堆排序<快速排序<归并排序

B.堆排序<归并排序<快速排序 C.堆排序>归并排序>快速排序

D.堆排序>快速排序>归并排序10.5归并排序13/38堆排序、快速排序、归并排序O(1)O(log2n)O(n)答案为DvoidMergeSortDC(RecTypeR[],intlow,inthigh)//对R[low..high]进行二路归并排序{intmid;if(low<high){mid=(low+high)/2;

MergeSortDC(R,low,mid);

MergeSortDC(R,mid+1,high);Merge(R,low,mid,high);}}voidMergeSort1(RecTypeR[],intn) //自顶向下的二路归并算法{

MergeSortDC(R,0,n-1);}自顶向下的递归二路归并排序10.5归并排序14/38239示例：百位十位个位r=101、基数排序的概念10.6基数排序基数r：对于二进制数r为2，对于十进制数r为10。元素R[j]的关键字R[j].key

kjd-1kjd-2…

kj1kj0d位数字或字符组成每一位的值都在0～r-1范围内，其中r称为基数一般地最高位最低位10.6基数排序15/38基数排序是一位一位地排序基数排序有两种：最低位优先（LSD）和最高位优先（MSD）。

2、基数排序的分类239百位十位个位最低位优先：从个位

百位最高位优先：从百位

个位选择哪种基数排序，需要根据数据的特点来定。例如，对整数序列递增排序，选择最低位优先，越重要的位越在后面排序。10.6基数排序16/38最低位优先排序过程如下：对i=0，1，…，d-1，依次做一次“分配”和“收集”（使用r个队列Q0，Q1，…，Qr-1。）。分配：开始时，把Q0，Q1，…，Qr-1各个队列置成空队列，然后依次考察线性表中的每一个结点aj（j=0，1，…，n-1），如果aj的关键字kji=k，就把aj放进Qk队列中。收集：按Q0，Q1，…，Qr-1顺序把各个队列中的结点首尾相接，得到新的结点序列，从而组成新的线性表。由于数据需要放入队列，又要从队列取出来，需要大量元素移动。所以排序数据和队列均采用链表存储更好。10.6基数排序17/38建立10个队列，f为队头，r为队尾

进行第1次分配：按个位进行第1次收集p→369→367→167→239→237→138→230→139f[0]←r[0]f[7]←r[7]f[8]←r[8]f[9]←r[9]→369→367→167→237→239→139→138→230p→230→367→167→237→138→369→239→139例如(

369，367，167，239，237，138，230，139)

基数排序第1趟排序完毕分配时是按一个一个元素进行的收集时是按一个一个队列进行的18/38

进行第2次分配：按拾位进行第2次收集f[3]←r[3]f[6]←r[6]→367→167→369→230p第2趟排序完毕→237→138→139→239p→230→367→167→237→138→369→239→139→230→237→138→139→239→367→167→36910.6基数排序19/38

进行第3次分配：按百位f[1]←r[1]f[2]←r[2]f[3]←r[3]→239→139→138→237→230→369→367p→230→237→138→139→239→367→167→369→167进行第3次收集p第3趟排序完毕→139→138→167→239→237→230→369→36710.6基数排序20/38基数排序是通过“分配”和“收集”过程来实现排序，不需要关键字的比较。结论已知的信息：基数，每个位的取值，这些值的大小确定！适合字符串排序适合多关键字排序：如有数学、语文成绩，排序方式：按数学成绩递减排序，数学成绩相同按语文成绩递减排序。10.6基数排序21/38#defineMAXE20 //线性表中最多元素个数#defineMAXR10 //基数的最大取值#defineMAXD8

//关键字位数的最大取值typedefstructnode{chardata[MAXD];

//元素的关键字串

structnode*next;}

RecType1;

//单链表中每个结点的类型a1pa2a3an∧…基数排序数据的存储结构：链表也可以采用数组实现3、基数排序算法（链表实现）10.6基数排序22/38voidRadixSort(RecType1*&p，intr，intd)//p为待排序序列链表指针，r为基数，d为关键字位数{RecType1*head[MAXR]，*tail[MAXR]，*t;//定义各链队的首尾指针

inti，j，k;

for(i=0;i<d;i--)

//从低位到高位做d趟排序

{for(j=0;j<r;j++)

//初始化各链队首、尾指针

head[j]=tail[j]=NULL;

while(p!=NULL)

//对于原链表中每个结点循环

{k=p->data[i]-'0';

//找第k个链队

if(head[k]==NULL)

//进行分配，即采用尾插法建立单链表

{head[k]=p;tail[k]=p;}

else

{tail[k]->next=p;tail[k]=p;}

p=p->next;

//取下一个待排序的结点

}分配10.6基数排序23/38p=NULL;

for(j=0;j<r;j++)//对于每一个链队循环进行收集

if(head[j]!=NULL){if(p==NULL)

{p=head[j];

t=tail[j];

}

else

{t->next=head[j];

t=tail[j];

}

}

t->next=NULL;

//最后一个结点的next域置NULL

}}排序完成后，p指向的是一个有序单链表。收集10.6基数排序24/38C/C++将数值转换为字符串：

123“321”210210应该从3

1，即低位到高位为了从3

1，应该高位到低位typedefstructnode{chardata[MAXD];

//元素的关键字串

structnode*next;}

RecType1;

//单链表中每个结点的类型注意：在整数排序时，这里data是由整数转换而来的数字字符数组10.6基数排序25/3810.6基数排序//获取数字的第k位（从个位开始，k=0表示个位）intgetDigit(intnum,intk){ for(inti=0;i<k;i++)

num/=10; returnnum%10;}typedefstructnode{intdata;

//元素的关键字

structnode*next;}

RecType1;

//单链表中每个结点的类型如果直接用int类型的data：则可以用以下算法求num的第k位数字：26/38

基数排序的时间复杂度为O(d(n+r))其中：

分配为O(n)

收集为O(r)（r为“基数”）

d为“分配-收集”的趟数4、基数排序算法分析

基数排序的空间复杂度为O(r)10.6基数排序27/38以下排序方法中，（）不需要进行关键字的比较。A.快速排序 B.归并排序

C.基数排序 D.堆排序示例10.6基数排序28/38排序方法时间复杂度空间复杂度稳定性平均情况最坏情况最好情况直接插入排序O(n2)O(n2)O(n)O(1)稳定折半插入排序O(n2)O(n2)O(nlog2n)O(1)稳定希尔排序O(n1.5)

O(n2)

O(n1.3)O(1)不稳定冒泡排序O(n2)O(n2)O(n)O(1)稳定快速排序O(nlog2n)O(n2)O(nlog2n)O(log2n)不稳定简单选择排序O(n2)O(n2)O(n2)O(1)不稳定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定二路归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定基数排序O(d(n+r))O(d(n+r))O(d(n+r))O(r)稳定10.7各种內排序的比较10.7各种内排序的比较29/38平方阶O(n2)：即简单排序方法，例如直接插入、简单选择和冒泡排序。线性对数阶O(nlog2n)：例如快速、堆和归并排序。线性阶O(n)：例如基数排序（假设r、d为常量）。1、按算法平均时间复杂度分类10.7各种内排序的比较30/382、按算法空间复杂度分类O(n)：归并排序，基数排序为O(r)。O(log2n)：快速排序。O(1)：其他排序方法。10.7各种内排序的比较31/383、按算法稳定性分类不稳定的：希尔排序、快速排序、堆排序、简单选择排序。稳定的：其他排序方法。10.7各种内排序的比较32/38

【例10.9】设线性表中每个元素有两个数据项k1和k2，现对线性表按以下规则进行排序：先看数据项k1，k1值小的在前，大的在后；在k1值相同的情况下，再看k2，k2值，小的在前，大的在后。满足这种要求的排序方法是（）。A.先按k1值进行直接插入排序，再按k2值进行简单选择排序B.先按k2值进行直接插入排序，再按k1值进行简单选择排序C.先按k1值进行简单选择排序，再按k2值进行直接插入排序D.先按k2值进行简单选择排序，再按k1值进行直接插入排序考虑1：排序数据项顺序：k1、k2还是k2、k1？越重要的数据项越在后面排序

应为k2、k1解10.7各种内排序的比较33/38标识k1k218090270903807247072k2直接插入排序标识k1k238072470721809027090标识k1k227090470721809038072k1简单选择排序相对次序改变相对次序改变考虑2：k2选择直接插入排序还是简单选择排序

？