《数据结构域算法设计ch10 内部排序》由会员分享，可在线阅读，更多相关《数据结构域算法设计ch10 内部排序（59页珍藏版）》请在金锄头文库上搜索。
1、第10章 内部排序,10.1 排序简介 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种排序方法的比较,本章知识点和要求,各种排序方法的特点并能灵活应用（掌握） 各种方法的排序过程（掌握） 各种排序方法的时间复杂度分析（掌握）,10.1 排序简介,排序(sorting)又称分类，意指把一批杂乱无章的数据序列重新排列成有序序列。 排序是程序设计中一种重要运算。在很多领域中有广泛的应用。譬如，在查找时，若文件的记录按关键字预先排好顺序，可以采用折半查找方法提高查找效率。折半查找的平均查找长度数量级为O(logn)，而顺序查找的平均查
2、找长度数量级为O(n)。又如，建立二叉排序树的过程本身就是一个排序过程。日常生活中的各类竞赛活动，如歌唱大奖赛等，还有各种升学考试录取工作均离不开排序。,10.1 排序简介,关键字 是数据元素中的某个数据项。如果某个数据项可以唯一地确定一个数据元素，就将其称为主关键字；否则，称为次关键字。 排序 将数据元素的任意序列,重新调整为一个按关键字排列有序的序列. 如:有数据元素序列(r1,r2,r3,r4,r5,r6,r7)其对应关键字值为:(5, 4, 8, 6, 9, 1,21);按关键字非递减排列得新的数据元数排列(r6,r2,r1,r4,r3,r5,r7)的操作.,10.1 排序简介,一般情
3、况下: 假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 Kp1Kp2Kpn 按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。,排序算法的稳定性 如果在待排序的记录序列中有多个数据元素的关键字值相同，经过排序后，这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，否则称之为不稳定的。 内部排序与外部排序 根据在排序过程中待排序的所有数据元素是否全部被放置在内存中，可将排序方法分为内部排序和外部排序两大类。 内部排序是指在排序的整个过程中，待排序
4、的所有数据元素全部被放置在内存中； 外部排序是指由于待排序的数据元素个数太多，不能同时放置在内存，而需要将一部分数据元素放置在内存，另一部分数据元素放置在外设上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。,排序的基本方法 内部排序主要有5种方法：插入、交换、选择、归并和基数。 一趟: 在排序过程中，基本动作执行一次。 排序算法的效率 评价排序算法的效率主要有两点： 一是在数据量规模一定的条件下，算法执行所消耗的平均时间，对于排序操作，时间主要消耗在关键字之间的比较和数据元素的移动上，因此我们可以认为高效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动次数； 二是执
5、行算法所需要的辅助存储空间，辅助存储空间是指在数据量规模一定的条件下，除了存放待排序数据元素占用的存储空间之外，执行算法所需要的其他存储空间，理想的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无关。,10. 2 插 入 排 序,插入排序的思路 不断地将待排序的数值插入到有序段(序列)中，使有序段(序列)逐渐扩大，直至所有数值都进入有序段中位置。 直接插入排序 折半插入排序 希尔排序,直接插入排序 首先将待排序记录序列中的第一个记录作为一个有序段; 将记录序列中的第二个记录插入到上述有序段中形成由两个记录组成的有序段; 再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的
6、有序段; 依此类推，每一趟都是将一个记录插入到前面的有序段中，假设当前欲处理第i个记录，则应该将这个记录插入到由前i-1个记录组成的有序段中，从而形成一个由i个记录组成的按关键字值排列的有序序列，直到所有记录都插入到有序段中。 一共需要经过n-1趟就可以将初始序列的n个记录重新排列成按关键字值大小排列的有序序列。,例,49 38 65 97 76 13 27,i=2 38 (38 49) 65 97 76 13 27,i=3 65 (38 49 65) 97 76 13 27,i=4 97 (38 49 65 97) 76 13 27,i=5 76 (38 49 65 76 97) 13 27
7、,i=6 13 (13 38 49 65 76 97) 27,( ),i=7 (13 38 49 65 76 97) 27,27,97,76,65,49,38,27,0 1 2 3 4 5 6 7,算法评价 时间复杂度 若待排序记录按关键字从小到大排列(正序),记录移动次数： 0,关键字比较次数：,关键字比较次数：,记录移动次数：,若待排序记录按关键字从大到小排列(逆序),若待排序记录是随机的，取平均值 关键字比较次数：,记录移动次数：,T(n)=O(n),空间复杂度：S(n)=O(1),折半插入排序 思想：用折半查找方法确定插入位置的排序叫,例,i=1 (30) 13 70 85 39 42
8、 6 20,i=2 13 (13 30) 70 85 39 42 6 20,i=7 6 (6 13 30 39 42 70 85 ) 20,.,i=8 20 (6 13 20 30 39 42 70 85 ),从上述过程可以看出:折半插入排序仅减少了关键字之间的比较次数,而记录的移动次数不变.,算法评价 时间复杂度：T(n)=O(n) 空间复杂度：S(n)=O(1),希尔排序(缩小增量法 Shells Sort) 排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止,算法描述,#d
9、efine T 3 int d=5,3,1;,49,13,38,27,27,4,55,38,65,48,97,55,76,4,1 2 3 4 5 6 7 8 9 10,1 2 3 4 5 6 7 8 9 10,1 2 3 4 5 6 7 8 9 10,希尔排序特点 子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列 希尔排序可提高排序速度，因为 分组后n值减小，n更小，而T(n)=O(n),所以T(n)从总体上看是减小了 关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序 增量序列取法 没有除1以外的公因子 最后一个增量值必须为1,作 业,1
10、.习题册 第9章习题2,4(1)(2) 2.有一随机数25,84,21,46,13,27,68,35,20,23,11,12采用希尔排序方法对它们排序，写出每趟排序的过程。其中di =di-1/2, d0=7,2.在执行某种排序算法的过程中出现了排序的关键字朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ 2.答：这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4，3，2，1起泡排序就可否定本题结论。 4.试问：对于初始状态如下的各个序列（长度为n）进行直接插入
11、排序时，至多需要进行多少次关键字间的比较（要求按照正序排序）？ (1)关键字按照升序有序； (2)关键字按照逆序有序； (1)n-1；(2)(n+2)(n-1)/2；,10.3 交换排序 冒泡排序 排序过程 将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r1.keyr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止,例,3
12、8,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,1 2 3 4 5 6 7 8,算法描述,算法评价 时间复杂度 最好情况（正序） 比较次数：n-1 移动次数：0 最坏情况（逆序） 比较次数：,移动次数：,空间复杂度：S(n)=O(1),T(n)=O(n),快速排序 快速排序由霍尔(Hoare)提出，它是一种对冒泡排序的改进。由于其排序速度快，因此称快速排序(quick sort)。 基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中
13、一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序,排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs，x=rp.key 初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换 重复上述两步，直至i=j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止,完成一趟排序： ( 27 38 13) 49 (76 97 65 50),分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76
14、 (97),快速排序结束： 13 27 38 49 50 65 76 97,49,27,49,65,13,49,49,97,作 业,1.习题册 第9章习题10题 2.有一随机数25,84,21,46,13,27,68,35,20采用冒泡排序和快速排序方法对它们排序，写出每趟排序的过程 习题10.有一随机数25,84,21,46,13,27,68,35,20,现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么? 初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84 第二趟:13,20,21,25,35,27
15、,46,68,84 第三趟:13,20,21,25,27,35,46,68,84 该排序方法为快速排序。,10.4 选择排序 10.4.1 简单选择排序 排序过程 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换 重复上述操作，共进行n-1趟排序后，排序结束,例,初始： 49 38 65 97 76 13 27 ,i=1,13,49,一趟： 13 38 65 97 76 49 27 ,i=2,27,38,六趟： 13 27 38 49 65 76 97 ,排序结束： 13 27 38 49 65 76 97,算法评价 时间复杂度 记录移动次数 最好情况：0 最坏情况：3(n-1) 比较次数：,空间复杂度：S(n)=O(1),T(n)=O(n),10.4.3 堆排序 堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆,例 （96，83，27，
