【算法】常见排序算法（插入排序、选择排序、交换排序和归并排序）

前言

1.插入排序（直接插入排序 和 希尔排序）、选择排序（直接选择排序 和 堆排序）、交换排序（冒泡排序 和 快速排序）和归并排序
2.重点内容：快速排序（三个版本的算法思路及代码实现 以及 快速排序的复杂度讨论及其优化方法：随机选取基准值 、三数取中选取基准值 和 三路划分）

一、排序概念及常见排序算法框图

1.排序概念

所谓排序，就是使⼀串记录，按照其中的某个或某些关键数据的大小，递增或递减的排列起来的操作。

2.常见排序算法框图

非比较排序中暂只介绍计数排序

二、实现比较排序算法

1.插入排序

1.1 直接插入排序

直接插入排序是⼀种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到⼀个已经排好序的有序序列中，直到所有的记录插入完为止，得到⼀个新的有序序列 。

void direct_insert_sort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
				break;
		}
		arr[end + 1] = tmp;
	}
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度（按最坏情况）：O(N^2)
3. 空间复杂度：O(1)

1.2 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap（通常 gap = n/2 或 n/3+1，n为数组元素个数），把待排序数据分成gap组，所有的距离相等的数据分在同⼀组内，并对每⼀组内的数据进行插入排序，然后 gap = n/2（或 n/3+1）得到下一个整数，再将数组分成gap组，对每⼀组内的数据排序，当gap=1时，就相当于直接插入排序。
直接插入排序算法的缺陷是它的时间复杂度在最优情况和最差情况下相差极大。希尔排序在直接插入排序算法的基础上进行改进，通过几轮分组排序（轮次越后面的排序，数组会越有序，效率会更高）使数组在最后一轮直接插入排序时接近有序，最后一轮直接插入排序效率会接近O(N)。
综合来说，希尔排序的效率肯定是要高于直接插入排序算法的。

void shell_sort(int* arr, int n)
{
	int gap = n;
	while(gap>1)
	{ 
		gap = gap / 2;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
					break;
			}
			arr[end + gap] = tmp;
		}
	}
}

希尔排序的时间复杂度取决于增量序列的选择（gap划分方法的选择），不同增量序列会导致不同的性能表现：

（1）原始希尔序列（$n/2,n/4,\dots ,1$）

• 最坏情况：$O(n^2)$（与直接插入排序相同）
• 平均情况：实际应用中约为 $O(n^{1.5})$，但缺乏严格证明。

（2）Hibbard 序列（$1,3,7,15,\dots ,2^k-1$）

• 最坏情况：$O(n^{3/2})$
• 平均情况：接近 $O(n^{5/4}))$。

（3）Sedgewick 序列（$1,5,19,41,\dots$）

• 最坏情况：$O(n^{4/3})$
• 平均情况：接近 $O(n{\log }^{2}n)$，是已知最优增量序列之一。

实际应用中，希尔排序通常比 $O(n^2)$ 的算法（如冒泡排序）快得多，但不如 $O(n\log n)$ 的算法（如快速排序、归并排序）。

2.选择排序

2.1 直接选择排序

每⼀次从待排序的数据元素中选出最小（或最大）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

优化版本：每⼀次从待排序的数据元素中选出一组最小值和最大值，分别存放在序列的起始位置和末尾位置，一次可以确定两个元素的位置，直到全部待排序的数据元素排完 。

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void direct_select_sort(int* arr, int n)
{
	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int min = left;
		int max = left;
		int cur = left + 1;
		while (cur <= right)
		{
			if (arr[cur] > arr[max])
				max = cur;
			if (arr[cur] < arr[min])
				min = cur;
			cur++;
		}
		swap(&arr[left], &arr[min]);
		if (left == max)
			max = min;
		swap(&arr[right], &arr[max]);
		left++;
		right--;
	}
}

时间复杂度计算：
第一次遍历n个元素的数组，确认一组最大最小值；
第二次遍历n-2个元素的数组，确认一组最大最小值；
……
最后一次遍历2（或3）个元素的数组。
所以计算式子为：2+4+……+（n-2）+ n = n ^ 2 + n
最终得到时间复杂度为：O(N^2)

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度： O(N^2)
3. 空间复杂度： O(1)

