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

引言

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

---

一、选择排序（Selection Sort）

1.1 核心思想

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

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

1.2 动态示意图

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

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

1.3 代码实现

代码语言：javascript代码运行次数：0运行复制

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）

堆排序在学习堆的时候学习过哦(´▽ʃ♡ƪ) 欢迎学习