石油大学软件技术基础 ch4_2排序课件.ppt

《石油大学软件技术基础 ch4_2排序课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.2排序4.2.1排序的基本概念4.2.2插入排序4.2.3交换排序4.2.4选择排序4.2.5归并排序4.2.6内部排序方法的比较和选择4.2.7小结14.2.1排序的一般概念排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~假设待排序的记录存放在地址连续的一组存储单元中，那么这种存储方式下的数据类型可描述为：#defineMAX20typedefstruct{structnode{intkey;floatotherinfo;}r[maxsize];intn;}SeqLis

2、tL;MAX01234………keyinfo排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置2排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问按排序依据原则(内部排序)插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、树形选择排序、堆排序归并排序：2-路归并排序3排序分类按排序的稳定性稳定的算法：相同关键字元素间的位置关系排序前与排序后一致不稳定的算法：相同关键字元素间的位置关系排序前与排序后不一致按排序所

3、需工作量简单的排序方法：T(n)=O(n²)先进的排序方法：T(n)=O(logn)44.2.2插入排序1.直接插入排序2.折半插入排序3.表插入排序4.希尔排序5直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。6直接插入排序算法描述voidinsertsort(SeqList&L){inti,j;for(i=2;i<=L.length;i++)if(L.r[i].key

4、将r[i]插入有序表{L.r[0]=L.r[i];/*作为监视哨*/for(j=i-1;L.r[0].key

5、597)1327i=613(13384949*6597)27()i=7(13384949*6597)2727jjjjjj9749*65493827(1327384949*6597)排序结果：voidinsertsort(SeqList&L){for(i=2;i<=L.length;i++)if(L.r[i].key

6、r[j+1]=L.r[j];//同时记录后移L.r[j+1]=L.r[0];//插入}}r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]直接插入排序是一个稳定的排序方法。8算法评价时间复杂度：向有序表中逐个插入记录的操作，进行了n-1趟，每趟操作分为比较关键字和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键字的初始排列。若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：0voidinsertsort(SeqList&L){for(i=2;i<=L.length;i

7、++)if(L.r[i].key

8、(SeqList&L){for(i=2;i<=L.length;i++)if(L.r[i].key