2.2 堆排序

堆是一棵完全二叉树，使用顺序结构的数组来存储数据。堆中某个结点的值总是不大于（或不小于）其父结点的值，将根结点最大的堆叫做大堆或大根堆，根结点最小的堆叫做小堆或小根堆。

核心思想总结
利用堆的性质高效地找到最大值（或最小值）并逐步完成排序。 其核心在于：

1. 构建堆：将无序数组转化为堆结构。
2. 反复提取极值：每次提取堆顶元素后调整堆，最终得到有序序列。

#include <queue>
#include <vector>
using namespace std;

void heap_sort(int* arr, int n)
{
	priority_queue<int,vector<int>,greater<int>> hp; 
	// priority_queue是C++的STL库中自带的堆结构，直接调用priority_queue生成一个小堆。
	// C语言要使用堆排序还需要自己先实现一个堆结构
	for (int i = 0; i < n; i++)
	{
		hp.push(arr[i]); // 先把数组中所有元素插入小堆中（将无序数组转化为堆结构）
	} 
	int i = 0;
	while (!hp.empty())
	{
		arr[i++] = hp.top(); // 每次提取堆顶元素后调整堆，最终得到有序序列
		hp.pop();
	} 
}

堆排序的特性总结:

1. 时间复杂度： $O(n\log n)$
2. 空间复杂度： $O(1)$

3.交换排序

3.1 冒泡排序

冒泡排序的核心思想就是：两两相邻的元素进行比较，满足条件进行交换；一趟冒泡排序确定一个数的位置。

冒泡排序改良：
（1）设置一个变量，让它可以判断一趟冒泡排序中有无进行数组元素交换。
（2）当一趟冒泡排序中无任何一次数组元素交换，说明数组中元素已经有序，这时可提前结束循环。

void bubble_sort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0; // 设置变量exchange，用来判断一趟冒泡排序中有无进行数组元素交换
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				exchange = 1;
				swap(&arr[j], &arr[j + 1]);
			}
		} 
		if(exchange == 0)
		{
			break;
		}
	}
}

时间复杂度计算（按最坏情况）：
每趟冒泡排序确定一个元素的位置，所以n个元素要进行n-1次冒泡排序。
第一趟冒泡排序要进行n-1次比较，确认一个元素的位置；
第二趟冒泡排序要进行n-2次比较（比上一趟少进行一次比较，因为确定了位置的元素无需再进行比较），再确认一个元素的位置；
……
依此类推，第n-1趟冒泡排序只需要进行1次比较
所以计算式子为：1+2+……+（n-2）+（n-1）=（n ^ 2）/ 2 - n/2
最终得到时间复杂度为：O(N^2)

冒泡排序的特性总结:

1. 时间复杂度： O(N^2)
2. 空间复杂度： O(1)

3.2 快速排序

快速排序是Hoare于1962年提出的⼀种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

3.2.1 hoare版本

算法思路 ：

1. 确定基准值（此处直接选择最左元素为基准值），用key标记其下标；创建left和right标记，left起始指向key+1位置，right起始指向末尾位置
2. 从右向左找出比基准值小的数据，用下标right标记；从左向右找出比基准值大的数据，用下标left标记；然后right和left指向的数据互换，进入下次循环；期间一旦left>right，循环直接终止
3. 结束循环后，right所在的位置就是基准值的正确位置，把基准值交换到right位置
4. 以基准值位置划分数组，左边的数组<=基准值，右边的数组>=基准值
5. 接着对左边和右边数组进行以上同样的操作，不断划分数组，直到无法再进行划分
   

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void hoare_quicksort(int* arr, int begin, int end)
{
	int key = begin;
	int left = begin + 1;
	int right = end;
	while (left <= right)
	{
		while (left <= right && arr[right] >= arr[key])
			right--;
		while (left <= right && arr[left] <= arr[key])
			left++;
		if (left <= right)
		{
			swap(&arr[left], &arr[right]);
			right--;
			left++;
		}
	}
	swap(&arr[key], &arr[right]);
	key = right; // [begin，key-1] key [key+1，end]
	if (begin < key - 1)
		hoare_quicksort(arr, begin, key - 1);
	if (key + 1 < end)
		hoare_quicksort(arr, key + 1, end);
}

