第8章-排序 - #瘫男日记

8.1 基本概念和排序方法概述

8.1.1 排序的基本概念

什么是排序？

排序：排序：将一组杂乱无章的数据按一定规律顺次排列起来。即，将无序序列排成一个有序序列（由小到大或由大到小）的运算。

如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言

排序方法的分类

按数据存储介质：
- 内部排序：数据量不大、数据在内存，无需内外存交换数据
- 外部排序：数据量较大、数据在外存（文件排序）

外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多

按比较器个数：
- 串行排序：单处理机（同一时刻比较一对元素）
- 并行排序：多处理机（同一时刻比较多对元素）

按辅助空间：
- 原地排序：辅助空间用量为O(1)的排序方法（所占的辅助空间与参加排序的数据量大小无关）
- 非原地排序：辅助空间用量超过O(1)的排序方法

按稳定性：
- 稳定排序：能够使任何数值相等的元素，排序以后相对次序不变
- 非稳定排序：不是稳定排序的方法

示例1是稳定排序，示例2是不稳定排序

排序的稳定性只对结构类型数据排序有意义，排序方法是否稳定，并不能衡量一个排序算法的优劣

按自然性：
- 自然排序：输入数据越有序，排序的速度越快的排序方法
- 非自然排序：不是自然排序的方法

8.1.2 待排序记录的存储方式

记录序列以顺序表存储

#define MAXSIZE 20

typedef int keyType;

typedef struct {
	keyType key;
	// other data
}recordType;


typedef struct {
	recordType r[MAXSIZE + 1];
	int length;
}suquenList;

8.2 插入排序

基本思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止

基本操作：有序插入

在有序序列中插入一个元素，保持序列有序，有序长度不断增加

插入排序的种类

8.2.1 直接插入排序

/*******************************************************************************************************************************
 * @description：直接插入排序
 * @param：L
 */
void directInsertionSort(sequenList& L)
{
	int i, j;
	for (i = 2; i <= L.length; i++) {
		if (L.r[i].key < L.r[i - 1].key) {
			L.r[0] = L.r[i];
			for (j = i - 1; L.r[0].key < L.r[j].key; j--) {
				L.r[j + 1] = L.r[j];
			}
			L.r[j + 1] = L.r[0];
		}
	}
}

性能分析

结论：

元素数据越接近有序，排序速度越快
最坏情况下（输入的数据是逆有序的）Tw(n) = O(n^2)
平均情况下，耗时差不多是最坏情况的一半 Te(n) = O(n^2)
要提高查找速度
- 减少元素的比较次数
- 减少元素的移动次数

8.2.2 折半插入排序

/*******************************************************************************************************************************
 * @description：折半插入排序
 * @param：L
 */
void binaryInsertionSort(sequenList& L)
{
	int i, j, low, high, mid;
	for (i = 2; i <= L.length; i++) {
		L.r[0] = L.r[i];
		// 二分查找
		low = 1;
		high = i - 1;
		while (low <= high) {
			mid = (low + high) / 2;
			if (L.r[0].key < L.r[mid].key) {
				high = mid - 1;
			}
			else {
				low = mid + 1;
			}
		}
		// 循环结束，high+1则为插入位置，移动元素
		for (j = i - 1; j >= high + 1; j--) {
			L.r[j + 1] = L.r[j];
		}
		L.r[high + 1] = L.r[0];
	}
}

折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列

减少了比较次数，但没有减少移动次数
平均性能优于直接插入排序

时间复杂度：O(n^2)

空间复杂度：O(1)

是一种稳定的排序方法

8.2.3 希尔排序

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

特点：

缩小增量
多遍插入排序

例如：

思路：

特点：

一次移动，移动位置较大，跳跃式地接近排序后的最终位置
最后一次只需要少量移动
增量序列必须是递减的，最后一个必须是1
增量序列应该是互质的

/*******************************************************************************************************************************
 * @description：希尔排序
 * @param：L
 */
void shellSort(sequenList& L)
{
	int i, j, increment;
	increment = L.length;
	do {
		increment = increment / 3 + 1;
		for (i = increment + 1; i <= L.length; i++) {
			if (L.r[i].key < L.r[i - increment].key) {
				L.r[0] = L.r[i];
				for (j = i - increment; j > 0 && L.r[0].key < L.r[j].key; j -= increment) {
					L.r[j + increment] = L.r[j];
				}
				L.r[j + increment] = L.r[0];
			}
		}
	} while (increment > 1);
}

算法分析：

时间复杂度是n和d的函数：O(n^1.25) ~O(1.6n^1.25)——经验公式
空间复杂度为O(1)
是一种不稳定的排序方法
如何选择最佳d序列，目前尚为解决
最后一个增量值必须为1，无除了1之外的公因子
不宜在链式存储结构上实现

8.3 交换排序

8.3.1 冒泡排序

基于简单的交换思想

