第6章内部排序

第6章内部排序1

6.1概述

6.2插入排序

6.3交换排序

6.4选择排序

6.5归并排序6.6基数排序6.7小结（直接插入排序、希尔排序）（起泡排序、快速排序）（直接选择排序、堆排序）6.1概述21.什么是排序？将一组杂乱无章的数据按一定的规律顺次排列起来。

2.排序的目的是什么？存放在数据表中按关键字排序3.排序算法的好坏如何衡量？时间效率——排序速度（即排序所花费的全部比较次数）空间效率——占内存辅助空间的大小稳定性———若两个记录A和B的关键字值相等，但排序后A、B

的先后次序保持不变，则称此排序算法是稳定的。

——便于查找！6.1概述3若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序。注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。

5.待排序记录在内存中怎样存储和处理？大多数排序算法都有两个基本的操作：（1）比较两个关键字的大小（2）将记录从一个位置移动到另一个位置（1）顺序存储（2）静态链表（3）地址4.什么叫内部排序？什么叫外部排序？6.1概述4注：大多数排序算法都是针对顺序表结构的(便于直接移动元素)Typedefstruct{

//定义每个记录（数据元素）的结构

KeyTypekey;

//关键字

InfoTypeotherinfo;

//其它数据项}RecordType;Typedefstruct{

//定义顺序表的结构

RecordTyper[MAXSIZE+1];

//存储顺序表的向量

//r[0]一般作哨兵或缓冲区

intlength;

//顺序表的长度}SqList;#defineMAXSIZE20//设记录不超过20个typedefintKeyType;//设关键字为整型量（int型）6.顺序存储（顺序表）的抽象数据类型6.2插入排序5插入排序的基本思想是：插入排序有多种具体实现算法：

（1）直接插入排序（2）折半插入排序（3）表插入排序

（4）希尔排序

每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。6.2.1直接插入排序6直接插入排序是最简单的排序方法新元素插入到哪里？在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。6.2.1直接插入排序7例1：关键字序列T=（13，6，3，31，9，27，5，11），请写出直接插入排序的中间过程序列。【13】,6,3,31,9,27,5,11第一趟直接插入排序【6,13】,3,31,9,27,5,11第二趟直接插入排序【3,6,13】,31,9,27,5,11第三趟直接插入排序【3,6,13，31】,9,27,5,11第四趟直接插入排序【3,6,9,13，31】,27,5,11第五趟直接插入排序【3,6,9,13，27,31】,5,11第六趟直接插入排序【3,5,6,9,13，27,31】,11第七趟直接插入排序【3,5,6,9,11，13，27,31】

例2：关键字序列T=（21，25，49，25*，16，08），

请写出直接插入排序的具体实现过程。8i=121254925*16080123456暂存21i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：假设该序列已存入一维数组V[7]中，将V[0]作为缓冲或暂存单元（Temp）。则程序执行过程为：254925*初态：16252108时间效率：

O(n2)——因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n2)。其他情况下还要加上移动元素的次数。空间效率：O（1）——因为仅占用1个缓冲单元算法的稳定性：稳定——因为25*排序后仍然在25的后面。2149164925*直接插入排序算法9voidInsertsort(){inti,j;for(i=2;i<=N;i++){ p[0]=p[i]; j=i-1; while(p[0]<p[j]) { p[j+1]=p[j]; j--; } p[j+1]=p[0];}}ijjj6.2.3希尔（shell）排序（又称缩小增量排序）10基本思想先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。技巧

