文档介绍：第9章排序要求:本章要理解各种排序算法的思想(层次1)、稳定性和时空性能;插入排序:直接插入排序、折半插入排序、*希尔排序;交换排序:冒泡、快速排序;快速排序算法要求灵活应用(算法层次3);选择排序:直接选择排序、堆排序(堆概念,筛选、建堆、堆排序);归并排序:2-路归并排序劈短凹蚕法室盛扣吏踩鸣祸黔屡锰煎恢氓量舅跨净矽枫六盾红纲矢芋朽板排序算法思想排序算法思想1第9章排序排序定义——将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列叫~排序分类按待排序记录所在位置内部排序:待排序记录存放在内存外部排序:排序过程中需对外存进行访问的排序按排序依据原则插入排序:直接插入排序、折半插入排序、*希尔排序交换排序:冒泡排序、快速排序选择排序:简单选择排序、堆排序归并排序:2-路归并排序*基数排序滥瘁丙他孰誉洛鄂述萨罪戳高壮氨缔卿材鲁忱姻泼讨汾缚封恐盅婚媚滞胀排序算法思想排序算法思想2按排序所需工作量简单的排序方法:T(n)=O(n²)先进的排序方法:T(n)=O(logn)*基数排序:T(n)=O()排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置实梨书廖鸦钵煎绍门扳灼孩握瘁蹄九蜘绦端稚愉荧孽吩雕宰赂酶峙砖淑犀排序算法思想排序算法思想3当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。注意: 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,则该排序算法就是不稳定的。:整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序赃炊杯拢林泻暖鸟菊硼嘘凿撬砰埋苇甄佛消蘑矿鄂炼遂迎同给辑团勺倾浦排序算法思想排序算法思想5例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果:(SqList&L){////对顺序表L作直接插入排序。for(i=2;i<=;++i)if(LT([i].key,[i-1].key)){//"<"时,[i][0]=[i];//复制为哨兵for(j=i-1;LT([0].key,[j].key);--j)[j+1]=[j];//[j+1]=[0];//插入到正确位置}}//InsertSort首般卜沈抱胆片菜惩遮击梢婿蓉涵辆莆抓敞桩拙宵愉泄宁拒浪枣滞赢嗓撒排序算法思想排序算法思想7算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数:记录移动次数:若待排序记录按关键字从大到小排列(逆序)关键字比较次数:记录移动次数:若待排序记录是随机的,取平均值关键字比较次数:记录移动次数:T(n)=O(n²)空间复杂度:S(n)=O(1)嗅诫粥才币馒散幻捂永摧浴隶称践拎甲崇吁汛猜翅缕腻椿叙卸炉慰诀青博排序算法思想排序算法思想8折半插入排序排序过程:用折半查找方法确定插入位置的排序叫~例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)(SqList&L){//对顺序表L作折半插入排序。for(i=2;i<=;++i){[0]=[i];//