数据结构 第 章 排序

数据结构第章排序第1页，共45页，2023年，2月20日，星期六教学内容1、插入排序（直接插入排序、折半插入排序、希尔排序）；2、交换排序（起泡排序、快速排序）；3、选择排序（直接选择排序、堆排序）；4、归并排序；5、基数排序；第2页，共45页，2023年，2月20日，星期六

排序：将数据元素的一个任意序列，重新排列成一个按关键字有序的序列。10.1概述例：将关键字序列：52,49,80,36,14,58,61,23调整为：14,23,36,49,52,58,61,80一般情况下，假设含n个记录的序列为{R1,R2,…,Rn

}，其相应的关键字序列为{K1,K2,…,Kn

}R1,R2,R3,R4,R5,R6,R7,R8

K1,K2,K3,K4,K5,K6,K7,K8

这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1≤Kp2≤…≤KpnKp1≤Kp2≤Kp3≤Kp4≤Kp5≤Kp6≤Kp7≤Kp8按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…,Rpn

}的操作称作排序。Rp1,Rp2,Rp3,Rp4,Rp5,Rp6,Rp7,Rp8

第3页，共45页，2023年，2月20日，星期六若Ki

为记录Ri

的主关键字，则排序结果惟一。若Ki

为记录Ri

的次关键字，则排序结果可以不惟一（因为会有相同的关键字）。设Ki=Kj

(1≤i≤n,1≤j≤n,i≠j)，且在排序前的序列中Ri

领先于Rj（即i<j）。若在排序后的序列中Ri

仍领先于Rj，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。例：设排序前的关键字序列为：52,49,80,36,14,58,36,23

若排序后的关键字序列为：14,23,36,36,49,52,58,80，则排序方法是稳定的。若排序后的关键字序列为：14,23,36,36,49,52,58,80，则排序方法是不稳定的。第4页，共45页，2023年，2月20日，星期六排序方法分类：内部排序：待排序记录放在内存，排序过程不需访问外存；

外部排序：排序过程需要访问外存。

1)、插入排序：直接插入排序、折半插入排序、希尔排序

2)、交换排序：冒泡排序、快速排序

3)、选择排序：简单选择排序、堆排序

4)、归并排序：2-路归并排序

5)、基数排序按待排序记录所在位置按排序依据原则按排序所需工作量简单的排序方法：T(n)=O(n²)

先进的排序方法：T(n)=O(nlogn)

基数排序：T(n)=O(d(n+rd))第5页，共45页，2023年，2月20日，星期六10.2插入排序10.2.1直接插入排序初始状态4938659776132749

R0R1R2R3

R4R5R6R7

R8i=2i=33849659776132749

i=43849659776132749

i=5384965769713274976i=6384965769713274913i=7384965769713274927i=83849657697132749494938659776132749

383849387趟排序1趟排序2趟排序voidInsertSort(SqList&L){//对顺序表L作直接插入排序。

for(i=2;i<=L.length;++i)if(L.r[i].key<L.r[i-1].key){}}//InsertSortL.r[0]=L.r[i];//复制为监视哨L.r[i]=L.r[i-1];for(j=i-2;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置排序过程：先将序列中第

1

个记录看成是一个有序子序列，

然后从第

2

个记录开始，逐个进行插入，直至整个序列有序。

第6页，共45页，2023年，2月20日，星期六比较次数和移动次数均约为：T(n)=O(n²)算法评价时间复杂度：比较次数：移动次数：0最好的情况：待排序记录按关键字从小到大排列（正序）比较次数：移动次数：最坏的情况：待排序记录按关键字从大到小排列（逆序）

一般情况：待排序记录是随机的，取平均值。

