数据结构课件(c语言)第10章 排序

《数据结构课件(c语言)第10章 排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章内部排序学习目标理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序方法有不同的分类方法，基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(n·logn)的高效排序方法和O(d·n)的基数排序方法。理解排序方法"稳定"或"不稳定"的含义，弄清楚在什么情况下要求应用的排

2、序方法必须是稳定的。6/30/20211重点和难点重点：希尔排序、快速排序、堆排序和归并排序等高效方法难点：希尔排序、快速排序、堆排序和归并排序等高效方法知识点排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序、基数排序、排序方法的综合比较。6/30/2021210.1概述排序假设含有n个记录的序列为：{R1，R2，…，Rn}，它们的关键字相应为{K1，K2，…，Kn}，对记录序列进行排序就是要确定序号1，2，…，n的一种排列P1，P2，…，Pn，使其相应的关键字满足如下

3、的非递减（或非递增）的关系：Kp1<=Kp2<=…<=Kpn使序列成为一个按关键字有序的序列{Rp1，Rp2，…，Rpn}目的利用高效的查找方法，以提高查找效率。6/30/20213排序分类按待排序记录所在位置内部排序：待排序记录存放在内存。外部排序：排序过程中需对外存进行访问的排序。按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序。交换排序：冒泡排序、快速排序。选择排序：简单选择排序、堆排序。归并排序：2-路归并排序。基数排序6/30/20214稳定若待排序文件中有关键字相等的记录，排序后，其前后相对次序与排序前未发生

4、变化，这种排序称为“稳定”排序；否则是“不稳定”排序。稳定排序与不稳定排序只是表示所用的排序方法，并不说明哪种方法好与差。排序基本操作比较两个关键字大小；将记录从一个位置移动到另一个位置；就全面性能而言，很难提出一种被认为最好的方法，每种方法均有优点和适用环境。6/30/20215本章讨论中，待排记录如下结构。#defineMAXSIZE20;//假设的顺序表最大长度typeintKeyType;//定义关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据

5、项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置或作为判别标志的“哨兵”单元intlength;//顺序表长度}SqList；//顺序表类型6/30/2021610.2插入排序10.2.1直接插入排序基本思想整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。6/30/2021749386597761327i=2(49)386597761327i=3(3849)6597761327i=4(38

6、4965)97761327i=5(38496597)761327i=6(3849657697)1327i=1()i=7(133849657697)2727977665493827(13273849657697)排序结果：383849659797769776137665493813))))))))))))监视哨r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]稳定的排序方法6/30/20218voidInsertSort(SqList&L){//对顺序表L作直接插入排序for(i=2;i<=L.length;++i)i

7、f(LT(L.r[i].key,L.r[i-1].key)){//将L.r[i]插入有序子表L.r[0]=L.r[i];//哨兵L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0].key,L.r[j].key;--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}//if}//InsertSort直接插入排序的算法12345678时间复杂度T(n)=O(n²)6/30/20219算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字

8、比较次数：记录移动次数：若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：6/30/202110若待排序记录是随机的，取平均值。关键字比较次数：记录移动次数：空间复杂度S(n)=O(1)6/30/20211110.