常见排序算法的实现

1. 冒泡排序

最基础的排序算法，没什么实际意义，适合小白应付学校教学考察。
通过不断交换相邻的元素，把大的元素逐渐“浮”到数组的末尾，就像气泡一样冒上来。

1.1 基本原理

• 相邻比较：从数组首端开始，依次比较相邻元素。若前一个元素大于后一个，则交换它们。
• 一轮冒泡：每轮遍历后，当前未排序部分的最大元素会被移动到正确位置（数组末尾）。
• 重复与终止：重复上述过程，每次缩小未排序范围。若某轮未发生交换，说明数组已有序，提前终止。
  

1.2 算法特性

• 时间复杂度：
  • 最坏 & 平均：O(N²)（完全逆序或随机）
  • 最好：O(N)（已有序且优化后）
• 空间复杂度 O(1) （原地排序）
• 稳定性：稳定（相等元素不交换）

1.3 优化策略

• 提前终止：若某轮未发生交换，说明数组已有序，直接结束排序。

1.4 代码实现

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

---

2. 插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，其核心思想是将待排序元素逐个插入到已排序序列的合适位置，类似于整理扑克牌时一张张调整牌的顺序。算法通过逐步构建有序序列实现整体排序。

2.1 基本原理

1. 分区思想：将数组分为已排序（左）和未排序（右）两部分，初始时已排序区仅含第一个元素。
2. 元素抓取：逐个从未排序区取首个元素，向已排序区反向扫描寻找插入位置。
3. 插入操作：通过后移比当前元素大的元素，腾出空位完成插入，保持已排序区始终有序。
   

2.2 算法特性

• 时间复杂度：
  • 最坏 & 平均：O(N²)（完全逆序）
  • 最好： O(n)（已有序时仅遍历一次）
• 空间复杂度：O(1)（原地操作）
• 稳定性：稳定（相等元素不跨跃交换）

2.3 优化策略

1. 二分插入：用二分查找定位插入点，减少比较次数（但移动次数不变，整体仍为O(n²)）。
2. 哨兵优化：在数组头部预置极小值作为哨兵，省去越界检查。

2.4 代码实现

// 非优化版本
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int tmp = a[i]; // 选取未排序的元素
		int j;
		for (j = i - 1; j >= 0 && tmp < a[j]; j--) 
			a[j + 1] = a[j]; // 查找到比当前元素更大的元素，就将其往后移，直到有元素比当前元素小就跳出循环
		a[j + 1] = tmp; // 将查找到的比当前元素小的位置的后面那个元素设置为选取的当前元素
	}
}

---

3. 希尔排序

希尔排序是插入排序的改进版，通过分组插入来实现，时间复杂度介于O(n)和O(n²)之间，具体取决于间隔序列的选择。关键点包括分组的策略、间隔序列的影响、排序过程的分阶段处理等。

3.1 基本原理

1. 分治优化思想：基于插入排序，通过分组插入逐步逼近全局有序，减少元素移动次数。
2. 增量序列：定义递减的间隔（gap），每组按间隔进行插入排序。常用序列有：
   • 希尔增量：gap = n/2, n/4, …, 1
   • Hibbard增量：2^k -1（更优时间复杂度）
3. 逐步细化：大间隔快速粗调元素位置，小间隔微调至完全有序。
   

3.2 算法特性

• 时间复杂度
  • 依赖增量序列，平均O(n log n) ~ O(n²)。
  • Hibbard增量可达 O(n^(3/2))。
• 空间复杂度：O(1)（原地排序）。
• 稳定性：不稳定（分组导致跨元素交换）。

3.3 优化策略

1. 增量序列选择：
   • Sedgewick序列：9×4ⁱ - 9×2ⁱ+1，综合性能最优（O(n^(4/3))）。
   • Knuth序列：(3^k -1)/2。
2. 预计算序列：对超大数组提前计算最优增量序列。

3.4 代码实现