3.2.2 挖坑法

算法思路 ：

1. 确定基准值（此处直接选择最左元素为基准值），创建变量key保存基准值；创建left和right标记，left起始指向开头位置（起始以left指向位置为"坑"位），right起始指向末尾位置
2. 首先移动right标记从右向左找出比基准值小的数据，找到后立即放入左边"坑"位中，当前位置变为新的"坑"位，然后移动left从左向右找出比基准值大的数据，找到后立即放入右边"坑"位中，当前位置变为新的"坑"，循环进行此过程，过程中一旦left和right相遇，循环立即终止。
3. 结束循环后，当前的"坑"位就是基准值的正确位置，将最开始用变量key存储的基准值放入当前的"坑"位中
4. 以基准值位置划分数组，左边的数组<=基准值，右边的数组>=基准值
5. 接着对左边和右边数组进行以上同样的操作，不断划分数组，直到无法再进行划分
   
   

void digholes_quicksort(int* arr, int begin, int end)
{
	int key = arr[begin];
	int left = begin;
	int right = end;
	while (left < right)
	{
		while (left < right && arr[right] >= key)
			right--;
		if (left == right)
			break;
		else
			arr[left] = arr[right];

		while (left < right && arr[left] <= key)
			left++;
		if (left == right)
			break;
		else
			arr[right] = arr[left];
	}
	arr[right] = key; // [begin，right-1] right [right+1，end]
	if (begin < right - 1)
		digholes_quicksort(arr, begin, right - 1);
	if (right + 1 < end)
		digholes_quicksort(arr, right + 1, end);
}

3.2.3 lomuto前后指针

算法思路 ：

1. 确定基准值（此处直接选择最左元素为基准值），用key标记其下标；创建prev和cur标记，prev起始指向开头位置，cur起始指向prev+1位置
2. 首先移动cur标记从左向右找出比基准值小的数据，找到之后，prev先后移一位，然后将cur和prev指向的数据交换，紧接着cur后移一位，继续循环进行此过程，直到cur越界，循环才终止。
3. 结束循环后，prev所在的位置就是基准值的正确位置，把基准值交换到prev位置
4. 以基准值位置划分数组，左边的数组<=基准值，右边的数组>=基准值
5. 接着对左边和右边数组进行以上同样的操作，不断划分数组，直到无法再进行划分
   
   

void lomuto_quicksort(int* arr, int begin, int end)
{
	int key = begin;
	int prev = begin;
	int cur = prev + 1;
	while (cur <= end)
	{
		while (cur <= end && arr[cur] >= arr[key])
			cur++;
		if (cur <= end)
		{
			prev++;
			swap(&arr[cur], &arr[prev]);
			cur++;
		}
	}
	swap(&arr[key], &arr[prev]);
	key = prev; // [begin，key-1] key [key+1，end]
	if (begin < key - 1)
		lomuto_quicksort(arr, begin, key - 1);
	if (key + 1 < end)
		lomuto_quicksort(arr, key + 1, end);
}

3.3 快速排序的复杂度讨论及其优化

3.3.1 快速排序的复杂度

时间复杂度分析：

1. 最好情况

   • 每次划分都能将数组均匀分成两部分（每次选的基准值都接近中位数）。
   • 递归深度为 $\log n$，每层需遍历 $n$ 个元素（实际就第一层需遍历n个元素，每层递归都会确定一些元素的位置，递归层数越深，需遍历的元素越少，但统一按每层遍历n个元素计算比较方便）。
   • 时间复杂度：$O(n\log n)$。

2. 平均情况

   • 假设基准值通过随机选择或三数取中法选出，划分的均衡性服从概率分布。
   • 数学期望计算后仍为 $O(n\log n)$。
   • 时间复杂度：$O(n\log n)$。

3. 最坏情况

   • 每次划分极不均衡（如数组已有序且固定选第一个元素为基准值）。
   • 递归深度为 $n$，总操作次数为 $n+(n-1)+\cdots +1=\frac{n(n+1)}{2}$。
   • 时间复杂度：$O(n^2)$。

空间复杂度分析：

1. 最好情况

   • 递归深度为 $\log n$，栈空间占用与递归深度成正比。
   • 空间复杂度：$O(\log n)$。

