代码探险家

这个屌丝很懒，什么也没留下！

热门标签

常见的七个排序算法：冒泡，直接插入，希尔，选择，堆，归并，快速排序。

作者：代码探险家 | 2024-08-23 07:14:54

踩

在本文开始前，先给大家推荐一个助于你理解各种排序的网站（通过动画可视化数据结构和算法）里面有各种排序的动画，非常直观。

一. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，它的核心思想是通过重复地遍历要排序的列表，比较每一对相邻元素的值，若顺序错误就把它们交换过来。这个过程重复进行，直到没有需要交换的元素为止。也就是列表已经排好序。这个算法得名于较大/小的元素会像气泡一样逐渐“浮”到列表的顶端。

冒泡排序的算法步骤如下：

比较相邻的元素。如果第一个比第二个大（为了排序成升序），就交换它们两个。
对每一对相邻元素做同样的操作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

具体过程如下：

1. 冒泡排序实现


void BubbleSort(int* a, int n) {
	for (int j = 0; j < n - 1; j++)
	{
		for (int i = 0; i < n - j - 1; i++)
		{
			if (a[i] > a[i+1])    // 第一个比第二个大，交换
			{
				int tmp = a[i+1];
				a[i+1] = a[i];
				a[i] = tmp;
			}
		}
	}
}

虽然冒泡排序是一种容易理解和实现的基本排序算法，但它在实际应用中效率不高，特别是在处理大数据集时。

但是可以在排序里增加一个 flag ，如下所示，这样就可以检查进行过数据交换，降低列表已经有序时（如【1，2，3，4，5，6，7】）时间复杂度。


void BubbleSort(int* a, int n) {
	for (int j = 0; j < n - 1; j++)
	{
		// bool flag = true;
		for (int i = 0; i < n - j - 1; i++)
		{
			if (a[i] > a[i+1])
			{
				// flag = false;
				int tmp = a[i+1];
				a[i+1] = a[i];
				a[i] = tmp;
			}
		}
	}
}

冒泡排序的稳定性：

冒泡排序是针对相邻的元素且存在相对大小时才交换元素位置，对于大小相等的相邻元素，不会交换两者位置，因此，冒泡排序是稳定的。

2. 冒泡排序时间，空间复杂度

最优情况：O( $n$ )；即一组完全顺序的数据。
最差情况：O( $n^{2}$ )；即一组完全逆序的数数据。
平均情况：O( $n^{2}$ )；

因为没有额外开辟空间，所以它的空间复杂度为O(1)。

二. 直接插入排序（Insertion Sort）

直接插入排序是一种简单的排序算法：它的核心思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到所有的记录都排好序为止。

直接插入排序的算法步骤如下：

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到该位置后。
重复步骤2~5。

具体过程如下：

1. 插入排序实现


void InsertSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];    // 将第一个元素视为有序，从第二个元素开始
		while (end >= 0)
		{
			if (tmp < a[end])    // 比新元素大，往后移
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}

由于它的简单性，直接插入排序在元素数量较少时非常高效，特别是在部分已排序的数组中效果很好。

直接插入排序的稳定性：

在排序过程中，如果遇到相同的元素，新元素会被放置在相同元素之后，保持它们原有的相对次序，因此，插入排序是稳定的。

2. 插入排序时间，空间复杂度

最优情况：O( $n$ )；即一组完全顺序的数据。
最差情况：O( $n^{2}$ )；即一组完全逆序的数数据。
平均情况：O( $n^{2}$ )；

因为没有额外开辟空间，所以它的空间复杂度为O(1)。

三. 希尔排序（Shell's Sort）

希尔排序是一种高效的插入排序算法，也称为缩小增量排序算法。它是对直接插入排序算法的一种优化：希尔排序的核心思想是：对于给定的一组待排序记录，首先将其分割成几个子序列，每个子序列中记录的个数相对较小，然后对这些子序列分别进行直接插入排序，使它们有一定的基本有序性。接着，对所有子序列重新归并为一个序列，再对这个序列进行一次直接插入排序即可。

