数据结构第11章内排序

发布时间：2024-11-10

课件(清华大学出版社)

第11章

内排序

11.1 排序的基本概念 11.2 插入排序11.3 11.4 11.5 11.6 交换排序选择排序归并排序基数排序

11.7 各种内排序方法的比较和选择

本章小结

课件(清华大学出版社)

11.1

排序的基本概念

所谓排序,就是要整理表中的记录,使之按关键字递增(或递减)有序排列。其确切定义如下：

输入：n个记录,R0,R1,…,Rn-1,其相应的关键字分别为k0,k1,…,kn-1。

输出： Ri0,Ri1,…,Rin-1, 使得 ki0≤ki1≤…≤kin-1 ( 或ki0≥ki1≥…≥kin-1)。

课件(清华大学出版社)

当待排序记录的关键字均不相同时,排序的结果是惟一的,否则排序的结果不一定惟一。如果待排序的表中,存在有多个关键字相同的记录,经过排序后

这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的；反之,若具有相同

关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。在排序过程中,若整个表都是放在内存中处理, 排序时不涉及数据的内、外存交换,则称之为内排序；反之,若排序过程中要进行数据的内、外存交换,则称之为外排序。

课件(清华大学出版社)

内排序的方法内部排序的过程是一个逐步扩大记录的

有序序列长度的过程。

有序序列区

无序序列区经过一趟排序

有序序列区

无序序列区

课件(清华大学出版社)

待排序的顺序表类型的类型定义如下：typedef int KeyType; /*定义关键字类型*/

typedef struct{ KeyType key; InfoType data; } RecType;

/*记录类型*/

/*关键字项*/ /*其他数据项,类型为 InfoType*/

/*排序的记录类型定义*/

课件(清华大学出版社)

11.2

插入排序

插入排序的基本思想是：每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。

两种插入排序方法：(1)直接插入排序 (2)希尔排序。

课件(清华大学出版社)

11.2.1

直接插入排序

假设待排序的记录存放在数组R[0..n-1]中,排序过

程的某一中间时刻,R被划分成两个子区间R[0..i-1]和R[i..n-1],其中：前一个子区间是已排好序的有序区,后一个子区间则是当前未排序的部分,不妨称其为无序区。直接插入排序的基本操作是将当前无序区的第1个记录 R[i]插入到有序区 R[0..i-1] 中适当的位置上 ,使 R[0..i]变为新的有序区。这种方法通常称为增量法,因

为它每次使有序区增加1个记录。

课件(清华大学出版社)

R[0]

R[i]

j=i-1 插入位置

在有序区中插入R[i]的过程

课件(清华大学出版社)

void InsertSort(RecType R[],int n) /*对R[0..n-1]按递增有序进行直接插入排序*/ { int i,j; RecType temp;

for (i=1;i<n;i++){ temp=R[i]; j=i-1; /*从右向左在有序区R[0..i-1]找R[i]的插入位置*/

while (j>=0 && temp.key<R[j].key){ R[j+1]=R[j]; /*将关键字大于R[i].key的记录后移*/ j--;

}R[j+1]=temp; } } /*在j+1处插入R[i]*/

课件(清华大学出版社)

例11.1 设待排序的表有10个记录,其关键字分别为 {9,8,7,6,5,

4,3,2,1,0}。说明采用直接插入排序方法进行排序的过程。初始关键字 i=1 i=2 i=3 i=4 i=5 i=6 i=7 i=8 i=9 9 [8 [7 [6 [5 [4 [3 [2 [1 [0 8 9] 8 7 6 5 4 3 2 1 7 7 9] 8 7 6 5 4 3 2 6 6 6 9] 8 7 6 5 4 3 5 5 5 5 9] 8 7 6 5 4 4 4 4 4 4 9] 8 7 6 5 3 3 3 3 3 3 9] 8 7 6 2 2 2 2 2 2 2 9] 8 7 1 1 1 1 1 1 1 1 9] 8 0 0 0 0 0 0 0 0 0 9]

课件(清华大学出版社)

对于直接插入排序：最好的情况(关键字在记录序列中顺序有序): “比较”的次数： “移动”的次数：0

i 1

n 1

1 n 1

最坏的情况(关键字在记录序列中逆序有序): “比较”的次数： “移动”的次数：

i 1

n 1

(n 1)(n 2) (i 1) 2

i 1

n 1

(i 1)

(n 1)(n 2) 2

课件(清华大学出版社)

11.2.2

希尔排序

希尔排序也是一种插入排序方法,实际上是一种分组插入方法。其基本思想是：先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1 个组,所有距离为d1 的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量d2(<d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

课件(清华大学出版社)

将记录序列分成若干子序列，分别对每个子序列进行插入排序。例如：将 n 个记录分成 d 个子序列： { R[0], R[d], R[2d],…, R[kd] } { R[1], R[1+d], R[1+2d],…,R[1+kd] } … { R[d-1],R[2d-1],R[3d-1],…,R[(k+1)d-1] }

其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。

课件(清华大学出版社)

例如：

16 25 12 30 47 11 23 36 9 18 31第一趟希尔排序，设增量 d =5

11 23 12 9 18 16 25 36 30 47 31第二趟希尔排序，设增量 d = 3

9 18 12 11 23 16 25 31 30 47 36第三趟希尔排序，设增量 d = 1

9 11 12 16 18 23 25 30 31 36 47

课件(清华大学出版社)

void ShellSort(RecType R[],int n) /*希尔排序算法*/ { int i,j,d;RecType temp; d=n/2; /*d取初值n/2*/ while (d>0) { for (i=d;i<n;i++) /*将R[d..n-1]分别插入各组当前有序区*/ { j=i-d; while (j>=0 && R[j].key>R[j+d].key) { temp=R[j]; /*R[j]与R[j+d]交换*/ R[j]=R[j+d];R[j+d]=temp; j=j-d; } } d=d/2; /*递减增量d*/ } }

课件(清华大学出版社)

例11.2 设待排序的表有10个记录,其关键字分别为 {9,8,7,6,5,4,3,2,1,0}。说明采用希尔排序方法进行排序的过程。初始状态 9 8 7 6 5 4 3 2 1 0 (连线部分为下一趟作准备)

d=5

5 (d=5 执行结果)

d=2 d=1

0 0

1 1

2 2

3 3

4 4

5 5

6 6