基本思想：每躺不断将记录两两比较，并按“前小后大”规则交换

/*******************************************************************************************************************************
 * @description：冒泡排序
 * @param：L
 */
void bubbleSort(sequenList& L)
{
	int i, j;
	recordType temp;
	// 外层循环控制比较的趟数
	for (i = 1; i <= L.length - 1; i++) {
		// 内层循环控制每趟比较的次数
		for (j = 1; j <= L.length - i; j++) {
			if (L.r[j].key < L.r[j + 1].key) {
				// 交换
				temp = L.r[j];
				L.r[j] = L.r[j + 1];
				L.r[j + 1] = temp;
			}
		}
	}
}

优点：每躺结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其它元素

如何提高效率？

一旦某一趟比较时不出现记录交换，说明已经排好序了，就可以结束本算法

/*******************************************************************************************************************************
 * @description：冒泡排序
 * @param：L
 */
void bubbleSort(sequenList& L)
{
	int i, j;
	recordType temp;
	int flag = 1;	// 用于标记是否发生交换

	// 外层循环控制比较的趟数
	for (i = 1; i <= L.length - 1 && flag == 1; i++) {
		flag = 0;
		// 内层循环控制每趟比较的次数
		for (j = 1; j <= L.length - i; j++) {
			if (L.r[j].key < L.r[j + 1].key) {
				flag = 1;	// 发生交换,标记为1;若本趟没发生交换，flag保持为0
				// 交换
				temp = L.r[j];
				L.r[j] = L.r[j + 1];
				L.r[j + 1] = temp;
			}
		}
	}
}

时间复杂度：

最好情况（正序）
- 比较次数：n-1
- 移动次数：0
最坏情况（逆序）
- 比较次数：
- 移动次数：

算法评价：

时间复杂度：O(n^2)
空间复杂度：O(1)
是稳定

8.3.2 快速排序

基本思想：

任取一个元素（如：第一个）为中心
所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表
对各子表重新选择中心元素并依次规则调整（递归）
直到每个子表的元素只剩一个

/*******************************************************************************************************************************
 * @description：获取中轴
 * @param：L
 * @param：low
 * @param：high
 * @return：
 */
int partition(sequenList& L, int low, int high)
{
	L.r[0] = L.r[low];
	int pivotkey = L.r[low].key;
	while (low < high) {
		while (low < high && L.r[high].key >= pivotkey) {
			high--;
		}
		L.r[low] = L.r[high];
		while (low < high && L.r[low].key <= pivotkey) {
			low++;
		}
		L.r[high] = L.r[low];
	}
	L.r[low] = L.r[0];
	return low;
}






/*******************************************************************************************************************************
 * @description：快速排序
 * @param：L
 * @param：low
 * @param：high
 */
void quickSort(sequenList& L, int low, int high)
{
	if (low < high) {
		// 将表一分为二
		int pivotloc = partition(L, low, high);
		// 递归对低子表递归排序
		quickSort(L, low, pivotloc - 1);
		// 递归对高子表递归排序
		quickSort(L, pivotloc + 1, high);
	}
}

时间复杂度：

quickSort()：O(logn)
partition()：O(n)

空间复杂度：

快速排序不是原地排序，由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度

在平均情况下：需要O(logn)的栈空间
最坏情况下：栈空间可达O(n)

稳定性：

快速排序是一种不稳定的排序方法

算法分析：

划分元素的选取是影响时间性能的关键
输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法
改变划分元素的选取情况，至多只能改变算法平均情况下的时间性能，无法改变最坏情况下的时间性能。即时最坏情况下，快速排序的时间复杂性总是O(n^2)

8.4 选择排序

8.4.1 简单选择排序

基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置

基本操作：

首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换
再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
重复上述操作，共进行n-1趟排序后，排序结束

/*******************************************************************************************************************************
 * @description：简单选择排序
 * @param：L
 */
void simpleSelectionSort(sequenList& L)
{
	int i, j, min;
	for (i = 1; i < L.length; i++) {
		min = i;
		for (j = i + 1; j <= L.length; j++) {
			if (L.r[j].key < L.r[min].key) {
                // 记录最小值的位置
				min = j;
			}
		}
		if (min != i) {
			swap(L.r[i], L.r[min]);
		}
	}
}

时间复杂度：O(n^2)

简单选择排序是不稳定排序

8.4.2 堆排序

堆的定义

堆排序

若在输出堆顶的最小值（最大值）后，使得剩余 n-1 个元素的序列重又建成一个堆，则得到 n 个元素的次小值（次大值）.…如此反复，便能得到一个有序序列，这个过程称之为堆排序

实现堆排序需解决两个问题：

如何由一个无序序列建成一个堆？
如何在输出堆顶元素后，调整剩余元素为一个新的堆？

堆的调整

如何在输出堆顶元素后，调整剩余元素为一个新的堆？