2. 平均情况

   • 递归深度仍为 $\log n$（通过随机化选择基准值减少最坏概率）。
   • 空间复杂度：$O(\log n)$。

3. 最坏情况

   • 递归深度为 $n$（如每次仅处理一个元素）。
   • 空间复杂度：$O(n)$。

• 优化策略：随机选择或三数取中法选择基准值，可有效降低与最坏情况1类似场景（数组有序或部分有序）的时间和空间复杂度 ；三路划分法 可有效降低与最坏情况2类似场景（数组存在大量重复数据）的时间和空间复杂度。
• 空间占用：虽为原地排序，但需注意递归栈的隐式空间消耗。

3.3.2 随机选取基准值 和 三数取中选取基准值

决定快排性能的关键点是每次单趟排序后，基准值对数组的分割，如果每次选的基准值都接近数组中的中位数，那么快排的递归树就是颗均匀的满二叉树，性能最佳。但是实践中虽然不可能每次都是二分居中，但是性能也还是可控的。但是如果出现每次选到最小值/最大值，划分为0个和N-1的子问题时，时间复杂度为O(N^2)，数组有序并且每次固定选第一个元素为基准值前不进行任何干预，就会出现这样的问题。
我们仍然可以采用第一个元素作为基准值的方法，不过在那之前进行随机选取 或 三数取中法选出基准值，再把选出的基准值换到第一个元素，这样可以有效减少因数组有序或部分有序而降低快排效率的情况。

1. 随机选取基准值
   每次排序时，从当前数组中随机选择一个元素作为基准值，再通过交换操作将其移动到数组的起始位置，最后进行常规的划分操作。

#include <time.h>
#include <stdlib.h>
void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void random_select(int* arr, int begin, int end)
{
	srand((unsigned)time(NULL));
	// 随机选择基准值的位置，选择区间在begin和end之间
	int key = rand() % (end - begin + 1) + begin;

	//把基准值位置的元素与begin位置元素互换，后续依然可以选第一个元素为基准值划分函数  
	swap(&arr[key], &arr[begin]);
}

2. 三数取中选取基准值
   从当前子数组的首、中、尾三个位置取元素，选择三者的中位数作为基准值，通过交换操作将其移动到数组的起始位置，最后进行常规的划分操作。

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void median_select(int* arr, int begin, int end)
{
	int mid = begin + ((end - begin) >> 1);//计算数组中间的元素的下标  

	// 使用三数取中法选择三者的中位数作为基准值并将其换到begin位置 
	if (arr[mid] < arr[end])//目标: arr[mid] >= arr[end]  
	{
		swap(&arr[mid], &arr[end]);
	}
	if (arr[begin] > arr[mid])//目标: arr[begin] <= arr[mid]  
	{
		swap(&arr[begin], &arr[mid]);
	}
	if (arr[begin] < arr[end]) //目标: arr[begin] >= arr[end]  
	{
		swap(&arr[begin], &arr[end]);
	}
	//此时，arr[mid] >= arr[begin] >= arr[end]  
    //begin位置上保存这三个位置中间的值，后续依然可以选第一个元素为基准值划分函数  
}

3.3.3 三路划分

快速排序的三路划分是一种优化策略，用于处理数组中存在大量重复元素的情况。 它将数组划分为三个区域：

• 小于基准值的部分（左段）
• 等于基准值的部分（中段）
• 大于基准值的部分（右段）

通过将重复元素集中到中间段，后续递归时只需处理左右两段，避免对重复元素重复操作，从而提升效率。

算法思路（类似hoare的左右指针和lomuto的前后指针的结合） ：

1. 确定基准值（直接选择最左元素为基准值），创建变量key保存基准值；创建 left、right 和 cur 标记，left起始指向开头位置，right起始指向末尾位置，cur起始指向left+1位置
2. cur标记从左向右移动会遇到三种不同的情形，每种情形都会有对应的处理方式：

• 情形一：cur遇到比基准值小的值后跟left位置交换，换到左边，left++，cur++；
• 情形二：cur遇到比基准值大的值后跟right位置交换，换到右边，right–；
• 情形三：cur遇到跟基准值相等的值后，cur++。

