数据结构ch08

第 8 章 排序技术 1

第 8 章 排序技术

8.1 概 述

8.1.1 排序的基本概念

在排序问题中，通常将数据元素称为记录。 排序

简言之，排序是将一个记录的任意序列重新排列成一个按关键码有序的序列。严格地说，给定一个记录序列(r1，r2，…，rn)，其相应的关键码分别为(k1，k2，…，kn)，排序是将这些记录排列成顺序为(rs1，rs2，…，rsn)的一个序列，使得相应的关键码满足ks1≤ks2≤…≤ksn（升序）或ks1≥ks2≥…≥ksn（降序）。 正序、逆序

若待排序序列中的记录已按关键码排好序，称此记录序列为正序；

若待排序序列中记录的排列顺序与排好序的顺序正好相反，称此记录序列为逆序或反序。 趟

在排序过程中，将待排序的记录序列扫描一遍称为一趟。 排序算法的稳定性

假定在待排序的记录序列中，存在多个具有相同关键码的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ki=kj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法稳定；否则称为不稳定。 单键排序、多键排序

根据一个关键码进行的排序称为单键排序；

根据多个关键码进行的排序称为多键排序，这主要针对关键码有重复的情况。 多键排序可以转化成单键排序。 排序的分类

·排序方法分为内排序和外排序两大类。 内排序： 外排序：

·根据排序方法是否建立在关键码比较的基础，将排序方法分为 基于比较的排序： 不基于比较的排序：

·根据排序过程中依据的原则对基于比较的内排序进行分类，大致可分为插入排序、交换排序、选择排序、归并排序等四类。

8.1.2 排序算法的性能

对于基于比较的内排序，在排序过程中通常需要进行下列两种基本操作：⑴ 比较：关键码之间的比较；⑵ 移动：记录从一个位置移动到另一个位置。

评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。 另外，算法本身的复杂程度也是一个要考虑的因素。

2 数据结构电子笔记

8.2 插入排序

8.2.1 直接插入排序

直接插入排序的基本思想是：依次将待排序序列中的每一个记录插入到一个已排好序的序列中，直到全部记录都排好序。

需解决的关键问题是：

⑴

⑵

例：初始键值序列 ［12］ 15 9 20 6 31 24

第一趟排序结果 第二趟排序结果 第三趟排序结果 第四趟排序结果 第五趟排序结果

第六趟排序结果

问题⑴的解决：

问题⑵的解决：

直接插入排序算法InsertSort void InsertSort(int r[ ], int n) 札记： {

}

分析时间性能： ·最好情况： ·最坏情况： ·平均情况： 分析空间性能（辅助空间）：

第 8 章 排序技术 3

8.2.2 希尔排序

希尔排序改进的着眼点是：

希尔排序的基本思想是：先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

需解决的关键问题是：

⑴

⑵

例：初始键值序列 59 20 17 36 98 14 23 83 13 28

第一趟排序结果(d=5)

第二趟排序结果(d=2)

第三趟排序结果(d=1)

问题⑴的解决：

问题⑵的解决：

希尔排序算法ShellSort void ShellSort(int r[ ], int n) 札记： { }

算法的时间性能： 算法的辅助空间：

4 数据结构电子笔记

8.3 交换排序

8.3.1 起泡排序

起泡排序的基本思想是：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。

需解决的关键问题是：

⑴

⑵

⑶

例：初始键值序列 ［50 13 55 97 27 38 49 65］

第一趟排序结果

第二趟排序结果 第三趟排序结果 第四趟排序结果

问题⑴的解决：

问题⑵的解决：

问题⑶的解决： 起泡排序算法BubbleSort void BubbleSort(int r[ ], int n) 札记： {

}

分析时间性能： ·最好情况： ·最坏情况： ·平均情况： 分析空间性能（辅助空间）：

第 8 章 排序技术 5

8.3.2 快速排序

快速排序是对起泡排序的一种改进，改进的着眼点是：

快速排序又称为分区交换排序，其基本思想是：首先选一个轴值（即比较的基准），将待排序记录分割成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。

在快速排序中，需解决的关键问题是： ⑴ ⑵ ⑶ ⑷

问题⑴的解决：

问题⑵的解决：设待排序序列是r[s] ~ r[t]，一次划分的过程用伪代码描述为：

1．将i 和j分别指向待排序区域的最左侧记录和最右侧记录的位置；

2．重复下述过程，直到i=j

2.1右侧扫描，直到记录j的关键码小于基准记录的关键码；

2.2 如果i

2.3左侧扫描，直到记录i的关键码大于基准记录的关键码；

2.4 如果i

3．退出循环，说明i和j指向了基准记录所在位置，返回该位置；

例：初始键值序列 23 13 49 6 31 19 28

具体的一次划分算法如下： 问题⑶和⑷的解决：

例：初始键值序列 23 13 49 6 31 19 28

6 数据结构电子笔记

快速排序一次划分算法Partition

int Partition(int r[ ], int first, int end) 札记：

