北邮数据结构排序课件培训讲学.ppt

《北邮数据结构排序课件培训讲学.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第八章排序北京邮电大学信息与通信工程学院《数据结构与STL》第八章排序学习内容：1.概述2.插入排序3.交换排序4.选择排序5.归并排序6.排序比较7.外部排序8.STL中相关排序算法2021/7/2821.概述《数据结构与STL》1概述排序给定一个记录序列，按照每个记录的关键码将记录进行重新排列，使关键码从小到大/从大到小有序。正序：关键码从小到大排列逆序：关键码从大到小排列2021/7/283《数据结构与STL》1概述趟在排序算法中，将待排序的记录扫描一遍称为一趟。稳定性待排序记录中具有相同关键码的记录，若排序

2、前后，这些记录的相对位置不变，则为稳定排序；否则为不稳定。2021/7/284《数据结构与STL》1概述排序的分类根据是否将全部记录放进内存，分为内部排序和外部排序根据排序的原则，可以将排序分成：插入排序交换排序选择排序归并排序2021/7/285《数据结构与STL》1概述如何评价一个排序算法？排序的基本操作:比较和移动主要:比较的次数或移动次数较少的算法性能较好。次要:空间复杂度.算法本身的复杂度2021/7/286《数据结构与STL》第八章排序学习内容：1.概述2.插入排序3.交换排序4.选择排序5.归并排序6

3、.排序比较7.外部排序8.STL中相关排序算法2021/7/2872.插入排序《数据结构与STL》插入排序主要内容1．存储结构2．直接插入排序3．希尔排序2021/7/288《数据结构与STL》1．存储结构排序使用顺序结构为了关注排序算法本身，所以本章所有排序的存储结构是0号位置留空的整型一维数组。intr[n];2021/7/289《数据结构与STL》2.插入排序插入排序的特征类似于玩纸牌时整理手中纸牌的过程。寻找一个指定记录在待排序记录中的位置，然后插入的排序算法。2021/7/2810《数据结构与STL》2.

4、直接插入排序基本思想每次将一个待排序的记录按其关键码的大小插入到一个已经排序好的有序序列中，直到全部记录排序好。2021/7/2811《数据结构与STL》r1≤r2≤……≤ri-1

5、riri+1……rn有序区无序区插入到合适的位置2.直接插入排序需要解决的问题1）如何构造初始有序序列？2）如何找到插入的位置？2021/7/2812《数据结构与STL》r1≤r2≤……≤ri-1

6、riri+1……rn有序区无序区插入到合适的位置1）如何构造初始有序序列？2021/7/2813有序序列r[1]无序序列r[3..n]r[2

7、]第一趟有序序列r[1..2]无序序列r[4..n]r[3]第二趟第n-1趟有序序列r[1..n-1]r[n]……《数据结构与STL》直接插入排序的过程2021/7/2814初始序列[12]15920103124第一趟[1215]920103124第二趟[91215]20103124第三趟[9121520]103124第四趟[910121520]3124第五趟[91012152031]24第六趟[9101215202431]《数据结构与STL》2）如何找到插入的位置？基本思想设置r[0]为“哨兵”，从后向前查找有序

8、区，边查找边后移，直到找到合适的位置，将r[0]插入。2021/7/2815r1≤r2≤……≤ri-1

9、riri+1……rn有序区无序区插入到合适的位置r[0]=r[i];for(intj=i-1;r[0]

10、tn)//升序排列{for(inti=2;i<=n;i++)//i从2~n循环，共n-1趟排序{r[0]=r[i];for(intj=i-1;r[0]

11、本有序的情况2021/7/2818《数据结构与STL》3.希尔排序希尔排序是对插入排序的一种改进,原因1)基本有序的序列，直接插入最快2)无序序列，记录数很少时，也很快基本思想将待排序的记录集分成多个子集，分别对这些子集进行排序，待整个序列基本有序时，在对记录进行一次直接插入排序。2021/7/2819《数据结构与STL》3.希尔排序2021/7/2820《