空间复杂度：S(n)=O(1)直接插入排序是稳定排序54321▲1第7页，共45页，2023年，2月20日，星期六10.2.2其他插入排序1、折半插入排序：用折半查找方法确定插入位置的排序。voidBInsertSort(SqList&L){

for(i=2;i<=L.length;++i){L.r[0]=L.r[i];low=1;high=i-1;

while(low<=high){m=(low+high)/2;//折半

if(L.r[0].key<L.r[m].key)high=m-1;elselow=m+1;}//while

for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//记录后移

L.r[high+1]=L.r[0];//插入

}//for}//BInsertSorti=1(30)1370853942620i=76(6133039427085)20…i=820(6133039427085)20lhmmi=820(6133039427085)20lhi=820(6133039427085)20lhi=820(613203039427085)i=820(6133039427085)20lhmT(n)=O(n²)时间复杂度：空间复杂度：S(n)=O(1)折半插入排序是稳定排序仅减少了比较次数，移动次数不变。第8页，共45页，2023年，2月20日，星期六第二趟希尔排序第三趟分组，设d3=110.2.3希尔排序（缩小增量排序）

基本思想：对待排序列先作“宏观”调整，再作“微观”调整。排序过程：先取一个正整数d1<n，把所有相隔

d1

的记录放

在一组内，组内进行直接插入排序；然后取

d2<d1，重复上述分

组和排序操作；直至

di=1，即所有记录放进一个组中排序为止。

其中

di

称为增量。例：49386597761327495504第一趟希尔排序1327495504493865977613044938274955659776第三趟希尔排序第一趟分组，设d1=549

38

659776

13

27

495504

13

27

49

55

044938659776

第二趟分组，设d2=304132738494955657697第9页，共45页，2023年，2月20日，星期六希尔排序特点：分组不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列。增量序列取法希尔最早提出的选法是di=n/2，di+1=di/2。克努特(Knuth)提出的选法是di+1=di/3。还有其他不同的取法。

如何选择增量序列以产生最好的排序效果，至今仍没有从数学上得到解决。

1)、没有除1以外的公因子；

2)、最后一个增量值必须为1。希尔排序可提高排序速度1)、记录跳跃式前移，在进行最后一趟排序时，已基本有序。

2)、分组后n

值减小，n2更小，而

T(n)=O(n2)，所以

T(n)从

总体上看是减小了。

▲2第10页，共45页，2023年，2月20日，星期六10.3交换排序

1、冒泡排序排序过程1、比较第一个记录与第二个记录，若关键字为逆序则交换；然

后比较第二个记录与第三个记录；

依次类推，直至第

n-1个记录和第

n

个记录比较为止——第一趟冒泡

排序，结果关键字最大的记录被安

置在最后一个记录上。

2、对前

n-1个记录进行第二

趟冒泡排序，结果使关键字次大的

记录被安置在第

n-1个记录位置。

3、重复上述过程，直到

“在

一趟排序过程中没有进行过交换记

录的操作”

为止。

初始关键字4938659776132749

第一趟排序4938499776979713979727979749

97

38496576132749

97384965132749

76第二趟排序3849132749

65第三趟排序3813274949

第四趟排序13273849第五趟排序132738第六趟排序

for(j=1;j<n

;j++)if(r[j+1]<r[j])r[j]r[j+1];

for(j=1;j<n-1;j++)if(r[j+1]<r[j])r[j]r[j+1];for(i=n;i>1;i--)i

;{

}while(i>1){

}//whilei=n;i=k;VoidBubbleSort(SqList&L){}

冒泡排序算法

初始关键字4938659776132749

k=j;//交换的位置k=1;第11页，共45页，2023年，2月20日，星期六算法评价时间复杂度：最好情况（正序）比较次数：n-1移动次数：0

T(n)=O(n)最坏情况（逆序）比较次数：移动次数：

T(n)=O(n2)空间复杂度：S(n)=O(1)稳定性：稳定排序第12页，共45页，2023年，2月20日，星期六一般取第一个记录

基本思想：任选一个记录，以它的关键字作为“枢轴”，凡关键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录均移至枢轴之后。

2、一趟快速排序（一次划分）lowhigh设R[s]=52为枢轴。例：52

52

49

80

36

14

58

61

97

23

75st附设两个指针low和high，从high所指位置起向前搜索找到第一个关键字小于枢轴的关键字的记录与枢轴记录交换，然后从low所指位置起向后搜索找到第一个关键字大于枢轴的关键字的记录与枢轴记录交换，重复这两步直至low=high为止。high23lowlow80highhighhighhigh14lowlow52第13页，共45页，2023年，2月20日，星期六intPartition(SqList&L,intlow,inthigh){pivotkey=L.r[low].key;//用子表的第一个记录作枢轴记录

while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;

L.r[low]←→L.r[high];//将比枢轴小的记录交换到低端

while(low<high&&L.r[low].key<=pivotkey)++low;

L.r[low]←→L.r[high];//将比枢轴大的记录交换到高端

}//whilereturnlow;//返回枢轴所在位置}//PartitionL.r[0]=L.r[low];L.r[low]=L.r[high];