{ i=first; j=end; //初始化 while (i

{

}

retutn i; //i为轴值记录的最终位置 }

快速排序算法QuickSort

void QuickSort(int r[ ], int first, int end) 札记：

{ }

分析快速排序算法的时间性能： ·最好情况： ·最坏情况： ·平均情况： 空间复杂度： ·最好情况： ·最坏情况： ·平均情况：

札记：

第 8 章 排序技术 7

8.4 选择排序

8.4.1 简单选择排序

简单选择排序是选择排序中最简单的排序方法，其基本思想是：第i趟排序通过n-i次关键码的比较，在n-i+1（1≤i≤n-1）个记录中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。

需解决的关键问题是：

⑴

⑵

例：初始键值序列 ［49 27 65 97 76 13 38］

第一趟排序结果 第二趟排序结果 第三趟排序结果 第四趟排序结果

第五趟排序结果

第六趟排序结果

问题⑴的解决：

问题⑵的解决：

简单选择排序算法SelectSort

void SelectSort(int r[ ], int n) 札记：

{

}

分析简单选择排序算法的时间性能： ·比较次数 ·移动次数 最好情况：

最坏情况：

平均情况：

8 数据结构电子笔记

8.4.2 堆排序

堆排序改进的着眼点是： 1. 堆的定义

堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（小根堆）；或者每个结点的值都大于或等于其左右孩子结点的值（大根堆）。

如果将堆按层序从1开始编号，则结点之间满足如下关系

ki≤k2i ki≤k2i+1 给出两个堆的示例： 或

ki≥k2i ki≥k2i+1

1≤i≤?n2? 堆调整的问题：在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？

例：调整根结点，将下列完全二叉树调整为堆。 28 35 20 32 18 12 需注意的问题： 假设当前要筛选结点的编号为k，堆中最后一个结点的编号为m，并且结点k的左右子树均是堆（即r[k+1] ~ r[m]满足堆的条件），则筛选算法用伪代码可描述为：

1. 设置i和j，分别指向当前要筛选的结点和要筛选结点的左孩子；

2. 若结点i已是叶子，则筛选完毕；否则，比较要筛选结点的左右孩子结

点（如果有右孩子），并将j指向关键码较大的结点；

3. 将要筛选结点i的关键码与j所指向的结点的关键码进行比较

3.1 如果结点i的关键码大，则完全二叉树已经是堆，筛选完毕；

3.2 否则将r[i]与r[j]交换；令i=j，转步骤2继续进行筛选；

筛选算法如下：

第 8 章 排序技术 9

筛选法调整堆的算法Sift

void Sift(int r[ ], int k, int m) 札记：

{

} 2. 堆排序

堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。

需解决的关键问题是： ⑴ ⑵ ⑶

例：（初始建堆过程） 36 18 30

40 32 45 22

50

问题⑴的解决： 问题⑵的解决：

10 数据结构电子笔记

问题⑶的解决：

例：堆排序过程为： 50 45 40 36 32 18 22 30

堆排序算法HeapSort void HeapSort(int r[ ], int n) 札记：

{

}

算法时间性能的分析：

8.5 归并排序

8.5.1 二路归并排序的非递归实现

需解决的关键问题： ⑴ ⑵ ⑶ ⑷

第 8 章 排序技术 11

例：初始键值序列 60 20 10 50 15 30 55

第一趟排序结果

第二趟排序结果 第三趟排序结果

问题⑴的解决：

问题⑵的解决：

一次归并算法Merge

void Merge(int r[ ], int r1[ ], int s, int m, int t) 札记： {

}

问题⑶的解决： ① 若i≤n-2h+1，则

② 若i＜n-h+1，则

③ 若i≥n-h+1，则

一趟归并排序算法MergePass

void MergePass(int r[ ], int r1[ ], int n, int h) 札记： { } 12 数据结构电子笔记

问题⑷的解决：

归并排序非递归算法MergeSort1 void MergeSort1(int r[ ], int r1[ ], int n ) 札记： { }

分析算法的时间性能： 分析算法的空间性能： 8.5.2 二路归并排序的递归实现

例：初始键值序列 60 20 10 50 15 30 55

归并排序的递归算法MergeSort2

void MergeSort2(int r[ ], int r1[ ], int s, int t) 札记： {

}

第 8 章 排序技术 13

8.6 各种排序方法的比较

排序方法的选用应该根据具体情况而定，一般应该从以下几个方面综合考虑：⑴ 时间复杂性；⑵ 空间复杂性；⑶ 稳定性；⑷ 算法简单性；⑸ 待排序记录个数n的大小；⑹ 记录本身信息量的大小；⑺ 关键码的分布情况。 1. 时间复杂性

前面所述各种内排序的时间和空间性能的比较结果如表8-1所示。

排序方法 直接插入排序 希起快尔泡速排排排序 序 序 表8-1 各种排序方法性能的比较

平均情况 最好情况 最坏情况 辅助空间 简单选择排序 堆归并排排序 序 2. 空间复杂性

从空间复杂性看，所有排序方法分为三类：

·归并排序单独属于一类，其空间复杂性为O(n)；

·快速排序单独属于一类，其空间复杂性为O(log2n) ~ O(n)； ·其它排序方法归为一类，其空间复杂性为O(1)。 3. 稳定性

所有排序方法可分为两类，一类是稳定的，包括直接插入排序、起泡排序、简单选择排序和归并排序； 另一类是不稳定的，包括希尔排序、快速排序和堆排序。 4. 算法简单性

从算法简单性看，一类是简单算法，包括直接插入排序、简单选择排序和起泡排序； 另一类是改进算法，包括希尔排序、堆排序、快速排序和归并排序，这些算法都很复杂。 5. 待排序的记录个数n的大小

从待排序的记录个数n的大小看，n越小，采用简单排序方法越合适。 6. 记录本身信息量的大小

记录本身信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。

表8-2 三种简单排序算法中记录的移动次数的比较

排序方法 最好情况 最坏情况 平均情况 直接插入排序 起泡排序 简单选择排序 O(n) 0 0 O(n2) O(n2) O(n) O(n2) O(n2) O(n) 7. 关键码的分布情况

当待排序记录序列为正序时，直接插入排序和起泡排序能达到O(n)的时间复杂度； 对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为O(n2)；

简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键码的分布而改变。

本文来源：https://www.bwwdw.com/article/3tnx.html