void ShellSort(int* a, int n)
{
	// 初始间隔gap为数组长度的一半，逐步减小到1
	for (int gap = n / 2; gap > 0; gap /= 2)
	{
		// 对每个子序列进行插入排序
		for (int i = gap; i < n; i++)
		{
			int tmp = a[i]; // 当前待插入元素
			int j;
			// 将元素插入到正确位置
			for (j = i; j >= gap && a[j - gap] > tmp; j -= gap)
			{
				a[j] = a[j - gap]; // 将较大的元素后移
			}
			a[j] = tmp; // 将元素插入到正确位置
		}
	}
}

---

4. 选择排序

选择排序的基本思想是每次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾。这个过程不断重复，直到所有元素排序完毕。

4.1 基本原理

1. 分区策略：将数组分为已排序区（左）和未排序区（右），初始时已排序区为空
2. 极值选择：每轮从未排序区中选出最小元素（或最大，默认升序用最小）。
3. 交换定位：将选中的最小元素与未排序区的首个元素交换，扩展已排序区边界。
   

4.2 算法特性

• 时间复杂度：
  • 所有情况均为O(n²)（无论输入是否有序，必须完整比较）。
• 空间复杂度：O(1)（原地交换，无需额外空间）。
• 稳定性：不稳定（跨位置交换可能破坏原有顺序，如 [5, 5, 2]）。

4.3 优化策略

1. 双向选择（双极值）：
   • 每轮同时选出最小和最大元素，分别置于未排序区首尾。
   • 减少总轮数（从n-1轮降至≈n/2轮），但单轮比较次数略增。
2. 跳跃记录法：
   • 记录最小值索引，每轮结束后仅交换一次，减少交换次数（基础版已实现此优化）。

4.4 代码实现

// 双向选择版
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;

	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			// 找出数值最大和最小的下标
			if (a[i] > a[maxi]) maxi = i;
			if (a[i] < a[mini]) mini = i;
		}
		Swap(&a[begin], a[mini]);
		Swap(&a[end], a[maxi]);
		++begin;
		--end;
	}
}

5. 堆排序

堆排序是基于完全二叉树的特性，通过建堆与堆删除实现的排序方法。
建堆和堆删除都得理解向下调整算法，具体的可以看我上一篇【数据结构】二叉树、堆，这里便不再过多讲解。

5.1 基本原理

1. 堆结构利用：基于完全二叉树的大顶堆（父节点≥子节点）或小顶堆特性。
2. 两步走策略：
   • 建堆阶段：将无序数组调整为堆结构。
   • 排序阶段：重复将堆顶元素（最大值）与末尾交换，缩小堆范围并重新调整。
3. 下沉操作（Heapify）：当堆顶被替换后，自上而下递归调整以维持堆性质。

5.2 算法特性

• 时间复杂度：
  • 建堆：O(N)（Floyd算法）
  • 排序：O(N logN)（每次Heapify为O(log n)，共n-1次）
  • 总体O(N log N)（所有情况一致）
• 空间复杂度：O(1)（原地排序）
• 稳定性：不稳定（跨层交换破坏顺序，如 [5,5,2]）

5.3 代码实现

