欢迎来到天天文库
浏览记录
ID:52449472
大小:983.50 KB
页数:54页
时间:2020-04-07
《排序——将一个数据元素(或记录)的任意序列,重新排列成.ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库。
1、第九章排序7/22/2021排序——将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。排序分类按待排序记录所在位置内部排序:待排序记录存放在内存外部排序:排序过程中需对外存进行访问的排序按排序依据原则插入排序:直接插入排序、折半插入排序、希尔排序交换排序:冒泡排序、快速排序选择排序:简单选择排序、堆排序归并排序:2-路归并排序基数排序7/22/2021按排序所需工作量简单的排序方法:T(n)=O(n²)先进的排序方法:T(n)=O(logn)基数排序:T(n)=O(d.n)排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置稳定排序:具有相同排序码的记录,排序前后
2、的相对位置保持不变。不稳定排序7/22/20219.1插入排序直接插入排序排序过程:整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序算法描述7/22/2021typedefstruct{intkey;floatinfo;}JD;voidstraisort(JDr[],intn){inti,j;for(i=2;i<=n;i++){r[0]=r[i];j=i-1;while(r[0].key3、327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果:7/22/2021算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数:记录移动次数:若待排序记录按关键字从大到小排列(逆序)关键字比较次数:记录移动次数:若待排序记录是随机的,取平均值关键字比较次数:记录移动次数:T(n)=O(n²4、)空间复杂度:S(n)=O(1)直接插入排序是稳定的比较、移动次数最少比较、移动次数最多7/22/2021折半插入排序排序过程:用折半查找方法确定插入位置的排序。例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)7/22/2021算法描述算法评价时间复杂度:T(n)=O(5、n²)空间复杂度:S(n)=O(1)voidbinsort(JDr[],intn){inti,j,s,m,k;for(i=2;i<=n;i++){r[0]=r[i];s=1;j=i-1;while(s<=j)//找插入位置{m=(s+j)/2;if(r[0].key=s;k--)r[k+1]=r[k];r[s]=r[0];}}7/22/2021希尔排序(缩小增量法)排序过程:先取一个正整数d16、一个组中排序为止7/22/2021取d3=1三趟分组:1327485544938659776三趟排序:4132738484955657697例初始:4938659776132748554一趟排序:1327485544938659776二趟排序:1344838274955659776取d1=5一趟分组:4938659776132748554取d2=3二趟分组:13274855449386597767/22/2021算法描述例4938659776132748554#defineT3intd[]={5,3,1};ji49133827一趟排序:1327485544938659776jiji274jij7、i55ji38jijiji二趟排序:1344838274955659776jiji6548ji9755ji7647/22/2021voidshellsort(JDr[],intn,intd[T]){inti,j,k;JDx;k=0;while(k=0)&&(x.key
3、327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果:7/22/2021算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数:记录移动次数:若待排序记录按关键字从大到小排列(逆序)关键字比较次数:记录移动次数:若待排序记录是随机的,取平均值关键字比较次数:记录移动次数:T(n)=O(n²
4、)空间复杂度:S(n)=O(1)直接插入排序是稳定的比较、移动次数最少比较、移动次数最多7/22/2021折半插入排序排序过程:用折半查找方法确定插入位置的排序。例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)7/22/2021算法描述算法评价时间复杂度:T(n)=O(
5、n²)空间复杂度:S(n)=O(1)voidbinsort(JDr[],intn){inti,j,s,m,k;for(i=2;i<=n;i++){r[0]=r[i];s=1;j=i-1;while(s<=j)//找插入位置{m=(s+j)/2;if(r[0].key=s;k--)r[k+1]=r[k];r[s]=r[0];}}7/22/2021希尔排序(缩小增量法)排序过程:先取一个正整数d16、一个组中排序为止7/22/2021取d3=1三趟分组:1327485544938659776三趟排序:4132738484955657697例初始:4938659776132748554一趟排序:1327485544938659776二趟排序:1344838274955659776取d1=5一趟分组:4938659776132748554取d2=3二趟分组:13274855449386597767/22/2021算法描述例4938659776132748554#defineT3intd[]={5,3,1};ji49133827一趟排序:1327485544938659776jiji274jij7、i55ji38jijiji二趟排序:1344838274955659776jiji6548ji9755ji7647/22/2021voidshellsort(JDr[],intn,intd[T]){inti,j,k;JDx;k=0;while(k=0)&&(x.key
6、一个组中排序为止7/22/2021取d3=1三趟分组:1327485544938659776三趟排序:4132738484955657697例初始:4938659776132748554一趟排序:1327485544938659776二趟排序:1344838274955659776取d1=5一趟分组:4938659776132748554取d2=3二趟分组:13274855449386597767/22/2021算法描述例4938659776132748554#defineT3intd[]={5,3,1};ji49133827一趟排序:1327485544938659776jiji274jij
7、i55ji38jijiji二趟排序:1344838274955659776jiji6548ji9755ji7647/22/2021voidshellsort(JDr[],intn,intd[T]){inti,j,k;JDx;k=0;while(k=0)&&(x.key
此文档下载收益归作者所有