数据结构课件10讲义.讲课稿.ppt

《数据结构课件10讲义.讲课稿.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课件10讲义.10.1概述10.2插入排序10.3快速排序10.4堆排序10.5归并排序10.6基数排序10.7各种排序方法的综合比较1、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,9710.1概述2、内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在

2、内存中完成，则称此类排序问题为外部排序。3、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区时间效率——排序速度（比较次数与移动次数）空间效率——占内存辅助空间的大小稳定性——A和B的关键字相等，排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。4.排序算法的好坏如何衡量？例如：将下列关键字序列52,49,97*,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,97*,97排序算法分类规则不同插入排序交换排序选择排序归并排

3、序时间复杂度不同简单排序O(n2)先进排序O(nlog2n)10.2插入排序基本思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。即边插入边排序，保证子序列中随时都是排好序的直接插入排序;折半插入排序;希尔排序有序序列R[1..i-1]R[i]无序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]无序序列R[i+1..n]直接插入排序利用“顺序查找”实现“在R[1..i-1]中查找R[i]的插入位置”直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个

4、记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】例（13，6，3，31，9，27，5，11）21254925*16080123456暂存21i=2i=3i=5i=4i=62525494

5、925*254925*49161625*08084921254925*21初态：164925*25211608完成!将序列存入顺序表L中，将L.r[0]作为哨兵（21，25，49，25*，16，08）*表示后一个25从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；R[0]=R[i];//设置“哨兵”循环结束表明R[i]的插入位置为j+1R[0]jR[i]for(j=i-1;R[0].key

6、动；for(j=i-1;R[0].key

7、ertSortL.r[0]=L.r[i];//复制为监视哨for(j=i-1;L.r[0].key

8、ey