西西 南南 大大 学学 计计 算算 机机 与与 信信 息息 科科 学学 学学 院院熊海灵熊海灵数据结构第十章 排序数据结构第十章第十章 内部排序内部排序 10.1 概述 10.2 插入排序10.2.1 直接插入排序10.2.2 其它插入排序10.2.3 希尔排序 10.3 快速排序 10.4 选择排序10.4.1 简单选择排序10.4.3 堆排序 10.5 归并排序 10.6 基数排序10.6.1 多关键字的排序10.6.2 链式基数排序 10.7 各种内部排序方法的比较讨论数据结构 10.1 10.1 概述概述排序：将一个数据元素（或记录）的任意序列，重新 排列成一个按关键字有序的序列。有序表与无序表：一组记录按关键字的递增或递减次 序排列得到的结果被称之为有序表，相应地，把排序 前的状态称为无序表。内部排序和外部排序： 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序正序表与逆序表：若有序表是按关键字升序排列的， 则称为升序表或正序表，否则称为降序表或逆序表。 不失普遍性，一般只讨论正序表。数据结构 内部排序的方法： 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 其它排序: 多关键字排序、基数排序排序基本操作： 比较两个关键字大小 将记录从一个位置移动到另一个位置 排序算法的稳定性: 考虑有多个数据元素具有相同关键字的情况。 稳定：具有相同关键字的数据元素的相对位置关系 在排序前后保持不变。 不稳定：具有相同关键字的数据元素的相对位置关 系在排序前后发生了改变。数据结构待排序记录在内存中怎样存储和处理？顺序排序排序时直接移动记录； 链表排序排序时只移动指针； 地址排序排序时先移动地址，最后再移动记录 。 注：地址排序中可以增设一维数组来专门存放记录的地址 。数据结构注：大多数排序算法都是针对顺序表结构的(便于直接移动元素)顺序存储（顺序表）的抽象数据类型如何表示？typedef struct /定义每个记录（数据元素）的结构KeyType key ; /关键字 InfoType otherinfo; /其它数据项 RedType; /记录类型typedef struct /定义顺序表L的结构RecordType r MAXSIZE +1 ; /存储顺序表的向量/r0一般作哨兵或缓冲区int length ; /顺序表的长度 SqList; /顺序表类型# define MAXSIZE 20 /设上课举例的记录数均不超过20个 typedef int KeyType ; /设关键字为整型量（int型）数据结构 内部排序的算法有哪些？按排序的规则不同，可分为5类： v插入排序 v交换排序（重点是快速排序） v选择排序 v归并排序 v基数排序d关键字的位数(长度)按排序算法的时间复杂度不同，可分为3类： v简单的排序算法：时间效率低，O(n2) v先进的排序算法: 时间效率高，O( nlog2n ) v基 数 排 序 算法：时间效率高，O( dn)数据结构例:49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827(13 27 38 49 65 76 97)排序结果：10.2 10.2 插入排序插入排序10.2.1 10.2.1 直接插入排序直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序列中第 1个记录看成是一个有序子序列，然后从第2个记录开始 ，逐个进行插入，直至整个序列有序。 算法参见P265数据结构直接插入排序直接插入排序算法的实现：算法的实现：void InsertSort ( SqList i =low; -j ) L.rj+1 = L.rj; / 记录后移L.rhigh+1 = L.r0; / 插入 / BInsertSort折半插入排序只能减少排序 过程中关键字比较的时间， 并不能减少记录移动的时间 ，因此折半插入排序的时间 复杂度仍为O (n2)。数据结构10.2.3 10.2.3 希尔排序希尔排序希尔排序（Shells Sort）又称为“缩小增量排序”。 排序过程：先取一个正整数d11时需对j循环中以防“出界“ 另作“j0“的判别，即L.r0 不再起到“ 监视哨“的作用，而仅仅作为一个暂存记 录的空间。 void ShellInsert ( SqList i0 i1 -i) change = FALSE;for (j=1; j L.rj+1.key) L.rjL.rj+1; change = TRUE; / for i / BubbleSort算法中设立了一个标志一趟起泡中 是否进行了交换记录操作的布尔型 变量change，在每一趟起泡之前均 将它设为“FALSE“，一旦进行记 录交换，则将它改为“TRUE“，因 此 change=TRUE 是进行下一趟起 泡的必要条件。 数据结构算法评价算法评价 最好情况（正序）时： 比较次数：n-1 移动次数：0最坏情况（逆序）时： 比较次数：移动次数：时间复杂度：T(n)=O(n)冒泡排序的优点：冒泡排序的优点：每一趟每一趟 整理元素时，不仅可整理元素时，不仅可 以完全确定一个元素以完全确定一个元素 的位置（挤出一个泡的位置（挤出一个泡 到表尾），还可以对到表尾），还可以对 前面的元素作一些整前面的元素作一些整 理，所以比一般的排理，所以比一般的排 序要快。序要快。空间复杂度：S(n)=O(1)数据结构 快速排序快速排序从待排序列中任取一个元素 (例如取第一个) 作 为中心，所有比它小的元素一律前放，所有比它大的 元素一律后放，形成左右两个子表； 然后再对各子表重新选择中心元素并依此规则调 整，直到每个子表的元素只剩一个。此时便为有序序 列了。基本思想：基本思想：优点：因为每趟可以确定不止一个元素的位置，而且呈 指数增加，所以特别快！ 前提：顺序存储结构 数据结构例：初始关键字： 49 38 65 97 76 13 27 50 ijji完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij算法参见P274,P275x=49数据结构如何编程实现？ 分析： 每一趟子表的形成是采用从两头向中间交替式逼近法； 由于每趟中对各子表的操作都相似，主程序可采用递归 算法。数据结构int Partition ( RcdType R, int low, int high) / 对记录子序列 Rlowhigh 进行一趟快速排序，并返回枢轴记录/ 所在位置，使得在它之前的记录的关键字均不大于它的关键字，/ 而在它之后的记录的关键字均不小于它的关键字R0 = Rlow; / 将枢轴记录移至数组的闲置分量pivotkey = Rlow.key; / 枢轴记录关键字while (low=pivotkey) -high;Rlow = Rhigh; / 将比枢轴记录小的记录移到低端while (lowL.rj.key) min=j; return min; 数据结构时间复杂度： T(n)=O(n)算法评价算法评价比较次数：记录移动次数最好情况：0最坏情况：3(n-1)讨论：讨论：能否利用（能否利用（或记忆或记忆）首趟的）首趟的n-1n-1次次比较所得比较所得 信息，从而尽量减少后续比较次数呢？信息，从而尽量减少后续比较次数呢？答：答：能！能！请看请看锦标赛排序和锦标赛排序和 堆排序堆排序数据结构10.4.2 10.4.2 锦标赛排序锦标赛排序 ( (又称树形选择排序又称树形选择排序) )基本思想：基本思想：与体育比赛时的淘汰赛类似。与体育比赛时的淘汰赛类似。首先对首先对 n n个记录的关键字进行两两比较，得到个记录的关键字进行两两比较，得到 n n/2/2 个优胜者个优胜者( (关键字小者关键字小者) )，作为第一步比较的结果，作为第一步比较的结果 保留下来。然后在这保留下来。然后在这 n n/2/2 个较小者之间再进行两两个较小者之间再进行两两 比较，比较，如此重复，直到选出最小关键字的记录为，如此重复，直到选出最小关键字的记录为 止。止。 优点：优点：减少比较次数，加快排序速度减少比较次数，加快排序速度 缺点：缺点：空间效率低空间效率低例：关键字序列T= （21，25，49，25*，16，08，63）， 请给出锦标赛排序的具体实现过程。0808Winner Winner ( (胜者胜者) )212108080808636325*25*212121212525494925*25*161608086363r r11注：为便于自动处理，建议每个记录多开两个特殊分量： keyotherinfoIndex(结结点位置编编号 ）Tag（是否参加比较较）初态：初态：补足补足2 2k k( k=( k= loglog2 2n n ) )个叶子结点个叶子结点第一趟：第一趟：第二趟：第二趟：0808212108080808636325*25*212121212525494925*25*161608086363161616161616r r22Winner Winner ( (胜者胜者) )求次小值求次小值1616时时, ,只需比较只需比较2 2 次，即只比较次，即只比较 loglog2 2n n -1 -1次次令其TagTag0,不参与比较令其TagTag0 0,不参与比较第三趟：第三趟：1616212116161616636325*25*212121212525494925*25*161608086363r r33Winner Winner ( (胜者胜者) )636321210808212108080808636325*25*212121212525494925*25*16160808636363632121第四趟：第四趟：r r44Winner Winner ( (胜者胜者) )252525252525左右结点 相同时左 边“小”0808212108080808636325*25*212121212525494925*25*16160808636316161616161663632121252525252525第五趟：第五趟：r r55Winner Winner ( (胜者胜者) )25*25*25*25*0808212108080808636325*25*212121212525494925*25*1616080863631616161616166363212125252525252525*25*25*25*第六趟：第六