数据结构课件排序.ppt

《数据结构课件排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章排序一、基本概念排序：将文件中的记录按照关键字值递增或递减的顺序排列起来。排序的稳定与不稳定：若关键字相同的记录在排序后先后顺序仍然不变，则称所用的排序方法是稳定的，否则就是不稳定的。内部排序：全部在内存中进行的排序外部排序：排序中需使用内存与外存内部排序：插入排序，交换排序，选择排序，归并排序，基数排序等。内部排序与存储结构：（1）一维数组作为存储结构：对记录进行物理重排；（2）以链表作为存储结构：无须移动记录，仅需修改指针即可；（3）建立索引表辅助排序排序算法的评价标准：（1）时间；（2）执行算法所需的附加空

2、间；（3）算法复杂度。主要是时间代价：算法的比较次数和移动次数。注：简单的排序方法，时间复杂度O(n2);先进的排序方法，时间复杂度O(nlogn)；基数排序，时间复杂度O(d·n)。以数组作为文件的存储结构#defineMAXSIZE100typedefstruct{KeyTypekey;InfoTypeotherinfo;}RecType;typedefstruct{RecTyper[MAXSIZE+1];//r[0]闲置或作为哨兵单元intlength;}SqList;如：以某课程考试成绩为关键字的排序二、插入排序

3、(InsertionSort)定义：将待排序记录分为有序区和无序区，每次将无序区中的第一个记录按其关键字值的大小插入到有序区中的适当位置，直到无序区记录全部插入为止。1直接插入排序方法：在插入第i个记录时，R1,R2,……，Ri-1已排好序，将关键字ki依次与关键字ki-1,ki-2,……,k1进行比较，从而找到应该插入的位置，然后将记录Ri插入。对R[1]~R[n]进行排序，R[0]为监视哨[]4733618272112547‘[]4733618272112547‘[33]3347618272112547‘//33<

4、47[33]3347618272112547‘[33]3347618272112547‘[72]3347617282112547‘[11]3347617282822547‘//11<82[11]3347617272822547‘//11<72[11]3347616172822547‘//11<61[11]3347476172822547‘//11<47[11]3333476172822547‘//11<33[11]1133476172822547‘//结束11的插入排序[25]1125334761728247

5、’//[47]1125334747’617282中间过程算法：voidInsertSort(SqList&L){for(i=2;i<=L.length;i++)if(L.r[i].key

6、l’smethod）“缩小增量排序”(DiminishingIncrementSort)基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。步骤：对整个待排记录序列，按间隔d1分组，组内排序取d2

7、182720211253347‘4757617282d=1记录分组：某一趟希尔排序的增量为d，文件分为d组：(R1,Rd+1,R2d+1,…),(R2,Rd+2,R2d+2,…),…，(Rd,R2d,R3d,…)确定Ri属于哪一组？Ri必然和Ri-d*m（i-d*m>0）、Ri+d*m(i+d*m<=n)同组voidShellInsert(SqList&L,intdk){for(i=dk+1;i<=L.length;i++)if(L.r[i].key

8、for(j=i-dk;j>0&&L.r[0].key