《数据结构(第9章)讲述》由会员分享，可在线阅读，更多相关《数据结构(第9章)讲述（83页珍藏版）》请在金锄头文库上搜索。
1、第九章 排序 教学内容教学内容 10.110.1 基本概念基本概念 10.210.2 插入排序插入排序 10.310.3 交换排序交换排序 10.410.4 选择排序选择排序 10.510.5 二路归并排序二路归并排序 10.610.6 基数排序基数排序 10.710.7 外排序外排序 教学目的及要求教学目的及要求 领会排序的基本思想和基本概念；领会排序的基本思想和基本概念； 理解并掌握插入排序、冒泡排序、快速排序、直接理解并掌握插入排序、冒泡排序、快速排序、直接 选择排序、堆排序、归并排序和基数排序的基本思想选择排序、堆排序、归并排序和基数排序的基本思想 、步骤、算法及时空效率分析；、步骤、
2、算法及时空效率分析； 了解外排序的定义和基本方法。了解外排序的定义和基本方法。 3 3、教学重点、教学重点 排序基本概念及内排序和外排序、排序基本概念及内排序和外排序、稳稳稳稳定排序和非定排序和非稳稳稳稳 定排序的区定排序的区别别别别； 插入排序的基本思想、基本步插入排序的基本思想、基本步骤骤骤骤和算法；和算法； 冒泡排序的基本思想、基本步冒泡排序的基本思想、基本步骤骤骤骤、算法和算法分析；、算法和算法分析； 快速排序的基本思想、基本步快速排序的基本思想、基本步骤骤骤骤和算法；和算法； 直接直接选择选择选择选择 排序的基本思想、基本步排序的基本思想、基本步骤骤骤骤、算法和算法、算法和算法 分析
3、；分析； 堆排序的基本思想、基本步堆排序的基本思想、基本步骤骤骤骤和算法；和算法； 归归归归并排序的思想；并排序的思想； 两个有序文件合并的方法和算法；两个有序文件合并的方法和算法； 二路二路归归归归并排序的算法和并排序的算法和时时时时空性能空性能 4 4、教学难点、教学难点 快速排序算法；快速排序算法； 堆排序方法堆排序方法 10.1 10.1 基本概念基本概念 排序排序(Sorting)(Sorting)是计算机程序设计中的一种重要是计算机程序设计中的一种重要 操作，其功能是对一个数据元素集合或序列重新排列操作，其功能是对一个数据元素集合或序列重新排列 成一个按数据元素某个项值有序的序列。
4、作为排序依成一个按数据元素某个项值有序的序列。作为排序依 据的数据项称为据的数据项称为“排序码排序码”，也即数据元素的关键码，也即数据元素的关键码 。为了便于查找，通常希望计算机中的数据表是按关。为了便于查找，通常希望计算机中的数据表是按关 键码有序的。如有序表的折半查找，查找效率较高。键码有序的。如有序表的折半查找，查找效率较高。 二叉排序树、二叉排序树、B-B-树和树和B+B+树的构造过程就是一个排序过树的构造过程就是一个排序过 程。若关键码是主关键码，则对于任意待排序序列，程。若关键码是主关键码，则对于任意待排序序列， 经排序后得到的结果是唯一的；若关键码是次关键码经排序后得到的结果是唯
5、一的；若关键码是次关键码 ，排序结果可能不唯一，这是因为具有相同关键码的，排序结果可能不唯一，这是因为具有相同关键码的 数据元素，这些元素在排序结果中，它们之间的的位数据元素，这些元素在排序结果中，它们之间的的位 置关系与排序前不能保持。置关系与排序前不能保持。 若对任意的数据元素序列，使用某个排序方法若对任意的数据元素序列，使用某个排序方法 ，对它按关键码进行排序：若相同关键码元素间的，对它按关键码进行排序：若相同关键码元素间的 位置关系，排序前与排序后保持一致，称此排序方位置关系，排序前与排序后保持一致，称此排序方 法是法是稳定的稳定的；而不能保持一致的排序方法则称为；而不能保持一致的排序
6、方法则称为不不 稳定稳定的。的。 排序分为两类：排序分为两类：内排序内排序和和外排序外排序。 内排序内排序：指待排序列完全存放在内存中所进行：指待排序列完全存放在内存中所进行 的排序过程，适合不太大的元素序列。的排序过程，适合不太大的元素序列。 外排序外排序：指排序过程中还需访问外存储器，足：指排序过程中还需访问外存储器，足 够大的元素序列，因不能完全放入内存，只能使用够大的元素序列，因不能完全放入内存，只能使用 外排序。外排序。 10.2 插入排序 10.2.1 直接插入排序 设有n个记录，存放在数组r中，重新安排记录 在数组中的存放顺序，使得按关键码有序。即 r1.keyr2.keyrn.
7、key 先来看看向有序表中插入一个记录的方法： 设rlow; /*/*以子表的第一个记录作为支点记录以子表的第一个记录作为支点记录* */ / pivotkeypivotkey= =tbltbl-rlow.key; -rlow.key; /*/*取支点记录关键码取支点记录关键码* */ / while(low=-rhigh.key=pivotkeypivotkey) high-;) high-; tbltbl-rlow=-rlow=tbltbl-rhigh; -rhigh; /*/*将比支点记录小的交换到低端将比支点记录小的交换到低端* */ / while(lowrlow=tbltbl-rh
8、igh; -rhigh; /*/*将比支点记录大的交换到低端将比支点记录大的交换到低端* */ / tbltbl-rlow=-rlow=tbltbl-r0; -r0; /*/*支点记录到位支点记录到位* */ / return low; return low; /*/*反回支点记录所在位置反回支点记录所在位置* */ / 【例例10.510.5】一趟快排序过程示例一趟快排序过程示例 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 存储单元存储单元 49 14 38 74 96 65 8 49 14 38 74 96 6
9、5 8 4949 55 27 55 27 记录中关键码记录中关键码 low=1low=1；high=10high=10； 设置两个搜索指针，设置两个搜索指针， r0=rlowr0=rlow； 支点记支点记 录送辅助单元，录送辅助单元， 14 38 74 96 65 8 14 38 74 96 65 8 4949 55 27 55 27 low high low high 第一次搜索交换第一次搜索交换 从从highhigh向前搜索小于向前搜索小于r0.keyr0.key的记录，得到结果的记录，得到结果 27 14 38 74 96 65 8 27 14 38 74 96 65 8 4949 55
10、 55 low high low high 从从lowlow向后搜索大于向后搜索大于r0.keyr0.key的记录，得到结果的记录，得到结果 27 14 38 96 65 8 27 14 38 96 65 8 4949 55 74 55 74 low high low high 第二次搜索交换第二次搜索交换 从从highhigh向前搜索小于向前搜索小于r0.keyr0.key的记录，得到结果的记录，得到结果 27 14 38 8 96 65 27 14 38 8 96 65 4949 55 74 55 74 low high low high 从从lowlow向后搜索大于向后搜索大于r0.ke
11、yr0.key的记录，得到结果的记录，得到结果 27 14 38 8 65 96 27 14 38 8 65 96 4949 55 74 55 74 low high low high 第三次搜索交换第三次搜索交换 从从highhigh向前搜索小于向前搜索小于r0.keyr0.key的记录，得到结果的记录，得到结果 27 14 38 8 65 96 27 14 38 8 65 96 4949 55 74 55 74 low high low high 从从lowlow向后搜索大于向后搜索大于r0.keyr0.key的记录，得到结果的记录，得到结果 27 14 38 8 65 96 27 14
12、38 8 65 96 4949 55 74 55 74 low high low high low=highlow=high，划分结束，填入支点记录划分结束，填入支点记录 27 14 38 8 49 65 96 27 14 38 8 49 65 96 4949 55 74 55 74 【算法算法10.810.8】 void void QSort(S_TBLQSort(S_TBL * *tbl,inttbl,int low,intlow,int high) /* high) /*递归形式的快排序递归形式的快排序* */ / /* /*对顺序表对顺序表tbltbl中的子序列中的子序列tbltbl-
13、low-lowhighhigh作快排序作快排序* */ / if(lowif(s-elemt.keyelemt.keys-s-elemj.keyelemj.key) ) t=jt=j； /* /* t t中存放关键码最小记录中存放关键码最小记录 的下标的下标 * */ / s-s-elemtelemts-s-elemielemi ； /* /* 关键码最小的记录与第关键码最小的记录与第i i个个 记录交换记录交换 * */ / 从程序中可看出，简单选择排序移动记录的次数较少，从程序中可看出，简单选择排序移动记录的次数较少， 但关键码的比较次数依然是但关键码的比较次数依然是 (n*(n+1)/2(n*(n+1)/2，所以时间复杂度仍所以时间复杂度仍 为为O(nO(n 2 2 ) )。 10.4.210.4.2树形选择排序树形选择排序 按照
