内部排序1概述2插入排序3快速排序

数据结构

10.1概述第十章内部排序

10.2插入排序

10.3快速排序

10.4选择排序

10.5归并排序

10.6基数排序

10.7各种内部排序方法的比较

10.1

概述一.排序的定义

假设含有n个记录的序列{r1,r2,,rn

},对应的关键字序列为{k1,k2,,kn

},需确定一种关系

p(1),p(2),,p(n)使得关键字序列满足：

kp1kp2

kpn或者

kp1kp2

kpn即使记录成为一个按关键字有序的序列

{rp1,rp2,,rpn

}这一过程称为排序。二.排序的稳定性在待排记录序列中，如果任意两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。

设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

概述排序稳定性的应用股票交易系统：考虑一种股票交易

1）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用户申购请求插入申购队列队尾；

2）股票交易系统按如下原则交易：

A）申购价高者先成交

B）申购价相同者按申购时间先后顺序成交例申购队列：用线性表表示交易前：将申购队列按申购价排序，显然为满足原则交易(B)，要求排序方法是稳定的申购队列（09,10),(06,10.5),(033,9.8),(051,10)排序后：(06,10.5),(09,10),(051,10),(033,9.8)实现

10.1

概述①待排记录放于地址连续的存储单元中；②待排记录放于链表，记录之间的次序关系由指针指示。③待排记录存放在地址连续的存储单元中，同时另设一个指示各个记录存储位置的地址向量。三.待排记录序列的存储方式

10.1

概述四.顺序存储结构表示待排记录#defineMAXSIZE20//顺序表的最大长度typedef

int

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

struct{

KeyTypekey;//关键字项

InfoType

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

struct{

RedTyper[MAXSIZE+1];//r[0]闲置或用作监视哨

intlength;//顺序表长度}SqList;//顺序表类型

10.1

概述

10.2

插入排序思路：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。插入排序有多种具体实现算法：

1)直接插入排序

2)希尔排序一.直接插入排序

10.2

插入排序思路：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。有序序列无序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……解决方法：将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。关键问题(1)如何构造初始的有序序列？一.直接插入排序

10.2

插入排序算法描述：for(i=2;i<=L.length;++i){…}关键问题(2)如何查找待插入记录的插入位置?解决方法：在i-1个记录的有序区r[1]~r[i-1]中插入记录r[i]，首先顺序查找r[i]的正确插入位置，然后将r[i]插入到相应位置。一.直接插入排序

10.2

插入排序算法描述：L.r[0]=L.r[i];

for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];

例初始关键字4938659776132749()i=23849659776132749()(38)i=33849659776132749()(65)i=43849659776132749()(97)i=81327384949657697()(49)i=53849657697132749()(76)i=61338496576972749()(13)i=71327384965769749()(27)算法：voidInsertSort(SqList&L){for(i=2;i<=L.length;++i)//只有一个元素也是有序表

if(L.r[i].key<L.r[i-1].key)//只有“<”才做插入操作

{L.r[0]=L.r[i];//r[0]为监视哨

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

L.r[j+1]=L.r[0];//插入到正确位置

}}voidInsertSort(SqList&L){for(i=2;i<=L.length;++i)//只有一个元素也是有序表

if(L.r[i].key<L.r[i-1].key)//只有“<”才做插入操作

{L.r[0]=L.r[i];//r[0]为监视哨

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

L.r[j+1]=L.r[0];//插入到正确位置

}}i=61338496576972749()(13)3849657697132749()j一.直接插入排序

10.2

插入排序算法分析最好情况（正序）最坏情况（逆序）时间复杂度为O(n2)直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。直接插入排序算法是一种稳定的排序算法。说明二.希尔排序（缩小增量排序）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高；由于直接插入排序算法简单，则在待排序记录数量n较小时效率也很高。改进：

10.2

插入排序二.希尔排序（缩小增量排序）先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。思路：

10.2

插入排序基本有序指已接近正序：1,2,8,4,5,6,7,3,9局部有序指某些部分有序：6,7,8,9,1,2,3,4,5二.希尔排序（缩小增量排序）问题1：如何使待排记录个数较少；问题2：如何分割待排序列；问题3：子序列内如何进行直接插入排序。待解决问题：

