数据结构及算法排序

《数据结构及算法排序》由会员分享，可在线阅读，更多相关《数据结构及算法排序（116页珍藏版）》请在金锄头文库上搜索。

1、第八章 排序技术 本章的基本内容是： 排序的基本概念 插入排序 交换排序 选择排序 归并排序 8.1概 述 排序：将一组“无序”的记录序列,调整为按关键字“有序” 的记录序列. 学号姓名高数英语思想品德 0002王 军8588 0001李 明6492 0003汤晓影8586 68 72 78 1.排序的基本概念 排序：给定一组记录的集合r1, r2, , rn，其相应的关 键码分别为k1, k2, , kn，排序是将这些记录排列成顺 序为rs1, rs2, , rsn的一个序列，使得相应的关键码满 足非递减关系ks1ks2ksn（称为升序）或非递增关系 ks1ks2ksn（称为降序）。 1.排

2、序的基本概念 学号姓名高数英语 0002李 明64 0001王 军85 0003汤晓影85 72 68 78 学号姓名高数英语 0001王 军85 0002李 明64 0003汤晓影85 68 72 78 8.1概 述 假定在待排序的记录集中，存在多 个具有相同键值的记录，若经过排序，这些记录的相 对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之 前，而在排序后的序列中，ri一定在rj之前，则称这种 排序算法是稳定的；否则称为不稳定的。 学号姓名高数英语思想品德 0001王 军8588 0002李 明6492 0003汤晓影8586 68 72 78 排序算法的稳定性： 8.1概 述

3、 1.排序的基本概念 待排序序列中的记录已按关键码排好序。 待排序序列中记录的排列顺序与排好 序的顺序正好相反。 学号姓名高数英语思想品德 0001王 军8588 0002李 明6492 0003汤晓影8586 68 72 78 8.1概 述 1.排序的基本概念 正序： 逆序（反序）： 排序的分类 在排序的整个过程中，待排序的所有记录 全部被放置在内存中,不需要访问外存 由于待排序的记录个数太多，不能同时放 置在内存，而需要将一部分记录放置在内存，另一部 分记录放置在外存上，整个排序过程需要在内外存之 间多次交换数据才能得到排序的结果。 8.1概 述 1.排序的基本概念 1.内排序： 2.外排

4、序： 2.内排序算法 1. 插入排序 2. 交换排序 3. 选择排序 4. 归并排序 直接插入排序 希尔排序 冒泡排序 快速排序 简单选择排序 堆排序 8.1概 述 排序基本过程:是一个逐步扩大记录的有序序列长度 的过程 3.排序的基本过程 有序序列区无序序列区 有序序列区无序序列区 一趟排序 一趟排序:将无序序列区里一个或几个记录合并到有序序列的 过程为一趟排序，有序序列长度增加1个或几个 8.1概 述 4.排序算法的存储结构 从操作角度看，排序是线性结构的一种操作，待排序 记录可以用顺序存储结构或链接存储结构存储。 假定2：将待排序的记录序列排序为升序序列。 rn+1 假定1：待排序记录采

5、用顺序存储结构，关键码为整 型，且记录只有关键码一个数据项。 8.1概 述 10 15 24 6 12 35 40 98 0 1 2 3 4 5 6 7 8 内排序算法 1. 插入排序 2. 交换排序 3. 选择排序 4. 归并排序 直接插入排序 希尔排序 冒泡排序 快速排序 简单选择排序 堆排序 8.1概 述 8.2插入排序 插入排序的主要操作是插入，其基本思想是： 每次将一个待排序的记录按其关键码的大小插 入到一个已经排好序的有序序列中，直到全部 记录排好序为止。 举例: 有序序列 2 , 待排序记录 3,6,1 1）直接插入排序 2）希尔排序 基本思想：在插入第 i（i1）个记录时，前面

6、的 i-1 个记录已经排好序。 8.2.1直接插入排序 有序序列无序序列 r r 1 r r 2 r r i-1 r r i r r n r r i+1 r r 1 r r 2 r r i-1 r r i r r n r r i+1 有序序列 无序序列 8.2插入排序 直接插入排序过程示例直接插入排序过程示例 r 0 1 2 3 4 5 6 2121181825252222101025*25* 2121 第一趟18182222101025*25*2525 252522222121 2525222221211010 2525* *2525222221211010 2525* *252522222

7、12118181010 1818101025*25* 第二趟 1818 第四趟 18182525* * 第三趟 第五趟 算法稳定吗？ 2121 算法思想？ i从第2个数到第n个数 将第i个数插入到有序序列中的 合理位置 8.2插入排序 共多少趟？ 对于ri，如何查找它的插入位置?如何实现插入？ 直接插入排序 需解决的关键问题? 无序序列 20202525212118182626 1)将ri暂存在r0 2) j=i-1；/从第i-1记录开始查找 3)当rjr0时，循环做 rj后移一个位置,j- 4)rj+1=r0 /将r0插入到位置j+1 2222 0 1 2 3 4 5 2121 ij 252