void AdjustDown(int* a, int n, int parent)
{
	// 先假设左孩子小
	int child = parent * 2 + 1;
	while (child < n)  // child >= n说明孩子不存在，调整到叶子了
	{
		// 找出小的那个孩子
		if (child + 1 < n && a[child + 1] > a[child])
			++child;
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

void HeapSort(int* a, int n)
{
	// 向下调整建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

6. 快速排序

快速排序（Quick Sort）是一种基于分治法的高效排序算法，核心思想是选定基准元素（key），将数组划分为“小等于基准”和“大等于基准”两部分，递归排序子数组。
快速排序的每一次分区操作都会确定一个元素的最终位置（即基准元素的位置），其他元素的位置后续递归处理

6.1 基本原理

1. 分治策略：
   • 分解：选取基准值（key），将数组划分为左（≤key）和右（≥key）两个子数组。
   • 征服：递归对左右子数组排序。
   • 合并：天然有序，无需额外操作。
2. 核心操作：
   • 分区（Partition）：通过交换使元素围绕基准值分布，决定分割点。
   • 基准选择：常见方法包括首元素、随机元素、三数取中等。

6.2 算法特性

• 时间复杂度：
  • 平均：O(N logN)（理想平衡划分）。
  • 最坏：O(N²)（如已有序数组+固定首元素基准）。
• 空间复杂度：
  • 递归栈：O(logN)（优化后） ~ O(N)（最坏）。
• 稳定性：不稳定（跨分区交换破坏顺序）。

6.3 优化策略

1. 基准选择优化：
   • 三数取中：选首、中、尾的中位数作为基准，减少不平衡风险。
   • 随机化：随机选基准，避免人为数据攻击。
2. 小区间优化：
   • 当子数组长度<10时切换为插入排序，减少递归开销。
3. 三路划分
4. 迭代法消除递归栈

6.4 单趟排序的实现方式

霍尔版本

1. 初始指针设定
   • 选择数组首元素为基准（key，通常需优化选择方式）。
   • 设置两个指针：left（从第二个元素开始）和 right（从最后一个元素开始）。
2. 双向扫描与交换
   • 左指针右移：找到第一个 ≥ key 的元素。
   • 右指针左移：找到第一个 ≤ key 的元素。
   • 交换元素：若 left ≤ right，交换两指针指向的元素，继续扫描；否则终止循环。
3. 基准位置确定
   • 最终将 key 与 right 指针位置交换，返回 right 作为分区点。
4. 递归排序：对基准左右子数组重复上述过程。

关于霍尔版本中，值得一说的就是指针移动顺序与基准位置的关系。

当基准元素在左边的时候：

• 操作顺序：右指针先移动，再移动左指针
• 原因：
  • 若基准元素在左侧，右指针需要先找到一个 <= 基准的元素，确保左指针不会越过基准导致错误交换
  • 右指针优先移动可以避免左指针直接跳过基准元素，从而保证分区逻辑的正确性。

相反，若是基准元素在右边的时候：

• 操作顺序：左指针先移动，再移动右指针

• 原因与上面同理。

若是觉得实在难以理解，那么我还是建议同学自己手动画一下图，图像带来的感受是比文字更直观的。

挖坑法

通过动态“挖坑”与填坑操作，逐步确定基准元素的最终位置，减少元素交换次数。

1. 选择基准：通常选择数组首元素为基准（需优化），将其值保存为 key，原位置视为初始“坑”。
2. 双指针扫描：
   • 右指针左移：从右向左找到第一个 < key 的元素，填入左坑，右指针位置成为新坑。
   • 左指针右移：从左向右找到第一个 > key 的元素，填入右坑，左指针位置成为新坑。
3. 重复填坑：交替移动左右指针，直至两指针相遇，将 key 填入最终坑位。
4. 递归排序：对基准左右子数组重复上述过程。

挖坑法中基准元素位置的选取与左右双指针的移动顺序与上面霍尔版本是一样的。
都是确保分区逻辑正确的关键，若忽略指针顺序与基准位置的匹配关系，将导致排序错误或死循环。

6.5 代码实现

// 三数取中 + 小区间优化版

// 三数取中
int GerMidi(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right]) return midi;
		else if (a[left] < a[right]) return right;
		else return left;
	}
	else // a[left] > a[midi]
	{
		if (a[midi] > a[right]) return midi;
		else if (a[left] < a[right]) return left;
		else return right;
	}
}

// 霍尔版本
int PartSort1(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]); // 因为这里是选择左边作为key，所以将取到的与最左元素交换
	int keyi = left;
	int begin = left, end = right;
	while (begin < end)
	{
		// 右边找小
		while (begin < end && a[end] >= a[keyi]) --end;
		// 左边找大
		while (begin < end && a[begin] <= a[keyi]) ++begin;

		Swap(&a[begin], &a[end]);
	}
	Swap(&a[keyi], a[begin]);
	return begin;
}

// 挖坑法
int PartSort2(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);
	int keyi = left;

	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		cur++;
	}

	Swap(&a[prev], &a[keyi]);
	return prev;
}

