排序算法思想

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

1、第9章排序要求：本章要理解各种排序算法的思想（层次1）、稳定性和时空性能；插入排序：直接插入排序、折半插入排序、*希尔排序；交换排序：冒泡、快速排序；快速排序算法要求灵活应用（算法层次3）；选择排序：直接选择排序、堆排序（堆概念，筛选、建堆、堆排序）；归并排序：2-路归并排序1第9章排序排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、*希尔排序交换排序：冒

2、泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序*基数排序2按排序所需工作量简单的排序方法：T(n)=O(n²)先进的排序方法：T(n)=O(logn)*基数排序：T(n)=O(d.n)排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置3当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。注意：

3、排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。排序的稳定性49.1插入排序直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序5例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)

4、27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果：算法描述算法10.1P2656voidInsertSort(SqList&L){//算法10.1//对顺序表L作直接插入排序。for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){//"<"时，需将L.r[i]插入有序子表L.r[0]=L.r[i];//复制为哨兵for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j

5、+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}}//InsertSort7算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：若待排序记录是随机的，取平均值关键字比较次数：记录移动次数：T(n)=O(n²)空间复杂度：S(n)=O(1)8折半插入排序排序过程：用折半查找方法确定插入位置的排序叫~例i=1(30)1370853942620i=213(1330)70853942620i=76(6133

6、039427085)20…...i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)9算法描述算法10.2P267voidBInsertSort(SqList&L){//对顺序表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(lo

7、w<=high){//在r[low..high]中折半查找有序插入的位置m=(low+high)/2;//折半if(LT(L.r[0].key,L.r[m].key))high=m-1;//插入点在低半区elselow=m+1;//插入点在高半区}for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//插入}}//BInsertSort算法评价时间复杂度：T(n)=O(n²)空间复杂度：S(n)=O(1)10*希尔排序(缩小增量法)排序过程：先取一个正整数d1

8、，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2