资源描述：
《第10章 排序(简).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构课程的内容第10章排序学习要点理解和熟悉各种排序的基本思想和过程掌握各种排序算法的时间复杂度的分析方法和结论要求能根据各种排序方法的优缺点及不同场合选择合适的排序方法本章内容10.1基本概念10.2插入排序（直接插入、折半插入、表插入排序、希尔排序）10.3快速排序（起泡排序、快速排序）10.4选择排序（简单选择排序、树形选择排序、堆排序）10.5归并排序10.6基数排序10.7各种内部排序方法的比较讨论10.1基本概念排序（Sorting）:是将数据元素（记录）的一个任意序列，重新排列成一个按关键字有序的序列。一般情况下，假设含n个记录的序列为（R1,R2,…,Rn）其
2、相应关键字序列为（K1,K2,…,Kn）需确定一种排列，使关键字满足如下的递增的关系Ki1≤Ki2≤…≤Kin则按此关系将记录序列重新排列为(Ri1,Ri2,…,Rin)的操作称之为排序。学号姓名年龄性别990001王晓佳18男990002林一鹏19男990003谢宁17女990004张丽娟18女990005周涛20男990006李小燕16女关键字是指在一个记录中可以标识该数据项的值，它是排序运算的重要依据。关键字的选取应根据需要而定，比如在学生档案表中，可选择“学号”为关键字来识别学生，也可选择“年龄”为关键字对学生排序。9.1基本概念按照排序过程中使用内、外存的不同，将排序方
3、法分为内部排序和外部排序。内部排序:如果待排序的记录放在计算机内存中进行排序，整个排序过程不需要访问外存便能完成，则此类排序称为～。内排序分类：插入排序、交换排序、选择排序、归并排序和基数排序。外部排序:排序的记录数量比较大，排序期间文件的全部记录不能同时存放在计算机的内存里，排序过程中需要不断地进行内存和外存之间的数据交换，则此类排序称为～。排序的分类排序的目的是什么？排序算法的好坏如何衡量？时间效率——排序速度（即排序所花费的全部比较次数）空间效率——占内存辅助空间的大小稳定性——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。——
4、便于查找！10.1基本概念在待排序的序列中，关键字可以是记录的主关键字，也可以是记录的次关键字，或是若干数据项的组合。由主关键字的定义可知，任何一个记录的无序序列经排序后得到的结果是唯一的。若是次关键字，排序的结果不唯一，因为等待排序的记录序列中可能存在两个或两个以上关键字相等的记录。若采用的排序方法使具有相同关键字的记录在排序过程中相对次序不变，则称此排序方法是稳定的，否则称为不稳定的。排序的稳定性例如：假定一组记录为（15,67,23,15*,40），其中关键字同为15的记录有两个。如果一种排序方法使排序后的结果必为（15,15*,23,40,67），则称此方法是稳定的；若一
5、种排序方法使排序后的结果可能为（15*,15,23,40,67），则称此方法是不稳定的。排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。有序表与无序表一组记录按排序关键字的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无序表。正序表与逆序表若有序表是按排序码升序排列的，则称为升序表或正序表，否则称为降序表或逆序表。排序的时间复杂性#definemaxsize20/*设记录不超过20个*/typedefintKeyType;/*定义关键字为整数类型*/typedefstruct{Ke
6、yTypekey;/*关键字域*/InfoTypeotherinfo;/*其它数据域*/}DataType;/*记录类型*/typedefstruct{DataTyper[maxsize+1];/*r[0]用作监视哨单元*/intlength;/*顺序表长度*/}SqList;在本章讨论的算法通常采用顺序存储结构，用一维数组来实现，且记录按照关键字递增的顺序排列。存储结构按排序过程中依据的不同原则对内排方法分类：（1）插入排序（2）交换排序（3）选择排序（4）归并排序（5）基数排序按内排过程中所需的工作量分类：（1）简单的排序方法，其时间复杂度为O(n×n)（2）先进的排序方法，
7、其时间复杂度为O(nlogn);（3）基数排序，其时间复杂度为O(d×n)排序算法的两种基本操作：（1）比较两个关键字的大小；（2）将记录从一个位置移至另一个位置；10.2插入排序插入排序的基本思想是：插入排序有多种具体实现算法：1)直接插入排序2)折半插入排序3)希尔排序每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。边插入边排序，保证子序列中随时都是排好序的。基本思想整个排序过程为n-1趟插入，即先将序列中第1个记录看