// 避免有序情况下，效率退化
// 1、 随机选key
// 2、 三数取中
void QuickSort(int* a, int left, int right)
{
	if (left >= right) return;

	// 小区间优化，不再递归分割排序，减少递归的次数
	if ((right - left + 1) < 10)
		InsertSort(a + left, right - left + 1);
	else
	{
		// int keyi = PartSort1(a, left, right);
		int keyi = PartSort2(a, left, right);
		
		// [left, keyi-1] keyi [keyi+1, right]
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

#include "Stack.h"
// 非递归
void QuickSortNonR(int* a, int left, int right)
{
	// 循环没走一次 (相当于之前的递归)
	// 取栈顶区间，但趟排序，右左子区间入栈

	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = PartSort2(a, begin, end);
		// [begin, keyi-1] keyi [keyi+1, right]
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}

		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}
}

7. 归并排序

归并排序（Merge Sort）是一种基于分治法的高效排序算法。

7.1 基本原理

• 分治三步骤：
  1. 分：递归将数组二分为子数组，直到每个子数组仅含一个元素（天然有序）。
  2. 治：逐层合并相邻有序子数组，生成更大有序数组。
  3. 合：通过双指针遍历，按序选择元素合并到临时数组，再回写原数组。
     

7.2 算法特性

• 时间复杂度：
  • 所有情况 O(N logN)
• 空间复杂度：
  • 递归栈：O(N) （需要额外临时数组存储合并结果）。
• 稳定性：稳定（合并时保留相等元素原始顺序）。

7.3 优化策略

1. 迭代法消除递归栈
   • 自底向上合并，避免递归调用栈开销
2. 小区间数组切换插入排序

7.4 代码实现

// 归并
// 比较 begin1 和 begin2 位置，小的尾插到tmp数组
void _MergeSort(int* a, int* tmp, int begin, int end)
{
	int mid = (begin + end) / 2;
	// [begin, mid] [mid+1,end]有序就可以进行归并了
	// [begin, mid-1] [mid,end]会导致死循环的问题
	_MergeSort(a, tmp, begin, mid - 1);
	_MergeSort(a, tmp, mid, end);

	// 归并
	int begin1 = begin, end1 = mid - 1;
	int begin2 = mid, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin] < 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++];
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail!\n");
		return;
	}

	_MergeSort(a, tmp, 0, n - 1);

	free(tmp);
	tmp = NULL;
}

// 非递归
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	// gap每组归并数据的数据个数
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			// [begin1, end1][begin2, end2]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);

			// 第二组都越界不存在，这一组就不需要归并
			if (begin2 >= n)
				break;

			// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并
			if (end2 >= n)
				end2 = n - 1;

			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
					tmp[j++] = a[begin1++];
				else
					tmp[j++] = a[begin2++];
			}

			while (begin1 <= end1)
				tmp[j++] = a[begin1++];

			while (begin2 <= end2)
				tmp[j++] = a[begin2++];
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		printf("\n");

		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}

8. 计数排序

计数排序是一种非比较型整数排序算法，通过统计元素频次确定其有序位置。
计数排序通过统计与映射实现高效排序，特别适合小范围整数数据。

8.1 基本原理

1. 确定范围：遍历原数组，找到最大值 max 和最小值 min，计算数据范围 $k=max-min+1$。
2. 统计频次：创建长度为 k 的计数数组 count，统计每个元素 x 出现的次数，存储于 $count[x-min]$。
3. 填充数组：将计数数组 count 中的元素填充到原数组中
   

8.2 算法特性

• 时间复杂度：
  • 平均、最好、最坏情况下均为O(N + k)，其中 n 为元素数量，k 为数据范围。
• 空间复杂度：
  • O(N + k)，用于存储结果数组和计数数组。
• 稳定性：
  • 稳定排序，逆向填充保证相同元素的原始顺序。

8.3 代码实现

// 只适合整数/适合范围集中
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];

		if (a[i] > max)
			max = a[i];
	}

	int range = max - min + 1;
	//printf("%d\n", range);

	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		perror("calloc fail");
		return;
	}

	// 统计次数
	for (int i = 0; i < n; i++)
		count[a[i] - min]++;

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

	free(count);
}