chapter10-Sort

《chapter10-Sort》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第10章内部排序授课教师：胡平计算机科学与工程系，20092021/9/71条件1：记录必须以顺序结构存储条件2：记录必须有序折半查找的条件high=9low=1mid=5查找“4”2021/9/72【目的】：理解各种排序算法的算法思想，能用它们求解现实生活中与排序有关的问题。【内容】：排序的有关概念、分类、直接插入排序、希尔排序、快速排序、归并排序的算法思想、描述，以及效率和稳定性。【重点】：上述4种排序方法的算法思想。【难点】：希尔排序、归并排序的算法思想。关于本讲2021/9/73排序：将若干记录按关键字以非递减（或非递增）的顺序

2、进行排列的操作。正序：记录按关键字以非递减顺序排列。逆序：记录按关键字以非递增顺序排列。稳定性：对任一序列，若序列中关键字相同的记录的先后关系在排序前后总一致，则该排序算法是稳定的。反之，则为不稳定的。有关的概念2，3，2，1排序算法A1，2，2，32，3，2，1排序算法B1，2，2，3(A不稳定)(尚不能判断B是否稳定)1，2，2，33，2，2，12021/9/74排序方法的分类内部排序：排序方法待排序的记录全部存放在内存中。外部排序：待排序的记录部分存放在外存中。插入排序快速排序选择排序归并排序基数排序2021/9/75直接插入排序

3、的算法思想打扑克(不计花色)：右手每起一张牌，按牌面大小插入到左手已有序的若干张牌中的合适位置，直至所有的牌起完。对{R1,R2,…,Ri,…,Rn}进行直接插入排序：每次将一个记录插入到当前已有序的子序列(即有序区)，直至所有记录插入完毕。将Ri插入到有序区的操作称为第i趟直接插入。抽象2021/9/76直接插入排序的算法思想开始结束将Ri插入到{R1…Ri-1}i2ii+1否是i≤n?待排序列i=2i=3i=4有序区无序区第i趟直接插入的关键是：在有序区{R1…Ri-1}中，找到Ri的插入位置。12342021/9/77第i趟直

4、接插入开始结束Ri

5、数//多个记录构成的顺序表2021/9/710直接插入排序算法的类C描述ji-1否Ri放在j+1位置开始是i≤n?i2Ri

6、].key;2021/9/711算法小结直接插入排序由若干趟组成。每一趟的关键是在有序区中找到待插入记录的插入位置。r[0]的作用：暂存r[i]、哨兵。算法的时空复杂度及稳定性。2021/9/712希尔排序的算法思想算法思想：将待排序记录分成若干组，分别对每组进行插入排序；继续进行分组和插入排序，直至所有记录“基本有序”；最后，做一次直接插入排序。改进的地方：依然基于“插入”的思想，但比较过程中，记录是“跳跃式”地挪动，从而减少算法总的比较次数。2021/9/713希尔排序的算法思想d1=5d2=3d3=1第一趟排序第二趟第三趟2021

7、/9/714希尔排序算法演示【观看演示】2021/9/715希尔排序的算法思想选取一个正整数di(增量)，将记录分成若干组，然后对所有组进行插入排序的操作，称为“一趟(增量为di)希尔排序”。每一趟希尔排序所选取的增量(它们组成增量序列)是依次递减的，且最后一个增量一定是1，故希尔排序又称为“缩小增量排序”。2021/9/716希尔排序的算法思想开始结束以di为增量做第i趟希尔排序i1ii+1否是i≤k?整个算法的关键是每一趟希尔排序。增量序列：D={d1,d2,…,dk-1,dk}当i>j时，di

8、717一趟增量为d的希尔排序设d=3ji-d否Ri放在j+d位置id+1开始j>0且Ri