10.2

插入排序例初始关键字4938659776132749一趟排序结果491327497638659749763813974965274927766513493897二趟排序结果2713493865497697三趟排序结果1327384949657697①增量序列的最后一个增量必须为1。②希尔排序较直接插入排序时间复杂度低,时间性能在O(n2)和O(nlog2n)之间。③算法不稳定。如2,5,5,4。说明：二.希尔排序（缩小增量排序）

10.2

插入排序思路：快速排序有多种具体实现算法：

1)起泡排序

2)快速排序

10.3

快速排序在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。思路：一.起泡排序对相邻记录关键字进行比较，若为逆序，则交换两记录。然后依次进行第n-1个记录和第n个记录关键字的比较。此过程称为第一趟排序。一般情况下，整个起泡排序只需进行k(1≤k≤n)趟操作，起泡排序的结束条件是“在某一趟排序过程中没有进行记录交换的操作”。

10.3

快速排序例一.起泡排序4938659776132749384965761327

4997初始关键字第一趟排序后4938384965977613274949653849659776132749659738496597761327499776384965769713274997133849657613972749972738496576132797499749例一.起泡排序4938659776132749384965761327

4997384965132749

76

9738491327

4965

76

9738132749

49

65

76

97381327

49

49

65

76

971327

3849

49

65

76

97初始关键字第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后第六趟排序后算法：voidBubble_Sort(SqList&L){

for(i=L.length-1,change=TRUE;i>=1&&change;--i){change=FALSE;

for(j=0;j<i;++j){if(L.r[j+1].key<L.r[j].key){L.r[j]↔L.r[j+1];change=TRUE;}}}}说明：起泡排序为稳定排序。一.起泡排序

10.3

快速排序起泡排序的时间性能分析最好情况（正序）：比较次数：n-1移动次数：0

12345时间复杂度为O(n)。12345一.起泡排序

10.3

快速排序起泡排序的时间性能分析最好情况（正序）：比较次数：n-1移动次数：0

时间复杂度为O(n)。最坏情况（反序）：比较次数：移动次数：2)1(1-=å=nn(n-i)n-1i2)1(1-=å=n3n3(n-i)n-1i5432143215321452134512345平均情况：时间复杂度为O(n2)

10.3

快速排序改进的着眼点：在起泡排序中，记录的比较和移动是在相邻单元中进行的，记录每次交换只能上移或下移一个单元，因而总的比较次数和移动次数较多。减少总的比较次数和移动次数增大记录的比较和移动距离较大记录从前面直接移动到后面较小记录从后面直接移动到前面思路：二.快速排序首先选一个枢轴值（即比较的基准），通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

10.3

快速排序选择枢轴的方法：1.使用第一个记录的关键码；2.选取序列中间记录的关键码；3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为枢轴并调换到第一个记录的位置；4.随机选取枢轴。关键问题⑴：如何选择枢轴？选取不同枢轴的后果：决定两个子序列的长度，子序列的长度最好相等。

10.3

快速排序关键问题⑵：如何进行一次划分？

10.3

快速排序13652750384955ji1338652750495513652750493855jjiiijijjj关键问题⑶:如何处理分割得到的两个待排序子序列？

10.3

快速排序解决方法：对分割得到的两个子序列递归地执行快速排序。1327386550495513275038495565ijij算法：voidPartition(SqList&L,int

low,inthigh){L.r[0]=L.r[low];//用表的第一个记录作枢轴记录

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[high]=L.r[low];//比枢轴记录大的记录移到高端

}

L.r[low]=L.r[0];returnlow;}算法：voidQSort(SqList&L,int

low,inthigh)//对顺序表的子表排序{if(low<high)//长度大于1{pivotloc=Partition(L,low,high);//枢轴位置

QSort(L,low,pivotloc-1);//对低子表递归排序

QSort(L.pivotloc+1,high);//对高子表递归排序

}}voidQuickSort(SqList&L)//对顺序表排序{QSort(L,1,L.length);}例初始关键字386597761327494949枢轴记录关键字pivotkey=lowhighhigh27进行第一次交换后27386597761349lowhighlow65进行第二次交换后2738977