希尔排序的算法步骤如下：

选择一个增量序列（代码中的 gap ），逐步缩小增量。
对于每个增量，将列表分成若干个子列表。
对每个子列表进行插入排序。
重复步骤2和步骤3，直到增量为1。
最后进行一次完整的插入排序，完成排序。

具体过程如下：

需要注意的是增量序列的最后一个增量值 gap 必须是 1

1. 希尔排序实现


void ShellSort(int* a, int n) {
	int gap = n;
	while (gap > 1)    // 当 gap < 1,说明已经排完序。
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end = end - gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}
}

可以看出，希尔排序其实就是对直接插入排序的改进。它的优点是比较次数相对较少，且可以提前发现并确定元素的大致位置，从而减少后期排序时元素的移动次数。缺点是需要一定的辅助空间，且在小规模数据集上效率并不理想。

希尔排序的稳定性：

在希尔排序中，每次对子列表进行插入排序时，元素的比较和交换是跨越较大间隔进行的。这样会导致相同元素之间的相对顺序可能发生改变。因此，希尔排序是不稳定的。

2. 希尔排序时间，空间复杂度

希尔排序的效率取决于增量值gap的选取，时间复杂度并不是一个定值。但在一般情况下：

最优情况：O( $n$ )
最差情况：O( $n^{2}$ )
平均情况：O( $n^{1.3}$ )

因为没有额外开辟空间，所以它的空间复杂度为O(1)。

四. 选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的核心思想是每次从未排序的部分中选择最小（或最大）的元素，然后将它与未排序部分的第一个元素交换位置，从而逐步将列表划分为已排序和未排序两部分。

选择排序的算法步骤如下：

遍历未排序部分，找到最小（或最大）的元素。
将最小（或最大）元素与未排序部分的第一个元素交换位置。
将已排序部分的末尾指针向后移动一位，将未排序部分的起始指针向后移动一位。
重复步骤1~3，直到未排序部分为空。

具体过程如下：

1. 选择排序实现


void SelectSort(int* a, int n) {
	for (int j = 0; j < n - 1; j++)
	{
		int mini = j;    // 选定一个最小元素
		for (int i = j + 1; i < n; i++)
		{
			if (a[i] < a[mini])    // 若遇见更小的，更新 mini
				mini = i;
		}
		if (j != mini)
			Swap(&a[j],&a[mini]);    // 交换二者位置
	}
}

选择排序是一种简单且稳定的排序算法,适用于数据量较小的情况。但大部分情况下，效率并不是很理想，一般用于对小规模数据的排序或作为其他复杂排序算法的辅助过程。

选择排序的稳定性：

在选择排序中，每次选择最小（或最大）的元素，并与未排序部分的第一个元素交换位置。这样可能导致相同元素的相对顺序发生改变。因此，选择排序是不稳定的。

2. 选择排序时间，空间复杂度

最优情况：O( $n^{2}$ )
最差情况：O( $n^{2}$ )
平均情况：O( $n^{2}$ )

可以看到，三种情况的时间复杂度都一样，所以堆的初始状况并不会影响排序效率，为 O( $n^{2}$ ) ，这是因为无论输入数据的顺序如何，都需要进行 n(n-1) / 2 次比较和交换操作。

因为没有额外开辟空间，所以它的空间复杂度为O(1)。

五. 堆排序（Heap Sort）

堆排序是一种基于堆数据结构的排序算法。它的核心思想是通过利用堆的性质来进行排序，通过构建最大堆或最小堆来实现升序或降序排序。

堆排序算法步骤如下：

构建最大堆（升序排序）或最小堆（降序排序）。
交换堆顶元素与堆的最后一个元素。
调整堆，使其满足堆的性质。
重复步骤2和步骤3，直到堆的大小为1。

具体过程如下：

1. 堆排序实现