L.r[high]=L.r[0];L.r[0]=L.r[low];L.r[low]=L.r[high];L.r[high]=L.r[0];

L.r[0]=L.r[low];L.r[low]=L.r[0];L.r[low]=L.r[high];//将比枢轴小的记录移到低端L.r[high]=L.r[low];//将比枢轴大的记录移到高端▲3第14页，共45页，2023年，2月20日，星期六快速排序过程

3、快速排序首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行一趟快速排序。无序的记录序列无序记录子序列(1)无序子序列(2)枢轴一次划分分别进行一趟快速排序有序的记录序列…第15页，共45页，2023年，2月20日，星期六voidQSort(SqList&L,intlow,inthigh){//对顺序表L中的子序列L.r[low..high]进行快速排序

if(low<high){//长度大于1

}}//QSortpivotloc=Partition(L,low,high);//对L.r[low..high]进行一次划分QSort(L,low,pivotloc-1);//对低子序列递归排序，pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子序列递归排序第一次调用函数Qsort时，待排序记录序列的上、下界分别为1和L.length。voidQuickSort(SqList&L){//对顺序表进行快速排序

QSort(L,1,L.length);}//QuickSort第16页，共45页，2023年，2月20日，星期六快速排序实质上是对冒泡排序的一种改进，它的效率与冒泡排序相比有很大地提高。在冒泡排序过程中是对相邻两个记录进行关键字比较和互换的，这样每次交换记录后，只能改变一对逆序记录，而快速排序则从待排序记录的两端开始进行比较和交换，并逐渐向中间靠拢，每经过一次交换，有可能改变几对逆序记录，从而加快了排序速度。到目前为止快速排序是平均速度最大的一种排序方法，但当原始记录排列基本有序或基本逆序时，每一趟的基准记录有可能只将其余记录分成一部分，这样就降低了时间效率，所以快速排序适用于原始记录排列杂乱无章的情况。快速排序是一种不稳定的排序，在递归调用时需要占据一定的存储空间用来保存每一层递归调用时的必要信息。第17页，共45页，2023年，2月20日，星期六10.4选择排序10.4.1简单选择排序排序过程：首先通过n–1次关键字比较，从

n

个记录中找出关键字最小的

记录，将它与第一个记录交换。

再通过

n–2次比较，从剩余的

n–1个记录中找出关键字次小的

记录，将它与第二个记录交换。

重复上述操作，共进行

n–1趟排序后，排序结束。

第18页，共45页，2023年，2月20日，星期六j++if(L.r[j].key<L.r[k].key)k=j;j=i+1;for(i=1;i<L.length;++i){}例：初始：[49386597761327]jjjjjjki=11349一趟：13[386597764927]i=2二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序结束：六趟：13273849657697kk=i;kfor(j=i+1;j<=n;j++)if(L.r[j].key<L.r[k].key)k=j;if(i!=k)L.r[i]←→L.r[j];//与第i