8、5 j 2222 j 2121 8.2插入排序 直接插入排序 无序序列 202025251010181825252222 0 1 2 3 4 5 1010 ij 2525222220201010 j r0的作用? 暂存单元, 监视哨 对于ri，如何查找它的插入位置?如何实现插入？ 需解决的关键问题? 1)将ri暂存在r0 2) j=i-1；/从第i-1记录开始查找 3)当rjr0时，循环做 rj后移一个位置,j- 4)rj+1=r0 /将r0插入到位置j+1 jj 8.2插入排序 void insertSort (int r , int n) for (i=2; i=n; i+) r0=ri;

9、 for(j=i-1; r0r0时，循环做： rj后移一个位置,j- 1.4 rj+1=r0 8.2插入排序 直接插入排序过程示例直接插入排序过程示例 r 0 1 2 3 4 5 6 2121181825252222101025*25* 2121 21212525 i = 218182222101025*25*2525 i = 318182222101025*25*2222 2525222221211010 252522222121101025 25 2525* *2525222221211010 2525* *25252222212118181010 1818 1818101025*25*i

10、 = 4 1818 i = 6 18182525* * i = 5 2525 2121 8.2插入排序 直接插入排序练习直接插入排序练习 12 5 9 20 6 31 24 8.2插入排序 直接插入排序练习直接插入排序练习 12 5 9 20 6 31 24 初始序列 5 12 9 20 6 31 24 第一趟 5 9 12 20 6 31 24 第二趟 5 9 12 20 6 31 24 第三趟 5 6 9 12 20 31 24 第四趟 第五趟 5 6 9 12 20 31 24 第六趟 5 6 9 12 20 24 31 8.2插入排序 1. 基本操作。内排序在排序过程中的基本操作： 比

11、较：关键码之间的比较； 移动：记录从一个位置移动到另一个位置。 2. 辅助存储空间。 辅助存储空间是指在数据规模一定的条件下，除了存 放待排序记录占用的存储空间之外，执行算法所需要 的其他存储空间。 3.算法本身的复杂程度。 排序算法的性能 8.2插入排序 直接插入排序算法性能分析 最好情况下： 1 1 2 2 3 3 4 4 5 5 时间复杂度为O(n)。 比较次数：n-1 移动次数：2(n-1) 1 1 2 2 3 3 4 4 5 5 2 2 1 1 2 2 3 3 4 4 5 5 3 3 1 1 2 2 3 3 4 4 5 5 4 4 1 1 2 2 3 3 4 4 5 5 5 5 （正

12、序） 8.2插入排序 直接插入排序算法性能分析 最好情况下（正序）： 比较次数：n-1 移动次数：2(n-1) 最坏情况下（逆序）： 时间复杂度为O(n2)。 5 5 4 4 3 3 2 2 1 1 4 4 5 5 3 3 2 2 1 1 4 4 3 3 4 4 5 5 2 2 1 1 3 3 2 2 3 3 4 4 5 5 1 1 2 2 1 1 2 2 3 3 4 4 5 5 1 1 比较次数： 移动次数： 2 ) 1)(2( 2 -+ = = nn i n i 2 ) 1)(4( 1 -+ =+ nn i n 2=i ）（ 时间复杂度为O(n)。 8.2插入排序 平均情况下（随机排列）：

13、 直接插入排序算法性能分析 时间复杂度为O(n2)。 比较次数： 移动次数： 4 ) 1)(4(-+ = nn n 2=i 4 ) 1)(2( 2 -+ = = nn n i i 2 （ 2 1+i ） 8.2插入排序 空间性能：需要一个记录的辅助空间。 直接插入排序算法是一种稳定的排序算法。 直接插入排序算法性能分析 直接插入排序算法简单、容易实现，适用于待排序 记录基本有序或待排序记录较小时。 当待排序的记录个数较多时，大量的比较和移动操 作使直接插入排序算法的效率降低。 8.2插入排序 8.2.2希尔排序 改进的着眼点： （1）由于直接插入排序算法简单，在待排序记录数 量n较小时效率也很

14、高。 （2）若待排序记录按关键码基本有序时，直接插入 排序的效率可以大大提高； 2 2 1 1 3 3 5 5 4 4 3 3 2 2 1 1 8.2插入排序 （1）应如何分割待排序记录，才能保证整个序列逐步 向基本有序发展？ （2）子序列内如何进行直接插入排序？ 需解决的关键问题? 基本思想：将整个待排序记录分割成若干个子序列， 在子序列内分别进行直接插入排序，待整个序列中的 记录基本有序时，对全体记录进行直接插入排序。 8.2.2希尔排序 20 18 19 ,6 5 7, 1 3 220 18 19 6 5 7 1 3 2 8.2插入排序 8.2.2希尔排序 子序列的构成不能是简单地“逐段分割”，而是将相 距某个“增量”的记录组成一个子序列。 逐渐缩短“增量”，当缩短为1时就是对全体记录进 行排序。 1010 2 2 6 6 1515 9 9 1 1 8 8 2020 4 4 1111 1010 2 2 6 6 1515 9 9 1 1 8 8 2020 4 4 1111 d=3 基本思想：将整个待排序记录分割成若干个子序列， 在子序列内分别进行直接插入排序，待整个序列中的 记录基本有序时，对全体记录进行直接插入排序。 8.2插入排序 希尔插入排序过程示例 1 2 3 4 5 6 7 8 9 404021