3. 直到cur > right才结束以上过程
4. 以 left 和 right位置划分数组，左边的数组<基准值，右边的数组>基准值
5. 接着对左边和右边数组进行以上同样的操作，不断划分数组，直到无法再进行划分
   

4.归并排序

4.1 归并排序的思想及实现

归并排序算法思想：
归并排序（MERGE-SORT）是建立在归并操作上的⼀种有效的排序算法,该算法是采用分治法的⼀个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成⼀个有序表，称为二路归并。

void merge_sort(int* arr, int begin, int end, int* tmp)
{
	int mid = begin + (end - begin) / 2;
	if (begin < mid)
		merge_sort(arr, begin, mid, tmp);
	if (mid + 1 < end)
		merge_sort(arr, mid + 1, end, tmp);
	int left1 = begin;
	int right1 = mid;
	int left2 = mid + 1;
	int right2 = end;
	int n = begin;
	while (left1 <= right1 && left2 <= right2)
	{
		if (arr[left1] <= arr[left2])
			tmp[n++] = arr[left1++];
		else
			tmp[n++] = arr[left2++];
	}
	while (left1 <= right1)
	{
		tmp[n++] = arr[left1++];
	}
	while (left2 <= right2)
	{
		tmp[n++] = arr[left2++];
	}
	while (begin <= end)
	{
		arr[begin] = tmp[begin];
		begin++;
	}
}

三、比较排序算法总结

1.复杂度及稳定性分析

$$\begin{array}{lccccc}\text{算法}& \text{最好}& \text{最坏}& \text{平均时间复杂度}& \text{空间}& \text{稳定}\\ 冒泡排序& O(n)& O(n^2)& O(n^2)& O(1)& ✓\\ 直接插入排序& O(n)& O(n^2)& O(n^2)& O(1)& ✓\\ 归并排序& O(n\log n)& O(n\log n)& O(n\log n)& O(n)& ✓\\ 直接选择排序& 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^2)& O(n^{1.3})& O(1)& ✗\\ 快速排序& O(n\log n)& O(n^2)& O(n\log n)& O(\log n)& ✗\end{array}$$

2.测试代码：比较排序性能对比

用以上各种比较排序算法排序同一组随机生成的数据，测试时间（单位：毫秒）消耗，要在Release版本运行这段代码（含递归的算法会在Debug版本生成更多调试数据，影响算法效率）:

#include "sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void TestOP()
{
	srand(time(0));
	const int N = 50000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	int* tmp = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
	} 
	int begin1 = clock();
	direct_insert_sort(a1, N);
	int end1 = clock();
	int begin2 = clock();
	shell_sort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	direct_select_sort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	heap_sort(a4, N);
	int end4 = clock();
	int begin5 = clock();
	hoare_quicksort(a5, 0, N - 1);
	int end5 = clock();
	int begin6 = clock();
	merge_sort(a6, 0, N - 1, tmp);
	int end6 = clock();
	int begin7 = clock();
	bubble_sort(a7, N);
	int end7 = clock();
	printf("direct_insert_sort:%d\n", end1 - begin1);
	printf("shell_sort:%d\n", end2 - begin2);
	printf("direct_select_sort:%d\n", end3 - begin3);
	printf("heap_sort:%d\n", end4 - begin4);
	printf("hoare_quicksort:%d\n", end5 - begin5);
	printf("merge_sort:%d\n", end6 - begin6);
	printf("bubble_sort:%d\n", end7 - begin7);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	free(tmp);
}

int main()
{
	TestOP();
	return 0;
}

四、实现非比较排序算法

1.计数排序

计数排序是对哈希直接定址法的变形应用。 操作步骤：
1）统计相同元素出现次数
2）根据统计的结果将序列回收到原来的序列中

"找出最大值k，创建长度为k+1的计数数组"的方式有些时候会造成很大空间浪费，可以找出待排序数组中的最大最小值，按范围开空间：

void count_sort(int* arr, int n)
{
	int min = arr[0], max = arr[0];
	for (int i = 1; i < n; i++)
	{
		if (arr[i] > max)
			max = arr[i];
		if (arr[i] < min)
			min = arr[i];
	} 
	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		perror("calloc fail");
		return;
	}
	// 统计次数
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++; 
	} 

	// 排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[j++] = i + min;
		}
	}
	free(count);
}