第10章 内部排序.ppt

《第10章 内部排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章内部排序10.1概述10.2插入排序10.2.1直接插入排序10.2.2折半插入排序10.2.3shell排序10.3交换排序（快速排序）10.4选择排序10.4.1简单选择排序10.4.3堆排序10.5归并排序10.6基数排序10.7各种排序方法的比较讨论学习要点理解排序的定义和各种排序方法的特点；了解各种方法的排序过程及其依据的原则；理解“稳定”或“不稳定”的含义；排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行

2、访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序10.1概述按排序所需工作量简单的排序方法：T(n)=O(n²)先进的排序方法：T(n)=O(logn)基数排序：T(n)=O(d.n)排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置稳定排序与不稳定排序关键码相同的数据对象在排序过程中是否保持前后次序不变。如2,2*,1，排序后若为1,2*,2则该排序方法是不稳定的。10.2插入排序直接插入排序:整个排序过程为n-1趟插入，

3、即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序例：序列为{49，38，65，97，76，13，27，49}{(49)，38，65，97，76，13，27，49}(38){(38，49)，65，97，76，13，27，49}(65){(38，49，65)，97，76，13，27，49}(97){(38，49，65，97)，76，13，27，49}(76){(38，49，65，76，97)，13，27，49}(13){(13，38，49，65，76，97)，27，49}(27){(13，27，38，4

4、9，65，76，97)，49}(49){(13，27，38，49，49，65，76，97)}直接插入排序的算法VoidInsertSort(SqList&L){for(i=2;i

5、入正确位置}}InsertSort算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：若待排序记录是随机的，取平均值关键字比较次数：记录移动次数：T(n)=O(n²)空间复杂度：S(n)=O(1)直接插入排序的稳定性直接插入排序是一种稳定的排序方法。原理：关键码相同的两个对象，在整个排序过程中，不会通过比较而相互交换。折半插入排序排序过程：用折半查找方法确定插入位置的排序叫~例i=1(30)1370853942620i=213(1330)70

6、853942620i=76(6133039427085)20…...i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)VoidBInsertSort(SqList&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];（将L.r[i]暂存到L.r[0]）low=1;high=i–1;while(low<=high){（在子表中查

7、找插入位置）m=(low+high)/2;ifLT(L.r[0].key,L.r[m].key)high=m-1;（插入点在低半区）elselow=m+1;（插入点在高半区）}whilefor(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];（记录后移）L.r[high+1]=L.r[0];（插入记录）}//for}时间复杂度：T(n)=O(n²)空间复杂度：S(n)=O(1)折半插入排序的稳定性折半插入排序是一种稳定的排序方法。原理：关键码相同的两个对象，在整个排序过程中，不会通过比较而相互交换。希尔排序(缩小增量法)它

8、属于插入排序类的方法。它的基本思想是：先将整个待排序的记录分割成若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序“时，再对全