数据结构排序

第十章排序第十章排序第十章排序

10.1概述10.2插入排序10.3交换排序10.4选择排序10.5归并排序

10.1概述学习要点理解排序的定义和各种排序方法的特点；了解各种方法的排序过程及其依据的原则；理解“稳定”或“不稳定”的含义；10.1概述1排序定义

将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序。假设含n个记录的序列为：{R1

R2R3

…Rn

}其相应的关键字为：{K1,K2,K3

…Kn}需确定1，2，…，n的一种排列p1,p2,…,pn，使其相应的关键字满足如下的非递减（或非递增）关系

Kp1<=Kp2<=…<=Kpn即使（10-1）的序列成为一个按关键字有序的序列

{Rp1，Rp2，…，Rpn}这样一种操作称为排序。10.1概述

2稳性排序：

在待排记录序列中，任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。例设49,38,65,97,76,13,27,49是待排序列排序后:13,27,38,49,49,65,76,97——稳定排序后:13,27,38,49,49,65,76,97——不稳定10.1概述3分类

按记录的存放位置分类有内排序：待排记录放在内存

外排序：待排记录放在外存·按排序原则分类（内排序）

插入排序

交换排序

选择排序

归并排序

基数排序按排序所需工作量简单的排序方法：T(n)=O(n²)

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

基数排序：T(n)=O(d*n)

排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置10.1概述4存储方式

待排序的记录序列通常有下列三种存储方法：

1）顺序表

2）静态链表：在排序过程，只需修改指针，不需要移动记录(表排序)；

3）待排记录本身有放在连续单元中，同时另建一索引表——用于存放各记录存贮位置；排序时不移过记录本身，而移动索引表中的记录“地址”，在排序结束后再按地址调整记录的存贮位置（地址排序）。10.1概述5约定在本章中1)为简洁起见，对待排记录只写出其关键字序列如对待排记录（(09,10),(06,10.5),(033,9.8),(051,10))只写出其关键字序列（10，10.5，9.8，10）2）将按关键字递增的顺序排序10.1概述3)待排序记录用顺序表存储，且关键字均为整数顺序表类型说明#defineMAXSIZE20//一个用作示例的小顺序表的最大长度typedef

int

KeyType;//定义关键字类型为整数类型typedef

struct{KeyTypekey;//关键字项InfoType

otherinfo;//其它数据项}RedType;//记录类型typedef

struct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元Intlength;//顺序表长度}SqList;//顺序表类型10.2插入排序

1、直接插入排序

基本思想

将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

排序过程：

整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。

例4938659776132749i=238(3849)659776132749

i=365(384965)9776132749

i=497(38496597)76132749i=576(3849657697)132749i=613(133849657697)2749i=1()i=7(133849657697)274927jjjjjj977665493827

(13273849657697)49排序结果：i=849(13273849

49657697)

1234567810.2插入排序voidInsertSort(SqList&L){//对顺序表L作直接插入排序。for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){//若L.r[i].key<L.r[i-1].key，需将L.r[i]插入有序子表，L.r[0]=L.r[i];//L.r[i]复制为哨兵

for(j=i-1;LT(L.r(0).key,L.r[j].key);--j)//从后向前查找子表L.r[j+1]=L.r[j];//若L.r[i].key<L.r[j].key，L.r[j]记录后移L.r[j+1]=L.r[0];//插入到正确位置}}//InsertSort10.2插入排序算法中引入附加记录R[0]有两个作用：其一是进入查找循环之前，它保存了R[i]的副本，使得不至于因记录的后移而丢失R[i]中的内容；其二是在while循环“监视”下标变量j是否越界，一旦越界（即j<1），R[0]自动控制while循环的结束，从而避免了在while循环内的每一次都要检测j是否越界（即省略了循环条件j>=1）。因此，我们把R[0]称为“监视哨”。10.2插入排序

性能分析：

基本操作

比较元素：比较、移动元素次数均取决于插入位置

移动元素

①处理第i个记录时待排序列递增（正向）有序时，比较元素次数最少：1次

待排序列递减（逆向）有序时，比较元素次数最多：i

次一般待排序列，平均比较元素次数：(i+1)/2②对n个记录待排序列,直接插入排序

待排序列正向有序时，比较元素次数最少：n-1次待排序列逆向有序时，比较元素次数最多：(n+2)(n-1)/2次一般待排序列，平均比较元素次数大约为：n2/4

类似可分析移动元素次数10.2插入排序时间复杂度待排序列正向有序时：0（n）

待排序列逆向有序时：0（n2）

一般待排序列：0（n2）特点：1)算法简单

2)时间复杂度为O（n2）3）初始序列基本（正向）有序时，时间复杂度为O（n）4）稳定排序:关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。

该方法适用于记录基本（正向）有序或n较少的情况

