ch8排序—学生

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

1、第八章排序排序插入排序交换排序选择排序排序方法比较本章小结排序SortingÆ排序定义——将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列叫~Æ排序分类∑按待排序记录所在位置ò内部排序：待排序记录存放在内存ò外部排序：排序过程中需对外存进行访问的排序∑按排序依据原则ò插入排序：直接插入排序、折半插入排序每次将一个待排序的记录，按关键字的大小插入到已排好序的子序列中的适当位置，直到全部记录插入完毕为止ò交换排序：冒泡排序两两比较待排序记录的关键值，交换不满足顺序要求的记录，直到全部满足顺序要求为止ò选

2、择排序：简单选择排序、堆排序每次从待排序记录中选出关键字最小的记录，顺序放在已排序的记录序列的后面，直到全部排完为止排序Sorting∑按排序所需工作量ò简单的排序方法：T(n)=O(n²)ò先进的排序方法：T(n)=O(nlogn)2Æ排序基本操作∑比较两个关键字大小∑将记录从一个位置移动到另一个位置排序SortingÆ排序算法稳定性待排序数列中如果有关键字相等的记录，例如：65493863974913275504经某一种算法排序时，04132738494955636597关键字相等的记录其先后次序始终不变，则称排序

3、算法为稳定的，具有稳定性；否则不稳定，具有不稳定性插入排序InsertionSorting×插入排序的基本思想：每次将一个待排序的记录，按关键字的大小插入到已排好序的子序列中的适当位置，直到全部记录插入完毕为止。直接插入排序StraightInsertionSort∑排序过程：¾先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序；¾整个排序过程为n-1趟插入。直接插入排序StraightInsertionSort012345初始1330268513*012345稳定的排序方法

4、第一趟1330012345第二趟132630012345第三趟13263085012345第四趟1313*263085×待排序记录为R[i]，将其与R[j](j=i-1)进行比较——¾若R[i]>R[j]——R[i]位置不变¾若R[i]

5、ength;i++){if(L.r[i].key

6、+4)(n−1)]记录移动次数：∑(i+1)=i=22©若待排序记录是随机的，取平均值2n]关键字比较次数：24T(n)=O(nT(n)=O(n22))n]记录移动次数：4ò空间复杂度：S(n)=O(1)折半插入排序BinaryInsertionSort∑排序过程：用折半查找方法确定插入位置的排序012345初始3013268515012345i=21330……012345i=51513263085lowmidhigh×待排序记录为R[i]¾low=1，high=i-1，mid=(low+high)/2¾将R[i]与R

7、[mid]比较，进行折半查找，直到low>high折半插入排序BinaryInsertionSort∑排序过程：用折半查找方法确定插入位置的排序012345初始3013268515012345i=21330……012345i=51513263085highlow×待排序记录为R[i]¾low=1，high=i-1，mid=(low+high)/2¾将R[i]与R[mid]比较，进行折半查找，直到low>high¾将i之前low之后元素后移¾将R[i]插入到low所指示位置折半插入排序BinaryInsertionSor

8、tvoidBinSort(SqList&L)∑算法描述{inti,j,high,low,mid;插入第i个记录for(i=2;i<=L.length;i++)∑算法评价{L.r[0]=L.r[i];设置监视哨low=1;high=i-1;ò时间复杂度：while(low<=high)折半查找T(n)=O(n²){mid=(low+