子序列的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短（例如依次取5,3,1），直到dk＝1为止。例：关键字序列T=(49，38，65，97,76,13,27,49*，55,04），请写出希尔排序的具体实现过程。11380123456789104938659776132749*5504初态：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*9755760427386549*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697r[i]4913382749*6555970476算法分析：开始时dk

的值较大，子序列中的对象较少，排序速度较快；随着排序进展，dk

值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。6.3交换排序12

两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。交换排序的主要算法有：

（1）冒泡排序

（2）快速排序交换排序的基本思想是：6.3.1冒泡排序13基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。例：关键字序列T=(21，25，49，25*，16，08），请写出冒泡排序的具体实现过程。21，25，49，

25*，16，0821，25，

25，49，

25*,49，

16，

49，

08

，49第1趟冒泡排序结果21，25，

25*,

16，

08

，49冒泡排序的算法14voidbsort(inta[],intn){inttemp,i,j;intflag;//交换标志

for(j=1;j<=n-1;j++)//最多做n-1趟排序

{flag=0;//本趟排序开始前，交换标志应为0for(i=1;i<=n-j;i++)//对当前无序区扫描

if(a[i]>a[i+1]){//交换记录

temp=a[i];a[i]=a[i+1];a[i+1]=temp;flag=1;//发生了交换，故将交换标志置为真

}if(flag==0)break;//本趟排序未发生交换，提前终止算法

}}6.3.2快速排序15

从待排序列中任取一个元素(例如取第一个)作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。基本思想：例1：关键字序列T=(21，25，49，25*，16，08），请写出快速排序的算法步骤。(设以首元素为枢轴中心)21，25，49，25*，16，08ij08，25，49，25*，16，□ij08，□，49，25*，16，25ji08，16，49，25*，□，25ji08，16，□，25*，49，25ji08，16，□，25*，49，25ji08<21,所以交换，i++25>21,所以交换，j--16<21,所以交换，i++49>21,所以交换，j--第1趟快速排序结果{08，16}，21，{25*，49，25}第1趟快速排序结果{08，16}，21，{25*，49，25}，分别对{08，16}和{25*，49，25}进行快速排序对{08，16}

进行快速排序

08，16ij08，16ij08<16,不需要交换，j--∴{08，16}快速排序结果08，{16}对{25*，49，25}进行快速排序

25*，49，25ij25*，49，25ij25*=25,不需要交换，j--∴{25*，49，25}快速排序结果25*，{49，25}25*，49，25ij25*<49,不需要交换，j--第2趟快速排序结果

08，{16}，21，25*，{49，25}快速排序算法18pivotkey=r[i].key;//取支点的关键码存入pivotkey变量while(i<j){

//从表的两端交替地向中间扫描

while(i<j&&r[j].key>=pivotkey)--j; r[i]=r[j];//将比支点小的记录交换到低端；

while(i<j&&r[i].key<=pivotkey)++i; r[j]=r[i];//将比支点大的记录交换到高端；}r[i]=r[0];//支点记录到位；

returni;//返回支点记录所在位置。}//PartitionintPartition(SqList&L,inti,intj){//一趟快排

r[0]=r[i];//以子表的首记录作为支点记录，放入r[0]单元一趟快速排序算法（针对一个子表的操作）①每一趟的子表的形成是采用从两头向中间交替式逼近法；②由于每趟中对各子表的操作都相似，主程序可采用递归算法。快速排序算法19voidQSort(SqList&L,inti,intj){

if(i<j){

pivot=Partition(L,i,j);

QSort(L,i,pivot-1);

QSort(L,pivot+1,j);}}整个快速排序的递归算法：//长度>1//对顺序表L中的子序列r[i…j]

作快速排序//一趟快排，将r[]一分为二//在左子区间进行递归快排，直到长度为1//在右子区间进行递归快排，直到长度为1//QSort6.4选择排序20选择排序有多种具体实现算法

（1）简单选择排序

（2）堆排序选择排序的基本思想是：每一趟在后面n-i个待排记录中选取关键字最小的记录作为有序序列中的第i个记录。6.4.1简单选择排序21思路简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小者放到r[2]位置；…如此进行下去，直到全部有序为止。6.4.1简单选择排序22例：关键字序列T=（21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。原始序列：

21，25，49，25*，16，08第1趟第2趟第3趟第4趟第5趟08，25，49，25*，16，2108，16,

49，25*，25，2108，16,21，25*，25，4908，16,21，25*，25，4908，16,21，25*，25，49最小值08

与r[1]交换位置简单选择排序的算法23SELECTSORT(){inti,j,k;for(i=1;i<n;i++){k=i;for(j=i+1;j<=n;j++)if(p[j]<p[k])k=j;if(k!=i){temp=p[i];p[i]=p[k];p[k]=temp;}}}//在r[i…n]中选择key最小的记录//与第i个记录交换6.4.2堆排序241.什么是堆？堆的定义：设有n个元素的序列k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。ki≤

k2iki≤

k2i+1ki≥

k2iki≥

k2i+1或者i=1,2,…n/2解释：如果让满足以上条件的元素序列（k1，k2，…，kn）顺次排成一棵完全二叉树，则此树的特点是：树中所有根结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。2.怎样建堆？3.怎样堆排序？6.4.2堆排序25082546495867234561（大根堆）918566765867234561557例：有序列T1=（08,25,49,46,58,67）和序列T2=（91,85,76,66,58,67,55）,判断它们是否“堆”？√（小根堆）√（小顶堆）（最小堆）（大顶堆）（最大堆）2.怎样建堆？26步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。212525*491608123456例：关键字序列T=(21，25，49，25*，16，08），请建大根堆。解：为便于理解，先将原始序列画成完全二叉树的形式完全二叉树的最后一个非终端结点编号必为n/2

！！注：终端结点（即叶子）没有任何子女，无需单独调整。21i=3:

49大于08，不必调整；i=2:

25大于25*和16，也不必调整；i=1:

21小于25和49，要调整！49而且21还应当向下比较！！3.怎样进行堆排序？27关键：将堆的当前顶点输出后，如何将剩余序列重新调整为堆？方法：将当前顶点与堆尾记录交换，然后仿建堆动作，从上至下新调整，如此反复直至排序结束。例：对刚才建好的大根堆进行排序28删除49交换1号与6号记录492525*211608123456初始最大堆2525*1621136542084929删除25交换1号与5号记录从1号到5号重新调整为最大堆082525*2116491234561625*08252149136542082525*08从1号到4号重新调整为最大堆25*16082125491234566.5归并排序30归并排序的基本思想是：将两个（或以上）的有序表组成新的有序表。更实际的意义：可以把一个长度为n的无序序列看成是n个长度为1的有序子序列，首先做两两归并，得到n/2个长度为2的子序列；再做两两归并，…，如此重复，直到最后得到一个长度为n的有序序列。310816212525*374954627293len=1616375408212525*49627293len=8212525*4908627293len=4163754212525*4962930872163754212525*9362720837165449len=1len=2例：关键字序列T=（21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。6.6基数排序32要讨论的问题：1.什么是“多关键字”排序？实现方法？2.单逻辑关键字怎样“按位值”排序？基数排序的基本思想是：借助多关键字排序的思想对单逻辑关键字进行排序。即：用关键字不同的位值进行排序。1.什么是“多关键字”排序？实现方法？33例1：对一副扑克牌该如何排序？

若规定花色和面值的顺序关系为：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A多关键字排序的实现方法通常有两种：最高位优先法MSD

(MostSignificantDigitfirst)最低位优先法LSD

(LeastSignificantDigitfirst)1.什么是“多关键字”排序？实现方法？34例：对一副扑克牌该如何排序？答：若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用MSD和LSD方法都可以达到排序目的。MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行排序。LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序。2.单逻辑关键字怎样“按位值”排序？35设n个记录的序列为：{V0,V1,…,Vn-1}，可以把每个记录Vi

的单关键码Ki

看成是一个d元组（Ki1,Ki2,…,Kid），则其中的每一个分量Kij

(1

jd)

也可看成是一个关键字。4注1：

Ki1＝最高位，Kid＝最低位；Ki共有d位，可看成d元组；注2：每个分量Kij(1

j

d)有radix种取值，则称radix为基数。26(9,8,4)(0,1,…,9)（a,b,…,z）(d,i,a,n)310例1：关键码984可以看成是

元组；基数radix

为

。例2：关键码dian可以看成是

元组；基数radix

为

。思路：这种LSD排序方法称为：36例：初始关键字序列T=（32,13,27,32*,19，33），请分别用MSD和LSD进行排序。法1（MSD）：原始序列：32,19,27,32*,13，33

先按高位Ki1

排序：（19,13）,27,（32,32*，33）

再按低位Ki2排序：13,19

，27,32,32*,33法2（LSD）：原始序列：32,13,27,32*,19，33

先按低位Ki2排序：

32,32*,13,33,27,19

再按高位Ki1排序：

13,19,27,32,32*,33基数排序用链队列来实现基数排序—链式基数排序2.单逻辑关键字怎样“按位值”排序？37例:请实现以下关键字序列的链式基数排序：

T=（614，738，921，485，637，101，215，530，790，306）614921485637738101215530790306第一趟分配e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]614738921485637101215530790306f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]原始序列链表：r[0]→（从最低位i=3开始排序，f[]

是队首指针，e[]

为队尾指针）第一趟收集（让队尾指针e[i]

链接到下一非空队首指针f[i+1]

即可）530790921101614485215306637738r[0]→第一趟收集的结果38e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]614738921485637101215530790306f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]第二趟分配（按次低位i=2）530790921101614485215306637738第二趟收集（让队尾指针e[i]

