资源描述：
《软件技术基础-排序1.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、排序的目的是将一组任意的数据元素(或记录)序列，按照人们所需要的顺序，排列成有规律的按关键字有序的序列。如手机电话簿、目前的各种排行榜第十四章排序本章主要内容：1.排序的基本概念2.插入排序3.选择排序4.交换排序5.归并排序第十四章排序预备知识：关键字(key):通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据，该域即为关键字。如学生这个数据对象，关键字可以是学号或身份证号。每个数据表用哪个属性域作为关键码，要视具体的应用需要而定。1.排序的基本概念1)排序的概念：就是整理文件中的记录，将它们按照关键字值的递增
2、或递减的顺序排列起来。假设文件中含有n个记录(R1,R2,…,Rn),它们的关键字分别为k1，k2，…，kn，我们将这n个记录重排为Ri1,Ri2,…,Rin,使得ki1≤ki2≤…≤kin(或ki1≥ki2≥…≥kin)，这就是排序。排序前：(R1,R2,…,Rn),k1，k2，…，kn(无序)排序后：(Ri1,Ri2,…,Rin)ki1≤ki2≤…≤kin(或ki1≥ki2≥…≥kin)(有序)1.排序的基本概念2)排序的稳定性：存在于文件中的记录，可能含有相同的关键字。对于关键字ki=kj的记录Ri和Rj，如果在原始文件中，Ri排在Rj之前，而排序
3、后的文件中Ri仍然排在Rj之前，就称排序是稳定的。反之，如果排序后变成Ri排在Rj之后，就称此排序是不稳定的。1.排序的基本概念1.排序的基本概念3)排序分类按待排序记录所在位置分：内部排序：整个排序过程都在内存中进行的排序，适用于记录文件个数不是很多的小文件。外部排序：当排序的文件很大时，以至内存不足以存放全部记录，需借助对外存进行访问的排序，适用于记录个数太多，不能一次将其全部放入内存的大文件。内部排序按排序所用策略分：插入排序：直接插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序归并排序：2-路归并排序1.排序的基本概念4)内部
4、排序所用的存储结构：以一维数组作为存储结构排序过程是对记录本身进行物理重排，即通过比较和判定，把记录移动合适的位置。以链表作为存储结构排序过程中无须移动记录，仅需修改指针即可，通常把这类排序称为表排序。为排序文件建立辅助表有的排序方法难以在链表上实现，此时，若仍需要避免排序过程记录的移动，可以为文件记录一个辅助表（如索引表），这样，排序过程中只需对这个辅助的表进行物理重排，而不移动记录本身。1.排序的基本概念5)排序方法的评价：执行算法所需要的时间执行算法所需要的附加空间算法本身的复杂程度排序是一种经常使用的一种运算，其所需的附加空间量一般都不大，所以排
5、序的时间代价是衡量排序算法好坏的最重要的标志。6)排序的基本操作：比较两个关键字大小将记录从一个位置移动到另一个位置排序的时间代价主要是指执行算法中关键字的比较和记录的移动次数，因此在下面讨论的各种排序算法时，我们将给出各算法的比较次数和移动次数。1.排序的基本概念7)本章排序方法所用的存储结构：本章中，假设记录数组作为文件的存储结构，关键字为整数，文件类型说明如下:typedefstruct/*定义记录为结构类型*/{intkey;/*关键字域*/datatypeother;/*记录的其它域*/}rectype;rectypeR[n];/*R为记录类型
6、的数组*/其中：n为文件的记录总数。本章主要内容：1.排序的基本概念2.插入排序3.选择排序4.交换排序5.归并排序第十四章排序2.插入排序插入排序（InsertionSort）将待排序的一组记录分为两个区：有序区和无序区，每次将无序区中的第一个记录按其关键字值的大小插入到有序区中的适当位置，直到无序区中的全部记录都插完为止。插入排序的分类:直接插入排序希尔排序2.插入排序－直接插入排序2.1直接插入排序1）基本思想直接插入排序是一种最简单的排序方法。具体做法是在插入第i个记录时，R1,R2,…,Ri-1已排好序，这时将Ri的关键字ki依次与关键字ki-
7、1,ki-2，…,k1进行比较，从而找到应该插入的位置，然后将ki插入。R1,R2,…,Ri-1Ri,Ri+1,…,Rn有序区无序区注意比较的方向2)直接插入排序实例初始关键字[47]33618272112547’i=2(33)[3347]618272112547’i=3(61)[334761]8272112547’i=4(82)[33476182]72112547’i=5(72)[3347617282]112547’i=6(11)[113347617282]2547’i=7(25)[11253347617282]47’i=8(47’)[11253347
8、47’617282]2.插入排序－直接插入排序2.插入排序－直接插入排序3）算法