10.2插入排序voidInsert_Sort1(SqList&L)//监视哨设在高下标端的插入排序算法

{

k=L.length;

for(i=k-1;i;--i)//从后向前逐个插入排序

if(L.r[i].key>L.r[i+1].key)

{

L.r[k+1].key=L.r[i].key;//监视哨

for(j=i+1;L.r[j].key>L.r[i].key;++j)

L.r[j-1].key=L.r[j].key;//前移

L.r[j-1].key=L.r[k+1].key;//插入

}

}//Insert_Sort12.折半插入排序排序过程：用折半查找方法确定插入位置的排序叫~例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)10.2插入排序4、希尔排序

直接插入排序法简单，适用于记录较少，或待排记录基本（正向）有序的情况。

基于直接插入排序上是述特点，希尔提出了另一种插入排序算法。1．

基本思想：

1）

将待排序记分为若干组，在各组内分别进行直接插入排序；

2）

作若干次使待排记录基本有序；

3）

对全部记录进行一次顺序插入排序；分组方法：选定一增量d，将间隔为d的记录作为一组。排序过程：先取一个正整数d1<n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。取d3=1三趟分组：134

485527

4938659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d1=5一趟分组：49

38

65

97

76

13

27

48

55

4取d2=3二趟分组：13

27

48

55

4

49

38

65

97

76算法描述Ch8_3.c例49

38659776

13

27

48554#defineT3intd[]={5,3,1};ji49133827一趟排序：1327

48

55

44938659776jiji274jiji55ji38jijiji二趟排序：13

4

48

38

27

49

55

65

97

76jiji6548ji9755ji764希尔排序特点子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列希尔排序可提高排序速度，因为分组后n值减小，n²更小，而T(n)=O(n²),所以T(n)从总体上看是减小了关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序增量序列取法无除1以外的公因子最后一个增量值必须为110.2插入排序特点

1）时间复杂度，取决于增量序列的选择，选择的好，效率优于直接插入排序，其时间复杂度为0（nlog2n）

2）不稳定排序方法

3）适用于n较大情况

10.3交换排序一、基本思想：将待排记录中两两记录关键字进行比较，若逆序而交换位置。例：4938659776132749若按关键字递增的顺序排序则4938为逆序

不同的比较顺序就得到不同的交换排序方法二起泡排序：顺序比较相邻的两记录的关键字，若逆序而交换位置三快速排序

1

基本思想

1）

选定一记录R，将所有其他记录关键字k’与该记录关键字k比较,

若

k’<k则将记录换至R之前,若k’

>k则将记录换至R之后;2）

继续对R前后两部分记录进行快速排序，直至排序范围为1;10.3交换排序2基本步骤为简洁起见，对待排记录仍只写出其关键字序列1(一趟快速排序）设被指定的关键字为待排序列的第一个关键字k，i指向待排序列的的第一个关键字；j指向最后一个关键字；若i<j循环：1）从后向前将关键字与k比较，直至遇到小于k的关键字

k’，k’前移；2）从前向后将关键字与k比较，直至遇到大于k的关键字k’’，k’’后移；（一趟快速排序后，“小”记录被移至k前，“大”的记录被移至k后2

继续对k前后两部分关键字进行快速排序，直至排序范围为1;10.3

交换排序

273865977613

27

49ii例待排记录

4938659776132749

jj273865

97761365

49jj273813

4976976549jji被指定的关键字从后向前，将关键字与49比较，直至遇到小于49的关键字，前移从后向前，将关键字与49比较，直至遇到小于49的关键字，前移从前向后，将关键字与49比较，直至遇到大于49的关键字，后移从前向后，将关键字与49比较，直至遇到大于49的关键字，后移273813977613

6549ii从后向前，将关键字与49比较，直至遇到i=j,将49放至i处49一趟快速排序结束10.3

交换排序[273813]49[769765

49]

[13

2738]49[49657697][13]

27[38]49[4965]76[97]1327384949657697两趟快速排序结束三趟快速排序结束快速排序结束10.3

交换排序例待排记录

4938659776132749273813

4976976549

[273813]49[769765

49]

[13

2738]49[49657697][13]

27[38]49[4965]76[97]1327384949657697两趟快速排序结果三趟快速排序结果一趟快速排序结果快速排序结束特点：1)时间复杂度为0（nlog2n）2）不稳定10.4选择排序一基本思想

在待排记录中依次选择关键字最小的记录，逐渐缩小范围直至全部记录选择完毕。二简单选择排序基本步骤

1）从左至右扫描待排记录

Ri，Ri+1，…，Rn（初始.i=1），在已扫描记录中选择关键字最小者，用j指示；

2）r（j）与r（i）交换；

3）

缩小范围

i=i+1；

重复1）2）3）直至i=n-1例

[4938659776132749]13[386597764927

49]

1327[6597764938

49]

132738[65977649

49]

13273849[65977649

]