链接到下一非空队首指针f[i+1]

）530790921101614485215306637738r[0]→r[0]→第二趟收集的结果39530790921101614485215306637738e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]614738921485637101215530790306f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]第三趟分配（按最高位i=1）第三趟收集（让队尾指针e[i]

链接到下一非空队首指针f[i+1]

）530790921101614485215306637738r[0]→r[0]→各种内部排序方法的比较40排序方法最好情况平均时间最坏情况辅助存储稳定性简单排序O(n)O(n2)O(n2)O(1）稳定快速排序O(nlgn)O(nlgn)O(n2)O(lgn)不稳定堆排序O(nlgn)O(nlgn)O(nlgn)O(1）不稳定归并排序O(nlgn)O(nlgn)O(nlgn)O(n）稳定基数排序O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd)稳定简单选择O(n2)O(n2)O(n2)O(1）不稳定直接插入O(n)O(n2)O(n2)O(1）稳定折半插入O(nlgn)O(nlgn)O(nlgn)O(1）稳定冒泡O(n)O(n2)O(n2)O(1）稳定练习411.

以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行直接插入排序的各趟排序过程。原始序列：

256，301，751，129，937，863，742，694，076，438[256，301]，751，129，937，863，742，694，076，438[256，301，751]，129，937，863，742，694，076，438[129，256，301，751]，937，863，742，694，076，438[129，256，301，751，937]，863，742，694，076，438[129，256，301，751，863，937]，742，694，076，438[129，256，301，742，751，863，937]，694，076，438[129，256，301，694，742，751，863，937]，076，438[076，129，256，301，694，742，751，863，937]，438[076，129，256，301，438，694，742，751，863，937]第1趟第2趟第3趟第4趟第5趟第6趟第7趟第8趟第9趟[]练习42Q,P,R,Y,S,XC,M,F,H,A,D,P,Q,R,2.

欲将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母升序重排，则初始步长为4的希尔排序第一趟的结果是？答：原始序列：

Q,H,C,Y,P,A,M,S,R,D,F,X

shell一趟后：A,D,H,C,F,M,S,X,Y第一趟希尔排序结果：PACSQDFXRHMY练习3、设文件有10个记录，其关键字值分别为:37,23,7,79,29,43,73,19,31,61,试给出冒泡排序法按非递减的次序进行排序过程中的每一趟结果序列。4、有一组键值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大进行排序，请写出第一趟排序过程中键值的移动情况。

5、已知有十个待排序的记录，其关键字分别为：256，301，751，129，937,863，742，694，076，438请用快速排序的方法将它们从小到大排列。6、设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。

(1)写