数据结构 09 第9章 排序

第9章排序数据结构(C++描述)

2013年12月25日星期三

本章主要内容9.19.2 9.3 9.4 9.5 *9.6

基本概念插入排序交换排序选择排序归并排序分配排序

9.7各种内排序方法的比较和选择2013年12月25日星期三 2

9.1基本概念9.1.1排序介绍排序(Sorting)是数据处理中一种很重要的运算，同时也是很常用的运算，一般数据处理工作25%的时间都在进行排序。简单地说，排序就是把一组记录(元素)按照某个域的值的递增(即由小到大)或递减(即由大到小)的次序重新排列的过程。

2013年12月25日星期三

表9-1学生档案表学号 99001 99002姓名王晓佳林一鹏年龄 18 19性别男男

9900399004 99005 990062013年12月25日星期三

谢宁张丽娟周涛李小燕

1718 20 16

女女男女4

例如，在表9-1中，若以每个记录的学号为关键字，按排序码年龄的递增(由小到大)排序，则所有记录的排序结果可简记为：

{(99006,16),(99003,17),(99001,18), (99004,18),(99002,19),(99005,20)};也可能为：{(99006,16),(99003,17),(99004,18), (99001,18),(99002,19),(99005,20)};这两个结果都是表9-1按年龄的递增排序结果。

2013年12月25日星期三

若按排序码姓名来进行递增排序，则得到的排序结果为：{(99006,李小燕),(99002,林一鹏),(99001,王晓佳),(99003,谢宁),(99004,张丽娟), (99005,周涛)}当然，我们还可以按排序码性别来进行递增排序，在此不再作进一步的分析。

2013年12月25日星期三

9.1.2基本概念1、排序码(Sort Key)作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。如上例中的学生年龄。在此我们认为对任何一种记录都可找到一个取得它排序码的函数Skey(一个或个关键字的组合)。

2、有序表与无序表一组记录按排序码的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无序表。2013年12月25日星期三 7

3、正序表与逆序表若有序表是按排序码升序排列的，则称为升序表或正序表，否则称为降序表或逆序表。不失普遍性，我们一般只讨论正序表。

4、排序定义若给定一组记录序列r1,r2,…,rn,其排序码分别为s1,s2,…,sn,将这些记录排成顺序为rk1,rk2,…, rkn的一个序列R’,满足条件sk1≤sk2≤…≤skn,获得这些记录排成顺序为rp1,rp2,…,rpn的一个序列R”,满足条件sp1≤sp2≤…≤spn的过程称为排序。也可以说，将一组记录按某排序码递增或递减排列的过程，称为排序

。2013年12月25日星期三 8

5、稳定与不稳定因为排序码可以不是记录的关键字，同一排序码值可能对应多个记录。对于具有同一排序码的多个记录来说，若采用的排序方法使排序后记录的相对次序不变，则称此排序方法是稳定的，否则称为不稳定的。在上例中(见表9-1,按年龄排序),

如果一种排序方法使排序后的结果必为前一个结果，则称此方法是稳定的；

若一种排序方法使排序后的结果可能为后一个结果，则称此方法是不稳定的。

2013年12月25日星期三

6、内排序与外排序按照排序过程中使用内外存的不同将排序方法分为内排序和外排序。若排序过程全部在内存中进行，则称为内排序；若排序过程需要不断地进行内存和外存之间的数据交换，则称为外排序。

2013年12月25日星期三

内排序大致可分为五类：插入排序、交换排序、选择排序、归并排序分配排序。本章仅讨论内排序。

2013年12月25日星期三

7、排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。

2013年12月25日星期三

为了以后讨论方便，我们直接将排序码写成一个一维数组的形式，具体类型设为Elemtype,并且在没有声明的情形下，所有排序都按排序码的值递增排列。

2013年12月25日星期三

插入排序(直插排序、二分排序、希尔排序)

交换排序(冒泡排序、快速排序)

排序

选择排序 (直选排序、树型排序、堆排序)归并排序(二路归并排序、多路归并排序)

分配排序 (多关键字排序、基数排序)2013年12月25日星期三 14

9.2

插入排序

9.2.1直接插入排序 1、直接插入排序的基本思想直接插入排序(Straight Insertion Sorting)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

2013年12月25日星期三

2、直接插入的算法实现void insertsort(ElemType R[],int n)//待排序元素用一个数组R表示，数组有n个元素{ for ( int i=1; i<n; i++)//i表示插入次数，共进行n-1次插入{ ElemType temp=R[i];//把待排序

元素赋给temp int j=i-1; while ((j>=0)&& (temp<R[j]))

{

R[j+1]=R[j]; j--;}//顺序比较和移动R[j+1]=temp;}

}2013年12月25日星期三 16

例如，n=6,数组R的六个排序码分别为： 17,3,25,14,20,9。它的直接插入排序的执行过程如图9-1所示。

2013年12月25日星期三

注意：数据从后面开始比较，然后发生移动的。R[0]初始状态 (17 ) R[1] 3 R[2] 25 R[3] 14 R[4] 20 R[5] 9

第一次插入第二次插入

(3 (3

17 ) 17

25 25 )

14 14

20 20

9 9

第三次插入

(3

14

17

25 )

20

9

第四次插入

(3

14

17

20

25 )

9

第五次插入

(3

9

14

17

20

25)

图 9-1直接插入排序示例2013年12月25日星期三 18

3、直接插入排序的效率分析从上面的叙述可以看出，直接插入排序算法十分简单。那么它的效率如何呢？首先从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次(正序),移动两次；最多比较i次，移动i+2次(逆序)(i=1,2,…, n-1)。若分别用Cmin,Cmax和Cave表示元素的总比较次数的最小值、最大值和平均值，用Mmin,Mmax和Mave表示元素的总移动次数的最小值、最大值和平均值，则上述直接插入算法对应的这些量为： Cmin=n-1 Cave=(n2+n-2)/4 M min=2(n-1) M max=3+4+…+n+1=(n2+3n-4)/2 M max=(n2+7n-8)/4

Cmax=1+2+…+n-1=(n2-n)/2

因此，直接插入排序的时间复杂度为O(n2)。直接插入算法的元素移动是顺序的，该方法是稳定的。

2013年12月25日星期三