【初探数据结构】详解三大经典排序算法（选择/堆/冒泡）

引言

排序算法是数据结构的核心基础。本文通过选择排序、堆排序、冒泡排序的对比解析，帮助初学者掌握算法思想与实现细节。文末附算法对比总结表。

一、选择排序（Selection Sort）

1.1 核心思想

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

这里我们在序列两头同时进行选择排序，可以一定程度上提高选择排序的性能。

1.2 动态示意图

[示例数组：7, 3, 5, 1]

• 第1轮：找到最小值1 ↔ 与7交换 → [1, 3, 5, 7]
• 第2轮：在剩余部分找最小3（已在正确位置）
• 第3轮：找最小5 ↔ 无需交换
• 排序完成

1.3 代码实现

void SelectSort(int* a, int n)
{
	//定义左右指针
	int left = 0;
	int right = n - 1;
	//当左右指针相遇，排序完成
	while (left < right)
	{
		int max = left, min = left;
		//遍历选出最大最小数
		for (int i = left+1; i <= right; i++) {
			if (a[max] > a[i]) {
				max = i;
			}
			if (a[min] < a[i]) {
				min = i;
			}
		}
		swap(&a[left], &a[min]);
		if (left == max)
			max = min;
		swap(&a[right], &a[max]);
		left++;
		right--;
	}
}

1.4 关键特性

• 时间复杂度：O(n²)（双重循环）
• 空间复杂度：O(1)（原地排序）
• 不稳定性：交换可能破坏相等元素顺序（如 [5, 5, 2]）

二、堆排序（Heap Sort）

堆排序在学习堆的时候学习过哦(´▽ʃ♡ƪ) 欢迎学习 🚀传送门：【初探数据结构】堆的应用实例（堆排序与TopK问题）

三、冒泡排序（Bubble Sort）

相信大家堆冒泡已经耳熟能详了吧，那么你是否能手撕呢？这也是检验你C语言代码功底的试金石哦😉

3.1 核心思想

“相邻比武，大的沉底” 通过相邻元素比较交换，使较大元素逐渐移动到末尾。

3.2 优化技巧

• 提前终止：若某轮未发生交换，说明已有序
• 记录最后交换位置：减少后续比较范围

3.3 动态示例

初始数组：[6, 3, 8, 2]

• 第1轮：3↔6, 6↔8 → [3, 6, 2, 8]
• 第2轮：2↔6 → [3, 2, 6, 8]
• 第3轮：2↔3 → [2, 3, 6, 8]

3.4 代码实现（带优化）

// 冒泡排序
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		bool exchange = false;
		for (int i = 0; i < n - 1 - j; i++)
		{
			if (a[i] > a[i + 1]) {
				swap(&a[i], &a[i + 1]);
				exchange = true;
			}
		}
		if (exchange == false) {
			break;
		}
	}
}

3.5 关键特性

• 时间复杂度：最佳O(n)（已排序），最差O(n²)
• 稳定性：稳定（相等元素不交换）
• 教学意义：直观体现排序过程，适合入门教学

3.6 扩展学习

🚀传送门：高阶C语言|库函数qsort的使用以及用冒泡排序实现qsort的功能详解

四、对比总结表