北邮数据结构排序课件

《数据结构与STL》

第八章

排序

北京邮电大学 信息与通信工程学院

第八章 排序学习内容： 1. 2. 3. 4. 5. 6. 7. 8.2013-12-11

概述 插入排序 交换排序 选择排序 归并排序 排序比较 外部排序 STL 中相关排序算法《数据结构与STL》 2

1 概述排序 给定一个记录序列，按照每个记录的关键码将 记录进行重新排列，使关键码从小到大/从大 到小有序。 正序：关键码从小到大排列 逆序：关键码从大到小排列

2013-12-11

《数据结构与STL》

1 概述趟 在排序算法中，将待排序的记录扫描一遍称为一 趟。

稳定性 待排序记录中具有相同关键码的记录，若排序前 后，这些记录的相对位置不变，则为稳定排序； 否则为不稳定。

2013-12-11

《数据结构与STL》

1 概述排序的分类 根据是否将全部记录放进内存，分为内部排序 和外部排序 根据排序的原则，可以将排序分成： 插入排序 交换排序 选择排序 归并排序

2013-12-11

《数据结构与STL》

1 概述如何评价一个排序算法？ 排序的基本操作:比较和移动 主要:比较的次数或移动次数较少的算法性能较好。 次要:空间复杂度. 算法本身的复杂度

2013-12-11

《数据结构与STL》

第八章 排序学习内容： 1. 2. 3. 4. 5. 6. 7. 8.2013-12-11

概述 插入排序 交换排序 选择排序 归并排序 排序比较 外部排序 STL 中相关排序算法《数据结构与STL》 7

插入排序主要内容 1.存储结构 2.直接插入排序 3.希尔排序

2013-12-11

《数据结构与STL》

1.存储结构排序使用顺序结构 为了关注排序算法本身，所以本章所有排序的存 储结构是0号位置留空的整型一维数组。

int r[n];

2013-12-11

《数据结构与STL》

2. 插入排序插入排序的特征 类似于玩纸牌时整理手中纸牌的过程。 寻找一个指定记录在待排序记录中的位置，然后 插入的排序算法。

2013-12-11

《数据结构与STL》

2.直接插入排序基本思想 每次将一个待排序的记录按其关键码的大小插入 到一个已经排序好的有序序列中，直到全部记录 排序好。插入到合适的位置 r1≤r2 ≤ ≤ ri-1 有序区 |ri ri+1 无序区 rn

2013-12-11

《数据结构与STL》

2.直接插入排序需要解决的问题 1)如何构造初始有序序列？ 2)如何找到插入的位置？

插入到合适的位置 r1≤r2 ≤ ≤ ri-1 |ri ri+1 rn

有序区

无序区

2013-12-11

《数据结构与STL》

1)如何构造初始有序序列？第一趟有序序列 r[2] 无序序列 r[3..n] r[1]

第二趟有序序列r[1..2] r[3] 无序序列 r[4..n]

第n-1趟有序序列r[1..n-1]2013-12-11 《数据结构与STL》

r[n]13

直接插入排序的过程初始序列第一趟

[12]15 9 20 10 31[12 15 ]9 20 10 31

2424

第二趟第三趟 第四趟 第五趟 第六趟2013-12-11

[9 12 15]20 10 31 24[9 12 15 20]10 31 24 24

[9 10 12 15 20] 31 [9 10 12 15 20 [9 10 12 15 20《数据结构与STL》

31] 24 24 31]14

2)如何找到插入的位置？基本思想 设置r[0]为“哨兵”,从后向前查找有序区，边 查找边后移，直到找到合适的位置，将r[0]插入。r[0]=r[i]; for (int j=i-1; r[0]<r[j]; j--) r[j+1] =r[j]; r[j+1] = r[0]; if (r[i]<r[i-1]){ r[0]=r[i]; for (int j=i-1; r[0]<r[j]; j--) r[j+1] =r[j]; r[j+1] = r[0]; } ri+1 无序区《数据结构与STL》 15

插入到合适的位置r1≤r2 ≤ ≤ ri-1 有序区2013-12-11

|ri

rn

2. 直接插入排序的算法void InsertSort(int r[], int n) //升序排列 { for (int i=2; i<=n; i++) //i从2~n循环，共n-1趟排序 { r[0]=r[i]; for (int j=i-1; r[0]<r[j]; j--) r[j+1] =r[j]; r[j+1] = r[0]; } }

2013-12-11

《数据结构与STL》