首先我们思考一个问题，堆排序升序中要用到的堆，我们是建大顶堆(max heap)还是小顶堆(min heap)？

答案是大顶堆：这主要是因为大顶堆的根结点是整个堆中值最大的结点。通过不断地将根结点与堆尾元素交换,并重新调整剩余元素构建新的大顶堆,可以确保每次交换都将当前未排序部分中的最大值放到了正确的位置。

同理，排降序时，用小顶堆。


// 将用到的向下调整函数
void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = child * 2 + 1;
			parent = parent * 2 + 1;
		}
		else
			break;
	}
}
// 堆排序
void HeapSort(int* a, int n)
{
	// 建大堆排升序
	for (int i = (n - 2) / 2; i >= 0; --i)
		AdjustDown(a, n, i);
 
	int end = n - 1;    // 数组大小 - 1
	while (end > 0)
	{
		Swap(&a[0], &a[end]);    // 将堆顶与堆尾数据交换，然后再重构堆
		AdjustDown(a, end, 0);
		--end;
	}
}

堆排序的效率相对较高，适用于大规模数据的排序。

堆排序的稳定性：

堆排序因为在构建初始堆和重新构建堆的过程中，会出现父节点和子节点的交换操作，这种交换是无序的，很可能打乱了相同键值记录的相对次序。因此，堆排序是不稳定的。

2. 堆排序时间，空间复杂度

最优情况：O( $n\log n$ )
最差情况：O( $n\log n$ )
平均情况：O( $n\log n$ )

和选择排序一样，三种情况的时间复杂度都一样，所以数据列表的初始状况并不会影响排序效率。

计算堆排序的时间复杂度，要分两个部分，一个是建立堆的时间复杂度，为 O( $n$ )，还有一个是排序过程的时间复杂度，为 O( $n\log n$ ),因此堆排序过程的时间复杂度为:

O( $n$ )+O( $n\log n$ ) = O( $n\log n$ )。

因为没有额外开辟空间，所以它的空间复杂度为O(1)。

六. 归并排序（Merge Sort）

归并排序是一种高效的排序算法，它是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序的核心思想是将一个大的无序数组不断地拆分成较小的数组，直到每个小数组只有一个元素为止。接着将这些小数组按照规则合并为较大的有序数组，最终合并所有小数组就可以得到一个完整的有序序列。

归并排序的算法步骤如下：

分解：将一个大的无序数组不断地对半拆分,直到每个小数组只有一个元素为止。
合并：将相邻的两个小数组合并为一个较大的有序数组。具体做法是对两个小数组遍历,每次从两个有序的小数组中取出一个较小值的元素存入新的有序数组中,直到有一个小数组为空为止。
拆分和合并：重复上述步骤,不断地将较小的有序数组合并为较大的有序数组,直到最终将整个无序数组合并为一个完整的有序序列。

具体过程如下：

1. 归并排序（递归版）实现

归并排序的实现有两种方式：1.迭代，2.递归。

下面介绍递归的方式：


