数据结构课件非常详细 ch9.ppt

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

1、第十章排序排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序按排序所需工作量简单的排序方法：T(n)=O(n²)先进的排序方法：T(n)=O(n*logn)基数排序：T(n)=O(d*n)排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置10.1插入排

2、序直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序算法描述例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果：算法评价时间复杂度若待

3、排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：若待排序记录是随机的，取平均值关键字比较次数：记录移动次数：T(n)=O(n²)空间复杂度：S(n)=O(1)Ch8_1.c折半插入排序排序过程：用折半查找方法确定插入位置的排序叫~例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20sjmi=820(6133039427085)20

4、sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)算法描述算法评价时间复杂度：T(n)=O(n²)空间复杂度：S(n)=O(1)Ch8_2.c2-路插入排序目的减少移动记录次数（约为n2/8)使用DS：辅助向量：d[1．．n],指针：first和final(当前最小和最大值位置）思想：将d[1]视为有序文件的中间记录，并将待插入记录r[ｉ]．key与d[1]．key进行比较若r[ｉ]．key＜d[1]．key:则将r[ｉ]插入到d[first]~

5、d[1]之间。若r[ｉ]．key≥d[1]．key:则将r[ｉ]插入到d[1]~d[final]之间。例如：49，38，65，97，76，13，27，49i=149firstfinali=24938finalfirsti=3496538finalfirsti=449659738finalfirst．．．d[1]d[2]………………………………..…d[n]finalfirst希尔排序(缩小增量法)1基本思想：分割成若干个较小的子文件，对各个子文件分别进行直接插入排序，当文件达到基本有序时，再对整个文件进行一次直接插入排序。2依据：⑴若待排序文

6、件"基本有序"，即文件中具有特性：r[i].key＜Max{r[j].key}1≤j＜i的记录数较少，则文件中大多数记录都不需要进行插入。⑵基本有序时，直接插入排序效率可以提高，接近于O(n)。3排序过程：先取一个正整数d1

7、938659776二趟排序：1344838274955659776取d1=5一趟分组：4938659776132748554取d2=3二趟分组：1327485544938659776算法描述Ch8_3.c例4938659776132748554#defineT3intd[]={5,3,1};ji49133827一趟排序：1327485544938659776jiji274jiji5538jijiji二趟排序：1344838274955659776jiji6548ji9755ji764希尔排序特点子序列的构成不是简单的“逐段分割”，而是将相隔某

8、个增量的记录组成一个子序列希尔排序可提高排序速度，因为分组后n值减小，n²更小，而T(n)=O(n²),所以T(n)从总体上看是减小了关键字较小的记录跳跃式前移，在