《第十章内部排序.ppt》由会员分享，可在线阅读，更多相关《第十章内部排序.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第十章第十章 内部排序内部排序10.1 内部排序概述排序排序(Sorting):(Sorting):将数据元素将数据元素(或记录或记录)的一个任意序列的一个任意序列,重新排列成重新排列成一个按关键字有序的序列。一个按关键字有序的序列。内部排序内部排序待排序记录存放在计算机的内存中进行排序。待排序记录存放在计算机的内存中进行排序。外部排序外部排序待排序记录的数量很大，以致内存一次不能容纳全待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序。部记录，在排序过程中尚需对外存进行访问的排序。稳定排序稳定排序 与与 不稳定排序不稳定排序假设假设 Ki=Kj，且排序前
2、序列中，且排序前序列中 Ri 领先于领先于 Rj；若在排序后的序列中若在排序后的序列中 Ri 仍领先于仍领先于 Rj，则称排序方法是，则称排序方法是稳定的稳定的。若在排序后的序列中若在排序后的序列中 Rj 仍领先于仍领先于 Ri，则称排序方法是，则称排序方法是不稳定的不稳定的。例，序列例，序列 3 15 8 8 6 9若排序后得若排序后得 3 6 8 8 9 15稳定的稳定的若排序后得若排序后得 3 6 8 8 9 15不稳定的不稳定的排序的分类按排序过程依据的不同原则进行分类：按排序过程依据的不同原则进行分类：插入排序、插入排序、交换排序、交换排序、选择排序、选择排序、归并排序和归并排序和基
3、数排序基数排序按工作量分类，可以分为三类：按工作量分类，可以分为三类：(1)(1)简单的排序方法简单的排序方法,其时间复杂度为其时间复杂度为O(nO(n2 2););(2)(2)先进的排序方法先进的排序方法,其时间复杂度为其时间复杂度为O(nlogO(nlog2 2n);n);(3)(3)基数排序，其时间复杂度为基数排序，其时间复杂度为O(dO(dn);n);排序的基本操作和记录的存储方式排序过程中需要的两种基本操作：排序过程中需要的两种基本操作：（1）比较关键字的大小；）比较关键字的大小；（2）将记录从一个位置移至另一个位置。）将记录从一个位置移至另一个位置。待排序记录序列可有下列三种存储方
4、式：待排序记录序列可有下列三种存储方式：（1）记录存放在一组连续的存储单元中；类似于线性表）记录存放在一组连续的存储单元中；类似于线性表的顺序存储结构，记录次序由存储位置决定，实现排序需的顺序存储结构，记录次序由存储位置决定，实现排序需移动记录。移动记录。（2）记录存放在静态链表中；记录次序由指针指示，实）记录存放在静态链表中；记录次序由指针指示，实现排序不需移动记录，仅需修改指针。现排序不需移动记录，仅需修改指针。-链排序链排序（3）记录本身存放在一组连续的存储单元中，同时另设）记录本身存放在一组连续的存储单元中，同时另设指示各个记录存储位置的地址向量，排序过程中不移动记指示各个记录存储位置
5、的地址向量，排序过程中不移动记录本身，而移动地址向量中相应记录的地址。排序结束后录本身，而移动地址向量中相应记录的地址。排序结束后再根据地址调整记录的存储位置。再根据地址调整记录的存储位置。-地址排序地址排序待排序记录的数据类型#define MAXSIZE 20typedef int KeyType;typedef struct KeyType key;InfoType otherinfo;RcdType;typedef struct RedType rMAXSIZE+1;int length;SqList;10.2 插入排序10.2.1 直接插入排序例：序列为 4949，3838，6565
6、，9797，7676，1313，2727，4949 (4949)，3838，6565，9797，7676，1313，2727，4949 (38)(38)(3838，49)49)，6565，9797，7676，1313，2727，4949 (65)(38(65)(38，4949，6565)，9797，7676，1313，2727，4949 (97)(38(97)(38，4949，6565，9797)，7676，1313，2727，4949 (76)(38(76)(38，4949，6565，7676，97)97)，1313，2727，4949 (13)(13)(1313，3838，4949，656
7、5，7676，97)97)，2727，4949 (27)(13(27)(13，2727，3838，4949，6565，7676，97)97)，4949 (49)(13(49)(13，2727，3838，4949，4949，6565，7676，97)97)直接插入排序算法void InsertSort(SqList&L)for(i=2;i=L.length;+i)if(LT(L.ri.key,L.ri-1.key)L.r0=L.ri;/复制为哨兵 for(j=i-1;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;/记录后移 L.rj+1=L.r0;/InsertSor
8、t时间：最坏情形比较与移动各接近时间：最坏情形比较与移动各接近 n(n+1)/2;最好情形比较最好情形比较 n次，无移动；故时间复杂度：次，无移动；故时间复杂度：O(n2)空间：一个辅助空间空间：一个辅助空间如何改进直接插入排序算法如何改进直接插入排序算法1.比较改进比较改进:折半插入排序折半插入排序由于直接插入排序算法利用了有序表的插入操作，由于直接插入排序算法利用了有序表的插入操作，故故顺序查找顺序查找操作可以替换为操作可以替换为折半查找折半查找操作。操作。例，序列例，序列 49 38 65 97 76 13 27 设已形成有序表设已形成有序表 38 49 65 97 76 插入元素插入元
9、素 132.移动改进移动改进:2-路插入排序路插入排序主要目的是减少排序过程中移动记录的次数。主要目的是减少排序过程中移动记录的次数。思想思想:以第一个元素为基准，将元素分为两个序列；以第一个元素为基准，将元素分为两个序列；比第一个元素小的元素构造前序列；比第一个元素小的元素构造前序列；比第一个元素大的元素构造后序列；比第一个元素大的元素构造后序列；例，序列例，序列 49 38 65 97 76 13 27 以以 49 为基准为基准 13 27 38 前序列前序列 65 76 97 后序列后序列算法描述算法描述初始，取第一个元素为初始，取第一个元素为基准元素基准元素；构造前序列构造前序列 S1
10、，后序列，后序列 S2；与基准元素比较与基准元素比较:若小，插入到前序列若小，插入到前序列 S1 中；中；若大，插入到后序列若大，插入到后序列 S2 中；中；对第对第 2,3,n 个元素依次执行个元素依次执行:S1+基准元素基准元素+S2 可得最终有序表。可得最终有序表。例，序列例，序列 49 38 65 97 76 13 27 以以 49 为基准为基准前序列前序列后序列后序列 38 65 65 97 65 76 97 13 38 13 27 38 13 27 38 +49 +65 76 97 10.2.2 Shell排序算法基本思想：基本思想：先将整个待排序记录序列分割成若干先将整个待排序记
11、录序列分割成若干子序列分别进行直接插入排序，待整个子序列分别进行直接插入排序，待整个序列序列“基本有序基本有序”时，再对全体记录进行时，再对全体记录进行一次直接插入排序。一次直接插入排序。算法复杂度：算法复杂度：O(nO(n3/2)例，序列例，序列 49 38 65 97 76 13 27 48 55 4 19 第一趟排序第一趟排序49 13 1938 2765 4897 5576 413 19 4927 3848 6555 974 76第二趟排序第二趟排序13 19 4927 3848 6555 974 7613 55 38 7627 4 65 4948 19 9713 38 55 764
12、27 49 6519 48 97第三趟排序第三趟排序4 13 19 27 38 48 49 55 65 76 97对顺序表L一趟希尔排序Void Shellinsert(Sqlist&L,int dk)For(I=dk+1;I0<(L.r0.key,L.rj.key;j-=dk)L.rj+dk=L.rj;L.rj+k=L.r0;10.3 交换排序交换排序10.3.1 冒泡排序冒泡排序思想思想:通过不断比较相邻元素大小，进行交换来实现排序。通过不断比较相邻元素大小，进行交换来实现排序。首先将第一个元素与第二个元素比较大小，若为逆序，则交换；首先将第一个元素与第二个元素比较大小，若为逆序，则交
13、换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；.直至比较第直至比较第 n-1 个元素与第个元素与第 n 个元素的大小，若为逆序，则交换；个元素的大小，若为逆序，则交换；第一趟排序第一趟排序:结果结果:关键字最大关键字最大的记录被交换至的记录被交换至最后最后一个元素位置上。一个元素位置上。例，序列例，序列 49 38 76 13 2749 38 76 13 2738 49 13 27 38 4913 7627 76初初始始第第一一趟趟排排序序后后最大值最大值13 4927 49次大值次大值第第二二趟趟排排序序后后38 13 2
14、713 2713 38 27 38第第三三趟趟排排序序后后第第四四趟趟排排序序后后 冒泡排序（其时间复杂度O(n2)）初初始始关关键键字字第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后第六趟排序后例：49 38 38 38 38 13 49 38 38 38 38 13 1313 38 49 49 49 13 27 38 49 49 49 13 27 2727 65 65 65 13 27 38 65 65 65 13 27 38 3838 97 76 13 27 49 97 76 13 27 49 4949 76 13 27 76 13 27 4949 4949 13 27 1
15、3 27 4949 6565 27 27 4949 7676 4949 979710.3.2 快速排序快速排序冒泡排序的一种改进算法。冒泡排序的一种改进算法。思想思想:以以首记录首记录作为作为枢枢轴记录轴记录，从前、后双向扫描序列，通过交换，从前、后双向扫描序列，通过交换，实现大值记录后移，小值记录前移，最终将轴记录安置在一个实现大值记录后移，小值记录前移，最终将轴记录安置在一个适当的位置。适当的位置。(小值记录在前、大值记录在后小值记录在前、大值记录在后)枢枢轴记录轴记录将原序列分割成两部分，依次对前后两部分重新设定将原序列分割成两部分，依次对前后两部分重新设定轴记录，继而分别再进行快速排序
16、。轴记录，继而分别再进行快速排序。直至整个序列有序。直至整个序列有序。例，序列例，序列 49 38 65 97 76 13 27 52 第一趟排序第一趟排序49 38 65 97 76 13 27 52ij从从前前寻找寻找大于大于轴记录的记录，从轴记录的记录，从后后寻找寻找小于小于轴记录的记录轴记录的记录；ij交换交换大值记录与小值记录大值记录与小值记录；27 65重复上述两步操作，直至重复上述两步操作，直至 i j；ji13 97ji交换交换枢枢轴记录轴记录和标识和标识 j 指示的记录指示的记录。13 49快速排序举例初始关键字：初始关键字：4949，3838，6565，9797，7676，
17、1313，2727，4949 pivot key 4949jji1 1次交换后：次交换后：2727，3838，6565，9797，7676，1313，4949 iji2 2次交换后：次交换后：2727，3838，9797，7676，1313，6565，4949 ijj3 3次交换后：次交换后：2727，3838，1313，9797，7676，6565，4949 iji4 4次交换后：次交换后：2727，3838，1313，7676，9797，6565，4949 jij一趟完成后：一趟完成后：2727，3838，1313，4949，7676，9797，6565，4949 快速排序算法（一）int
18、 Partition(SqList&L,int low,int high)L.r0=L.rlow;/用子表的第一记录作枢轴记录 pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey)-high;L.rlow=L.rhigh;/将比pivotkey 小的记录移到低端 while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;/将比pivotkey 大的记录移到高端 L.rlow=l.r0;return low;快速排序算法（二）void Qsort(SqList&L,int low,int hi
19、gh)if(lowhigh)pivotloc=Partition(L,low,high);Qsort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high);/QSortvoid QuickSort(SqList&L)Qsort(L,1,L.length);/QuickSort快速排序分析快速排序的平均时间为快速排序的平均时间为T(n)=knlog(n)T(n)=knlog(n)k k为某个常数因子为某个常数因子经验表明经验表明,在同数量级的排序方法中在同数量级的排序方法中,快速排序快速排序的常数因子的常数因子k k最小最小.就平均时间而言就平均时间而言,快速排序
20、是最好的快速排序是最好的.若初始序列按关键字基本有序若初始序列按关键字基本有序,快速排序蜕化快速排序蜕化为起泡排序为起泡排序,其时间复杂度为其时间复杂度为O(nO(n2 2)。10.4 选择排序选择排序 10.4.1.简单选择排序简单选择排序（其时间复杂度其时间复杂度O(nO(n2 2)）基本思想：基本思想：每一趟在序列的后每一趟在序列的后n-i+1(i=1,2,.,n-1)n-i+1(i=1,2,.,n-1)个个记录中选取关键字最小的记录作为第记录中选取关键字最小的记录作为第i i个记录。个记录。void SelectSort(SqList&L)for(i=1;iL.length;+i)j=
21、SelectMinKey(L,i);/在在L.ri.length中中选择选择key最小最小 if(i!=j)L.ri L.rj;/与第与第i个记录交个记录交换换 /SelectSort10.4.1 简单选择排序简单选择排序思想思想:第第 1 趟选择趟选择:从从 1n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 1 个个记录交换。记录交换。第第 2 趟选择趟选择:从从 2n 个记录中选择关键字最小的记录，并和第个记录中选择关键字最小的记录，并和第 2 个个记录交换。记录交换。第第n-1趟选择趟选择:从从 n-1n 个记录中选择关键字最小的记录，并和第个记录中选择关键
22、字最小的记录，并和第 n-1 个记录交换。个记录交换。.例，序列例，序列 49 38 97 65 76第第 1 趟选择趟选择:min38 49 97 65 76第第 2 趟选择趟选择:min38 49 97 65 76第第 3 趟选择趟选择:min38 49 65 97 76第第 4 趟选择趟选择:min38 49 65 76 97 简单选择排序简单选择排序（其时间复杂度其时间复杂度O(nO(n2 2)）基本思想：基本思想：每一趟在序列的后每一趟在序列的后n-i+1(i=1,2,.,n-1)n-i+1(i=1,2,.,n-1)个个记录中选取关键字最小的记录作为第记录中选取关键字最小的记录作为第
23、i i个记录。个记录。void SelectSort(SqList&L)for(i=1;iL.length;+i)j=SelectMinKey(L,i);/在在L.ri.length中选择中选择key最最小小 if(i!=j)L.ri L.rj;/与第与第i个记录交换个记录交换 /SelectSort选择排序的主要操作是进行关键字间的选择排序的主要操作是进行关键字间的比较比较。在在 n 个关键字中选出最小值，至少需要个关键字中选出最小值，至少需要 n-1 次比较次比较。在剩余的在剩余的 n-1 个关键字中选出最小值，至少需要个关键字中选出最小值，至少需要 n-2 次比较次比较？如果能利用前如果
24、能利用前 n-1 次比较所得信息，可以减少后面选择的比较次数。次比较所得信息，可以减少后面选择的比较次数。体育比赛中的锦标赛体育比赛中的锦标赛:例，例，8 名运动员要决出名运动员要决出 冠、亚、季军。冠、亚、季军。按简单选择排序需要比赛按简单选择排序需要比赛 7+6+5=18 场。场。若能够利用以前的比赛结果，比赛场次实际可以减少为若能够利用以前的比赛结果，比赛场次实际可以减少为 11 场。场。前提前提:若若 甲甲 胜胜 乙乙，乙，乙 胜胜 丙丙，则，则 甲甲 必能胜必能胜 丙丙。ZhaoChaLiuBaoDiaoYangXueWangBaoBaoDiaoChaBaoDiaoWang冠军冠军如
25、何求如何求 亚军？亚军？ZhaoChaLiuDiaoYangXueWangChaDiaoCha亚军亚军可以利用前面的比赛结果！可以利用前面的比赛结果！ChaLiuDiaoWang如何求如何求 季军？季军？ZhaoLiuDiaoYangXueWangLiuDiaoDiao季军季军同样可以利用前面的比赛结果！同样可以利用前面的比赛结果！LiuDiaoWangZhao10.4.2 树形选择排序树形选择排序又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。例，序列例，序列 49 38 65 97 76 13 27 50第一趟选择第一趟选
26、择133813493865977613275038651327最小值最小值第二趟选择第二趟选择2738274938659776275038657627次小值次小值第三趟选择第三趟选择38385049386597765038657650次次小值次次小值493865977613275049386597762750缺点缺点:需要需要大量辅助存大量辅助存储空间储空间10.4.3 堆排序堆的定义：堆的定义：n n个元素的序列个元素的序列kk1 1,k,k2 2,.,k,.,kn n 当且仅当满足下当且仅当满足下列条件时，称之为堆。列条件时，称之为堆。ki i i i=k2i2i2i2iki i i i=
27、k2i+12i+12i+12i+1或或(i=1,2,.,n/2)堆堆:一棵完全二叉树，任一个非终端结点的值均小于一棵完全二叉树，任一个非终端结点的值均小于等于等于(或大于等于或大于等于)其左、右儿子结点的值。其左、右儿子结点的值。堆举例：堆举例：96,83,27,38,11,09)12,36,24,85,47,30,53,919683381109271236854730245391完全二叉树完全二叉树,且所有非叶结点的值均不大于且所有非叶结点的值均不大于(不小于不小于)其其左、右孩子结点的值左、右孩子结点的值大顶堆小顶堆2.把这棵普通的完全二叉树改造成堆，便可获取把这棵普通的完全二叉树改造成堆
28、，便可获取最小值最小值；思想思想:3.输出最小值输出最小值；4.删除根结点，继续改造剩余树成堆，便可获取删除根结点，继续改造剩余树成堆，便可获取次小值次小值；5.输出次小值输出次小值；6.重复改造，输出次次小值、次次次小值，直至所有结点均重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序输出，便得到一个排序。1.将序列构造成一棵完全二叉树将序列构造成一棵完全二叉树；实现堆要解决的问题（1）如何从一个无序序列建成一个堆？）如何从一个无序序列建成一个堆？（2）如何在输出堆顶元素之后，调整剩余元）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？（筛选）素成为一个新的堆？（筛选
29、）1236854730245391(a)9136854730245312(b)91368547302453(c)24368547913053(d)筛选：自堆顶至叶子的调整过程筛选：自堆顶至叶子的调整过程 无序序列建成一个堆（从第n/2到1个元素）49，38，65，97，76，13，27，494938497613652797(b)4938497665132797(c)49389776132749(a)654938497665132797(d)1338497665274997(e)10.10Void HeapAdjust(HeapType&H,int s,int m)rc=H.rs;For(j=2
30、*s;j=m;j*=2)If(jm<(H.rj.key,H.rj+1.key)+j;/j为key 较大的纪录的下标If(!LT(rc.key,H.rj.key)break;rc插入在位置s上H.rs=H.rj;s=j;H.rs=rc;/新的位置存放原RC的值10.5 归并排序归并排序归并归并:将两个或两个以上的有序表合并成一个新的有序表。将两个或两个以上的有序表合并成一个新的有序表。有序线性表、有序链表的归并；有序线性表、有序链表的归并；利用归并的利用归并的思想思想实现排序实现排序:初始，初始，n 个记录看作是个记录看作是 n 个有序的子序列，长度为个有序的子序列，长度为 1；两两归并，得
31、到两两归并，得到 n/2 个长度为个长度为 2 或或 1 的有序的子序列的有序的子序列；再两两归并再两两归并；重复执行直至得到一个长度为重复执行直至得到一个长度为 n 的有序序列为止的有序序列为止。这种排序方法称为这种排序方法称为 2路归并排序路归并排序。10.5 归并排序(Merging Sort)2-路归并举例路归并举例:初始关键字初始关键字:49 38 65 97 76 13 27一趟归并后一趟归并后:38 49 65 97 13 76 27二趟归并后二趟归并后:38 49 65 97 13 27 76 三趟归并后三趟归并后:13 27 38 49 65 76 97 2-路归并算法voi
32、d Merge(RcdType SR,RcdType&TR,int i,int m,int n)/将有序的将有序的SRi.m和和SRm+1.n合并为有序的合并为有序的TRi.n for(j=m+1,k=i;i=m&j=n;+k)if LQ(SRi.key,SRj.key)TRk=SRi+;else TRk=SRj+;if(i=m)TRk.n=SRi.m;/复制剩余的复制剩余的SRi.m if(j=n)TRk.n=SRj.n;/复制剩余的复制剩余的SRj.n/Merge归并算法的特点需要辅助空间需要辅助空间:O(n):O(n)整个归并需要整个归并需要 log log2 2n n 趟趟时间复杂度时
33、间复杂度:O(n log:O(n log2 2n)n)它是稳定的排序方法它是稳定的排序方法思想可以推广到思想可以推广到“多多-路归并路归并“10.6 基数排序基数排序(Radix Sorting)(Radix Sorting)不需要进行关键字之间的比较不需要进行关键字之间的比较借助多关键字排序的思想对单关键字排序借助多关键字排序的思想对单关键字排序10.6.1 多关键字排序多关键字排序 22 33 44 55 66 77 88 99 1010 JJ QQ KK AA 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 J J Q Q K K A A 2 2 3 3 4 4
34、 5 5 6 6 7 7 8 8 9 9 1010 J J Q Q K K A A 22 33 44 55 66 77 88 99 1010 JJ QQ KK A A花色花色()优先于面值优先于面值(23.A)(23.109-063-930-589-184-505-269-008-083278-109-063-930-589-184-505-269-008-0830132456789278109063930184505589269008083930-063-083-184-505-278-008-109-589-269930-063-083-184-505-278-008-109-589-26
35、9930-063-083-184-505-278-008-109-589-269930-063-083-184-505-278-008-109-589-2690132456789278109063930184505589269008184505-008-109-930-063-269-278-083-184-589505-008-109-930-063-269-278-083-184-5890132456789505008109930063269278083083589008-063-083-109-184-269-278-505-589-930008-063-083-109-184-269-
36、278-505-589-930基数排序分析(d个关键字的取值范围rd）“收集收集”重复的次数为重复的次数为d;d;一轮一轮“分配分配”的次数为的次数为n+rd;n+rd;时间复杂度为时间复杂度为O(d(n+rd);O(d(n+rd);链式基数排序所需辅助存储量为链式基数排序所需辅助存储量为O(n)O(n)。10.7 各种排序方法的比较讨论排序方法简单排序Shell排序快速排序堆排序归并排序基数排序平均时间O(n2)O(n3/2)O(nlogn)O(nlogn)O(nlogn)O(d(n+rd)最坏情况O(n2)O(n2)O(n2)O(nlogn)O(nlogn)O(d(n+rd)辅助存储O(1)O(1)O(logn)O(1)O(n)O(rd)插入插入,交换交换,选择选择,归并归并,基数排序基数排序几个结论(1)平均时间性能快速排序最佳,但最坏情况下的时间性能不如堆排序和归并排序.(2)简单排序以“直接插入排序”最简单,当序列“基本有序”或n较小时,它是最佳排序方法,通常用它与“先进的排序方法”结合使用.(3)基数排序最适合n很大而关键字较小的序列(4)从稳定性看,归并排序,基数排序和“简单排序法”是稳定的;而快速排序,堆排序和SHELL排序是不稳定的.(5)稳定性由方法本身决定,不稳定的方法总能举出使其不稳定的实例.