个记录交换i=6voidSelectSort(SqList&L){//对顺序表L作简单选择排序。}//SelectSorti=3i=4i=5比较次数n-1n-2n-6比较次数：移动次数：正序：最小值为0；最大值为3(n-1)。前n–1个为正序，第n

个记录的关键字最小。时间复杂度：O(n2)空间复杂度：O(1)不稳定第19页，共45页，2023年，2月20日，星期六锦标赛排序

前提：若乙胜丙，甲胜乙，则认为甲必能胜丙。ZhaoChaLiuBaoDiaoYangXueWangChaBaoDiaoWangBaoDiaoBao

LiuChaChaBaoCha

Zhao

LiuDiaoDiao

Yang

Wang

Liu

Liu

Zhao

Wang

Wang

Xue

Xue

Xue

Xue

Yang

Yang

Yang

Zhao

选出冠军的比较次数为22+21+20=23-1=n-1。选出亚军的比较次数为3，即log2n

次。其后的n2个人的名次均如此产生，所以对于n

个参赛选手来说，即对n

个记录进行锦标赛排序，总的关键字比较次数至多为(n1)log2nn1，故时间复杂度为：O(nlog2n)。此法除排序结果所需的n

个单元外，尚需n-1个辅助单元。▲4第20页，共45页，2023年，2月20日，星期六10.4.2树形选择排序

思想：首先对n

个记录的关键字进行两两比较，然后在其中

n/2

个较小者之间再进行两两比较，直到选出最小关键字的记录为止。可以用一棵有n

个叶子结点的完全二叉树表示。

38

13

13

13

38

65

27

13

38

49

65

97

76

27

4913

76

27

27

27

49

49

3838

49

49

4949

65

4949

76

6565

97

97

76

9776971327384949657697

时间复杂度：由于含有n

个叶子结点的完全二叉树的深度为log2n+1，则在树形选择排序中中，除了最小关键字外，每选择一个次小关键字仅需进行log2n

次比较，故时间复杂度为

O(nlog2n)。缺点：

1、与“”的比较多余；

2、辅助空间使用多。第21页，共45页，2023年，2月20日，星期六10.4.3堆排序

堆的定义：n

个元素的序列

(k1,k2,…,kn)，当且仅当满足下

列关系时，称之为堆。

或(i=1,2,…,n/2)ki

k2i

kik2i+1

ki

k2ikik2i+1

小顶堆大顶堆小根堆正堆大根堆逆堆第22页，共45页，2023年，2月20日，星期六例1：(96,83,27,38,11,09)例2：(13,38,27,49,76,65,49,97)9627091138831327384965764997可将堆序列看成完全二叉树，则：

k2i是ki的左孩子；k2i+1是ki的右孩子。所有非终端结点的值均不大（小）于其左右孩子结点的值。堆顶元素必为序列中n

个元素的最小值或最大值。第23页，共45页，2023年，2月20日，星期六堆排序：堆排序需解决的两个问题：

1、如何由一个无序序列建成一个堆？2、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？将无序序列建成一个堆，得到关键字最小（大）的记录；输出堆顶的最小（大）值后，将剩余的n-1个元

素重又建成一个堆，则可得到

n个元素的次小值；如此

重复执行，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列，这个过程叫堆排序。第24页，共45页，2023年，2月20日，星期六第二个问题解决方法——筛选：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。132738496576499797972797499738979749656549764976979765762765493849971376对深度为k

的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)。第25页，共45页，2023年，2月20日，星期六817364279812第一个问题解决方法：从无序序列的第n/2个元素（即无序序列对应的完全二叉

树的最后一个内部结点）起，至第一个元素止，进行反复筛选。

建堆是一个从下往上进行“筛选”的过程。例:排序之前的关键字序列为：40554936123673499881984940现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。817355第26页，共45页，2023年，2月20日，星期六堆排序的时间复杂度和空间复杂度：对深度为k

的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；3.调整“堆顶”n-1次，总共进行的关键字比较的次数不超过

2(log2(n-1)+log2(n-2)+…+log22)<2n(log2n)因此，堆排序的时间复杂度为O(nlogn)，与简单选择排序

O(n2)相比时间效率提高了很多。2.对

n

个关键字，建成深度为h(=log2n+1)的堆，所需进行的

关键字比较的次数至多4n；

空间复杂度：S(n)=O(1)堆排序是一种速度快且省空间的排序方法。不稳定。▲5第27页，共45页，2023年，2月20日，星期六10.5归并排序

归并：将两个或两个以上的有序表组合成一个新的有序表。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录有序的序列。初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]看成是n

个有序的子序列（长度为1），然后两两归并。得到n/2个长度为2或1的有序子序列。空间复杂度为：O(n)。时间复杂度为：O(nlog2n)。稳定。第28页，共45页，2023年，2月20日，星期六10.6基数排序基数排序是一种基于多关键字排序的思想，是将单关键字按基数分成“多关键字”进行排序的方法。10.6.1多关键字的排序例：将右表所示的学生成绩单按数学成绩的等级由高到低排序，数学成绩相同的学生再按英语成绩的高低等级排序。学号数学英语其它

101

B

C…

102

A

B…

103

C

D…

104

B

B…

105

A

A…

106

D

B…

107

E

A…

108

C

B…105AA102AB104BB101BC108CB103CD106DB107EA特点：每个记录最终的位置由两个关键字k1k2决定。

第二关键字K2

第一关键字K1我们将它称之为复合关键字，即多关键字排序是按照复合关键字的大小排序。第29页，共45页，2023年，2月20日，星期六例：扑克牌中52张牌，可按花色和面值分成两个“关键字”，其大小关系为：花色：

<<

<

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A若对扑克牌按花色、面值进行升序排序，得到如下序列：