小根堆：

输出堆顶元素之后，以堆中最后一个元素替代之
然后将根结点值与左、右子树的根结点值进行比较，并于其中小者进行交换
重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”

/*******************************************************************************************************************************
 * @description：堆的调整
 * @param：L
 * @param：s
 * @param：m
 */
void heapAdjust(sequenList& L, int s, int m)
{
	int j;
	L.r[0] = L.r[s];
	for (j = 2 * s; j <= m; j *= 2) {
		if (j < m && L.r[j].key < L.r[j + 1].key) {
			++j;
		}
		if (L.r[0].key >= L.r[j].key) {
			break;
		}
		L.r[s] = L.r[j];
		s = j;
	}
	L.r[s] = L.r[0];
}

可以看出：

对于一个无序序列反复“筛选”就可以得到一个堆；即：从一个无序序列建堆的过程就是一个反复“筛选”的过程

堆的建立

在完全二叉树中所有以叶子结点（序号 i>n/2）为根的子树是堆。这样，我们只需依次将以序号为 n/2，n/2-1，……，1的结点为根的子树均调整为堆即可

即：对应由n个元素组成的无序序列，“筛选”只需从第n/2个元素开始

/*******************************************************************************************************************************
 * @description：堆的建立
 * @param：L
 */
void heapCreate(sequenList& L)
{
	int i;
	for (i = L.length / 2; i > 0; i--) {
		heapAdjust(L, i, L.length);
	}
}

由以上分析知：

若对一个无序序列建堆，然后输出根；重复该过程就可以由一个无序序列输出为有序序列

实质上，堆排序就是利用完全二叉树中父节点与孩子结点之间的内在关系来排序的

/*******************************************************************************************************************************
 * @description：堆排序
 * @param：L
 */
void heapSort(sequenList& L)
{
	int i;
	heapCreate(L);	// 建立初始堆
	for (i = L.length; i > 1; i--) {
		swap(L.r[1], L.r[i]);
		heapAdjust(L, 1, i - 1);	// 将剩余的i-1个元素整理成堆
	}
}

时间复杂度：O(nlogn)

堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复筛选上。堆排序在最坏清况下，其时间复杂度也为O(nlogn)，这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于“最好”或“最坏”的状态。
另外，堆排序仅需一个记录供交换用的辅助存储空间
然而堆排序是一种不稳定的排序方法，它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的

8.5 归并排序

基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列

在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列R[l…m]和R[m+1…n]归并为一个有序序列R[l…n]

算法分析：

时间效率：O(nlogn)
空间效率：O(n)
稳定

8.6 基数排序

基本思想：分配+收集

也叫桶排序或箱排序：设置若干个箱子，将关键字为k的记录放入第k个箱子，然后在按序号将非空的连接

基数排序：数字是有范围的，均由0-9个十个数字组成，则只需设置十个箱子，相继按个、十、百……进行排序

时间效率：O(k*(n+m))

k：关键字个数
m：关键字取值范围为m个值

空间效率：O(n+m)

稳定性：稳定

8.7 排序方法综合比较

一、时间性能：

按平均的时间性能来分，有三类排序方法：
1. 时间复杂度为O(nlogn)的方法有：
  1. 快速排序、堆排序和归并排序，其中快速排序为最好
2. 时间复杂度为O(n^2)的有：
  1. 直接插入排序、冒泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录列尤为如此
3. 时间复杂度为O(n)的排序方法只有：基数排序
当待排记录序列按关键字顺序有序时，直接插入排序和冒泡排序能达到O(n)的时间复杂度；而对于快速排序而言，这是最不好的情况，此时的时间性能退化为O(n^2)，因此应该尽量避免的情况
简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变

二、空间性能：指的是排序过程中所需的辅助空间的大小

所有的简单排序方法（包括：直接插入、冒泡和简单选择）和堆排序的空间复杂度为O(1)
快速排序为O(logn)，为栈所需的辅助空间
归并排序所需辅助空间最多，其空间复杂度为O(n)
链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)

三、排序方法的稳定性能

稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。
当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。
对于不稳定的排序方法，只要能举出一个实例说明即可。
快速排序和堆排序是不稳定的排序方法。

8.8 写在最后

完整代码：戳我🌹

本文完

敬爱与明天🌹

8.1 基本概念和排序方法概述

8.1.1 排序的基本概念

8.1.2 待排序记录的存储方式

8.2 插入排序

8.2.1 直接插入排序

8.2.2 折半插入排序

8.2.3 希尔排序

8.3 交换排序

8.3.1 冒泡排序

8.3.2 快速排序

8.4 选择排序

8.4.1 简单选择排序

8.4.2 堆排序

堆的调整

堆的建立

8.5 归并排序

8.6 基数排序

8.7 排序方法综合比较

8.8 写在最后

发送评论 编辑评论

推荐文章

发送评论编辑评论