chapter 8 内部排序

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

1、Chapter8Chapter8内部排序内部排序8.1引言8.2插入排序8.3选择排序8.4“交换”排序8.5归并排序8.6基数排序8.7各种内部排序方法的比较讨论本章重点：1.排序的定义，排序方法“稳定”或“不稳定”的含义。2.各类排序方法中性能先进的高效方法（希尔排序、堆排序、快速排序、归并排序及基数排序）的基本思想、算法特点、排序过程以及它们的时间和空间复杂度分析。本章难点：1.堆排序和快速排序。2.各种排序方法的时间复杂度的分析，注意从“关键字的比较次数”和“记录的移动次数”分析排序算法的平均情况和最坏情况的时间性能。8.18.1引言引言一、什么叫排序？

2、设含有n个记录的文件{R,R,…,R},其对应的关键01n-1字为{K,K,…,K}，将此n个记录按其关键字大小非递01n-1减（或非递增）的次序排列起来，成为一个有序的文件，这样一种运算称为排序（Sorting）。二、排序的类型内部排序外部排序三、稳定性例：15，18，10，18，70，13，44→10，13，15，18，18，44，70（稳定的）→10，13，15，18，18，44，70（不稳定的）稳定的排序方法有：插入（直接、折半）、归并、基数。不稳定的排序方法有：希尔、选择（直接选择、堆）、快速。如不作特别说明，本章算法中的记录类型均为如下定义的Data

3、Type类型，而且采用顺序表结构。typedefintKeyType;typedefstruct{KeyTypekey;/*关键字域*/…/*其它数据域*/}DataType;8.28.2插入排序插入排序一、直接插入排序（StraightInsertionSort）1.基本思想依次将每个记录插入到一个有序的子文件中去，插入后该文件仍是有序的。例：8,3,2,5,9,4,6假设前面几个记录已按关键字递增的次序有序：2,3,5,8,9现将4插入以得到一个新的有序文件，∵3<4<5∴应插在3与5之间，∴得到新的文件：2,3,4,5,8,9具体做法：先将文件中的第一个记

4、录看成是一个有序子文件，然后从第二个记录起逐个进行插入，直至整个文件变成按关键字非递减有序文件为止。直接插入排序也适合用单链表作存储结构。（即在线性表一章中提到的在单链表中进行就地排序的算法，只是在查找插入位置时，要从有序子文件的表头开始查找）。2.算法voidInsertSort(DataTypea[],intn)/*用直接插入排序法对a[0]~a[n-1]排序*/{inti,j;DataTypetemp;for(i=1;i

5、=0&&temp.keytemp.key的记录后移*/j--;}a[j+1]=temp;/*插入到正确位置*/}}例：初始关键字：8325946i=1：[8]325946jjii=2：[38]25946i=3：[238]5946i=4：[2358]946i=5：[23589]46i=6：[234589]6排序结果：[2345689]3.算法分析辅助空间：O(1)时间：(1)关键字的比较次数n−1最好(“正序”)：∑1=n−1i=1n−1n(n−1)最坏(“逆序”)：∑i=1+2+3+L+(n−1)=2i

6、=1取平均值：21n−n1212(+n−1)=(n+n−2)≈n2244(2)记录的移动次数开始时，将要插入的记录→temp，移动1次最后，将记录插入适当位置，即temp→a[j+1]，移动1次比较后，若temp.key

7、量排序”（DiminishingIncrementSort）。1.基本思想将整个文件分割成为若干个小组，各小组分别进行直接插入排序；小组的个数逐次减少，直至个数为1（此时，文件的记录达到基本有序，再进行一次直接插入排序就可得到有序文件）。注意：分割时，是按某个“增量”进行分组。“增量”的选择：希尔：d1=n/2,di+1=di/2都取奇数：如7,5,3,1d之间互素：如5,3,2,1i例：记录数n=8，进行希尔排序初始：465513429417570d=417551513第一趟排序结果：461754294551370d=22第二趟排序结果：5171342

8、46559470d=13