2,3,...,A,2,3,...,A,2,3,...,A,2,3,...,A即两张牌，若花色不同，不论面值怎样，花色低的那张牌小于花色高的，只有在同花色情况下，大小关系才由面值的大小确定。这也是按照复合关键字的大小排序，即：多关键字排序。第30页，共45页，2023年，2月20日，星期六多关键字排序的方法：

n

个记录的序列{R1,R2,…,Rn}对关键字(Ki0,Ki1,…,Kid-1)有序是指：对于序列中任意两个记录Ri

和Rj

(1≤i<j≤n)都满足下列（词典）有序关系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)其中：K0

被称为最主位关键字，

Kd-1

被称为最次位关键字。多关键字排序按照从最主位关键字到最次位关键字或从最次位关键字到最主位关键字的顺序逐次排序，分两种方法：

最高位优先法，简称MSD法：先按k

0排序分组，同一组中记录，关键字k

0相等，再对各组按k1

排序分成子组，之后，对后面的关键字继续这样的排序分组，直到按最次位关键字kd

对各子组排序后，再将各组连接起来，便得到一个有序序列。第31页，共45页，2023年，2月20日，星期六例：先将学生记录按英语等级由高到低分成A、B、C、D、E五个组：关键字类别ABCDE各组成员AAABBCCDEABBCBDB学号数学英语其它

101

B

C…

102

A

B…

103

C

D…

104

B

B…

105

A

A…

106

D

B…

107

E

A…

108

C

B…

最低位优先法，简称LSD法：先从kd-1

开始排序，再对kd-2

进行排序，依次重复，直到对k

0

排序后便得到一个有序序列。然后按从左向右，从上向下的顺序将它们收集起来得到关键字序列：AA，EA，AB，BB，CB，DB，BC，CD第32页，共45页，2023年，2月20日，星期六再按数学成绩由高到低分成A、B、C、D、E五个组：关键字类别ABCDE各组成员AAABBCCDEABBCBDB关键字类别ABCDE各组成员AABBCBDBEAABBCCD可以看出，这个关键字序列已经是有序的了。AA，AB，BB，BC，CB，CD，DB，EA对每个关键字都是将整个序列按关键字分组，然后按顺序收集，显然LSD法，操作比较简单。按从上向下，从左向右的顺序将其收集起来得到关键字序列：AA，EA，AB，BB，CB，DB，BC，CD按从上向下，从左向右的顺序将其收集起来得到关键字序列：第33页，共45页，2023年，2月20日，星期六MSD与LSD的不同特点

必须将序列逐层分

割成若干子序列，

然后对各子序列分

别排序。

不必分成子序列，

对每个关键字都是

整个序列参加排序；

通过若干次分配与

收集实现排序。

LSDMSD第34页，共45页，2023年，2月20日，星期六基数排序：是借助于多关键字排序思想进行排序的一种排序方法。该方法将排序关键字K

看作是由多个关键字组成的组合关键字，即：K=k0k1…kd-1。每个关键字ki

表示关键字的一位，其中k0

为最高位，kd-1

为最低位，d

为关键字的位数。例：对于关键字序列(101,203,567,231,478,352)，可以将每个关键字

K

看成由三个单关键字组成，即K=k1k2k3，每个关键字的取值范围为0≤ki≤9，所以每个关键字可取值的数目为10。通常将关键字取值的数目称为基数，用r表示，在本例中r=10。对于关键字序列（AB,BD,ED）可以将每个关键字看成是由二个单字母关键字组成的复合关键字，并且每个关键字的取值范围为“A~Z”，所以关键字的基数r=26。第35页，共45页，2023年，2月20日，星期六基数排序可用多关键字的LSD方法排序，即对待排序的记录序列按复合关键字从低位到高位的顺序交替地进行“分组”、“收集”，最终得到有序的记录序列。在此我们将一次“分组”、“收集”称为一趟。对于由d

位关键字组成的复合关键字，需要经过d

趟的“分配”与“收集”。因此，若d

值较大，基数排序的时间效率就会随之降低。▲6第36页，共45页，2023年，2月20日，星期六

在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：10.6.2链式基数排序1、以静态链表存储待排记录，并令表头指针指向第一个记录；2、“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；3、“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表；4、对每个关键字位均重复2和3两步。第37页，共45页，2023年，2月20日，星期六278109063930589184505269008083例：109589269278063930083184505008e[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]一趟分配930063