第7章内排序1.ppt

《第7章内排序1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章内排序数据结构（C++描述）目录7.1基本概念7.2三种代价为O(n2)的排序方法7.3希尔排序7.4快速排序7.5归并排序7.6堆排序7.7基数排序7.8各种内排序方法的比较和选择7.1基本概念7.1.1排序介绍排序是数据处理中一种很重要的运算，同时也是很常用的运算，一般数据处理工作25%的时间都在进行排序。简单地说，排序就是把一组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程。表7-1学生档案表学号姓名年龄性别03001王晓佳18男03002林一鹏19男03003谢宁17女03004张丽娟18女03005周涛20男03006李小燕16女例

2、如，在表7-1中，若以每个记录的学号为关键字，按排序码年龄的递增（由小到大）排序，则所有记录的排序结果可简记为：{（03006，16），（03003，17），（03001，18），（03004，18），（03002，19），（03005，20）}；也可能为：{（03006，16），（03003，17），（03004，18），（03001，18），（03002，19），（03005，20）}；这两个结果都是表7-1按年龄的递增排序结果。若按排序码姓名来进行递增排序，则得到的排序结果为：{（03006，李小燕），（03002，林一鹏），（03001，王晓佳），（03003，谢宁），（0300

3、4，张丽娟），（03005，周涛）}当然，我们还可以按排序码性别来进行递增排序，在此不再作进一步的分析。7.1.2基本概念1．排序码（Sortskey）作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。如上例中的学生年龄。在此我们认为对任何一种记录都可找到一个取得它排序码的函数Sskey(一个或个关键字的组合)。2．有序表与无序表一组记录按排序码的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无序表。3．正序表与逆序表若有序表是按排序码升序排列的，则称为升序表或正序表，否则称为降序表或逆序表。不失普遍性

4、，在本课中我们一般只讨论正序表。4．排序定义若给定一组记录序列r1，r2，…，rn，其排序码分别为s1，s2，…，sn，将这些记录排成顺序为rk1，rk2，…，rkn的一个序列R’，满足条件sk1≤sk2≤…≤skn，或者这些记录排成顺序为rp1，rp2，…，rpn的一个序列R”，满足条件sp1≤sp2≤…≤spn的过程称为排序。也可以说，将一组记录按某排序码递增或递减排列的过程，称为排序。5．稳定与不稳定因为排序码可以不是记录的关键字，同一排序码值可能对应多个记录。对于具有同一排序码的多个记录来说，若采用的排序方法使排序后记录的相对次序不变，则称此排序方法是稳定的，否则称为不稳定的。在

5、上例中（见表7-1，按年龄排序），如果一种排序方法使排序后的结果必为前一个结果，则称此方法是稳定的；若一种排序方法使排序后的结果可能为后一个结果，则称此方法是不稳定的。6．内排序与外排序按照排序过程中使用内外存的不同将排序方法分为内排序和外排序。若排序过程全部在内存中进行，则称为内排序；若排序过程需要不断地进行内存和外存之间的数据交换，则称为外排序。本章仅讨论内排序。7．排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以用算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该

6、方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。为了以后讨论方便，我们直接将排序码写成一个一维数组A[]的形式，具体类型设为Elem，并且在没有声明的情形下，所有排序都按排序码的值递增排列。7.2三种代价为O(n2)的排序方法7.2.1插入排序1．插入排序的基本思想插入排序（InsertSort）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位

7、置，使之成为新的有序表。Templatevoidinsertsort(ElemA[],intn)//插入排序{for(inti=1;i0)&&(skey(A[j])