// 用来实现归并排序的主要逻辑
void _MergeSort(int* a, int begin, int end, int* tmp) {
	if (begin >= end)
		return;
	int mid = (begin + end) / 2;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
	int begin1 = begin, end1 = mid, begin2 = mid + 1, end2 = end,i = begin;
	// 排序
	while (begin1 <= end1 && begin2 <= end2)    // 当左右子数组都没有元素时，退出循环
	{
		if (a[begin1] <= a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	while (begin1 <= end1)    
		tmp[i++] = a[begin1++];    // 将左子数组剩余元素复制到临时数组中
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];    // 将右子数组的剩余元素复制到临时数组中
	// 把tmp拷贝给a
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
 
// 归并排序
void MergeSort(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);    // 创建一个临时数组 tmp ，用于存放合并后的结果
	if (tmp == NULL)
	{
		perror("malloc");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);
}

需要注意的是,这个实现使用了递归,对于较大的数据集可能会导致栈溢出。在实际应用中,可以考虑使用非递归的实现方式或者对递归进行优化,以提高性能和稳定性。

归并排序的稳定性：

归并排序使用了"分治"思想，将原始数组分成较小的数组进行递归操作。在合并两个已排好序的子数组时，归并排序会先比较两个子数组中的第一个记录。如果两个记录的值相等，那么算法会先把位于左侧子数组中的记录复制到合并后的数组中，这就保证了相等键值的记录前后顺序不变。因此，归并排序是稳定的。

2. 归并排序时间，空间复杂度

最优情况：O( $n\log n$ )
最差情况：O( $n\log n$ )
平均情况：O( $n\log n$ )

可以看到三种情况的时间复杂度都一样，所以数据列表的初始状况并不会影响排序效率。

计算归并排序的时间复杂度，要分三个部分

1. 分解阶段的时间复杂度是 O( $\log n$ ) 2. 合并阶段的时间复杂度是 O( $n$ ) 3. 递归深度是O( $\log n$ )，因此，总的时间复杂度是：O( $\log n$ ) * O( $n$ ) = O( $n\log n$ )。

在整个归并排序过程中,除了需要存储原始数组本身需要 O( $n$ ) 的空间外,还需要辅助数组占用 O( $n$ ) 的空间,因此总的空间复杂度为 O( $n$ )+O( $n$ ) = O( $n$ )。

七. 快速排序（Quick Sort）

快速排序是一种高效的排序算法，是一种基于分治策略的排序算法，运行高效，应用广泛。
快速排序的核心思想是“分治思想”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

快速排序的算法步骤如下：

选择一个元素作为基准点。
将列表划分为两个子列表：一个包含所有小于基准点的元素，另一个包含所有大于基准点的元素。
对两个子列表递归地应用快速排序。
将排序后的两个子列表合并为一个已排序的列表。

具体过程如下：

1. 快速排序实现

1.1 Hoare版本（直接交换）


void QuickSort1(int* a, int begin, int end) {
	if (begin >= end)
		return;
	int left = begin, right = end;
	int key = begin;
	while (left < right)    // 直到要查找的元素重合
	{
		while (left < right && a[key] <= a[right])
			right--;    // 从右向左找首个小于 基准数 的元素
		while (left < right && a[key] >= a[left])
			left++;    // 从左向右找首个大于 基准数 的元素
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[key]);    // 将基准数交换至两子数组的分界线
	key = right;
 
	// key 将数据列表分为两个部分：[left, key - 1] key [key + 1, right]  
    // 先向左递归子数组，再向右递归。  
	QuickSort1(a, begin, key - 1);    
	QuickSort1(a, key + 1, end);
}

基准数优化

在快速排序中：基准数的选取尤为重要，会极大的影响排序的时间效率，例如，我们可以随机选取一个元素作为基准数。然而，如果运气不佳，每次都选到不理想的基准数，效率仍然不尽如人意。
为了进一步改进，我们可以用三数取中法：在数组中选取三个候选元素（通常为数组的首、尾、中点元素）， 并将这三个候选元素的中位数作为基准数。这样一来，基准数“既不太小也不太大”的概率将大幅提升。

这种改进方法如下：


// 三数取中优化法
int GetMid(int* a, int begin, int end) {
	int mid = (begin + end) / 2;
	if (a[begin] <= a[mid])
	{
		if (a[mid] <= a[end])
			return mid;
		else if (a[end] <= a[begin])
			return begin;
		else
			return end;
	}
	else
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[begin] > a[end])
			return end;
		else
			return begin;
	}
}
 
// 优化后
void QuickSort1(int* a, int begin, int end) {
	if (begin >= end)
		return;
	int mid = GetMid(a, begin, end);
    // 三数取中后，将中位数交换至数组最左端
	Swap(&a[begin], &a[mid]);
	int left = begin, right = end;
	int key = begin;
	while (left < right)
	{
		while (left < right && a[key] <= a[right])
			right--;    
		while (left < right && a[key] >= a[left])
			left++;     
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[key]);    
	key = right;
	QuickSort1(a, begin, key - 1);
	QuickSort1(a, key + 1, end);
}

下面两种方法都会用到三数取中法：

1.2 挖坑法


void QuickSort2(int* a, int begin, int end) {
	if (begin >= end)
		return;
	int mid = GetMid(a, begin, end);
	Swap(&a[begin], &a[mid]);     // 三数取中后，将中位数交换至数组最左端
	int left = begin, right = end;
	int key = a[begin];
	while (left < right)
	{
		while (left < right && key <= a[right])    // 右边找小，填到左边的坑
			right--;
		a[left] = a[right];
		while (left < right && key >= a[left])    // 左边找大，填到右边的坑
			left++;
		a[right] = a[left];
	}
	a[left] = key;
	key = right;
	//[left, keyi - 1] keyi [keyi + 1, right]
	QuickSort2(a, begin, key - 1);
	QuickSort2(a, key + 1, end);
}

1.3 前后指针法


void QuickSort3(int* a, int begin, int end) {
    // 如果数组只有一个元素或没有元素，则直接返回
	if (begin >= end)
		return;
	int mid = GetMid(a, begin, end);
	Swap(&a[begin], &a[mid]);     // 三数取中后，将中位数交换至数组最左端
	int prev = begin;    // 指向小于基准元素的部分的最后一个位置
    cur = prev + 1;    // 当前移动的元素
    key = begin;
	while (cur <= end)    // 如果当前元素小于基准元素，就将它交换到 prev 的下一个位置
	{
		if (a[cur] < a[key] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
		cur++;
	}
	Swap(&a[prev], &a[key]);
	key = prev;
    // 先递归左子序列，再递归右
	QuickSort3(a, begin, key - 1);
	QuickSort3(a, key + 1, end);
}

总的来说,快速排序是实用的高效排序算法,在大数据量的排序中有着良好的表现。但在小数据量和特殊序列分布时,还需结合其他算法来提高效率。

快速排序的稳定性：

快速排序在每次分区时，我们会选择一个基准元素，然后将小于基准的元素放到基准前面，大于基准的元素放到基准后面。对于等于基准的元素，有些实现方式会将它们全部放到小于基准的一侧，有些实现方式会将它们全部放到大于基准的一侧。这就导致了相等元素的相对次序发生了改变。因此，快速排序是不稳定的。

2. 快速排序时间，空间复杂度

最优情况：O( $n\log n$ )；每次选择基准都能将序列均匀分为两半。
最差情况：O( $n^{2}$ )；每次选择基准都是序列中最大或最小的元素,导致每次只有一部分元素被划分,另一部分是空的。
平均情况：O( $n\log n$ )；

由于快速排序使用了递归调用的方式，需要借助栈来存储每一层递归时的状态。因此，快速排序的空间复杂度取决于递归调用的深度，在平均情况下为O( $\log n$ )。

下面是各个算法的性能比较：

排序方法	时间复杂度(最优)	时间复杂度(平均)	时间复杂度(最差)	空间复杂度	稳定性
冒泡排序	O( $n$ )	O( $n^{2}$ )	O( $n^{2}$ )	O(1)	稳定
插入排序	O( $n$ )	O( $n^{2}$ )	O( $n^{2}$ )	O(1)	稳定
希尔排序	O( $n$ )	O( $n^{1.3}$ )	O( $n^{2}$ )	O(1)	不稳定
选择排序	O( $n^{2}$ )	O( $n^{2}$ )	O( $n^{2}$ )	O(1)	不稳定
堆排序	O( $n\log n$ )	O( $n\log n$ )	O( $n\log n$ )	O(1)	不稳定
归并排序	O( $n\log n$ )	O( $n\log n$ )	O( $n\log n$ )	O( $n$ )	稳定
快速排序	O( $n\log n$ )	O( $n\log n$ )	O( $n^{2}$ )	O( $\log n$ )	不稳定

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/1020013