一、冒泡排序（Bubble Sort）
核心思想：重复遍历待排序序列，依次比较相邻元素，若顺序错误则交换，使较大元素逐步 "冒泡" 至末尾。
- 时间复杂度：平均 / 最坏 O(n2)，最好 O(n)（优化后）
- 空间复杂度：O(1)
- 稳定性：稳定
解题步骤
- 从数组首元素开始，比较相邻两元素，前 > 后则交换。
- 每轮遍历确定当前最大元素位置，下一轮减少一次比较。
- 若某轮无交换，说明已有序，可提前结束。
蓝桥常考：基础排序实现、时间复杂度分析、稳定性判断。
二、选择排序（Selection Sort）
核心思想：每轮选未排序区最小（大）元素，放至已排序区末尾。
- 时间复杂度：平均 / 最坏 / 最好 O(n2)
- 空间复杂度：O(1)
- 稳定性：不稳定
解题步骤
- 设首元素为最小值，遍历后续找更小值并记录下标。
- 遍历结束，将最小值与未排序区首元素交换。
- 缩小未排序区间，重复至全部有序。
蓝桥常考：与冒泡 / 插入对比、交换次数、稳定性辨析。
三、插入排序（Insertion Sort）
核心思想：将未排序元素逐个插入已排序序列对应位置。
- 时间复杂度：平均 / 最坏 O(n2)，最好 O(n)（基本有序）
- 空间复杂度：O(1)
- 稳定性：稳定
解题步骤
- 首元素视为已排序，从第 2 个元素开始。
- 取当前元素，向前扫描已排序区，大于当前值则后移。
- 找到合适位置插入，直至全部处理。
蓝桥常考：近乎有序数据、小规模数据、作为高级排序优化（如快排、归并）。
四、归并排序（Merge Sort）
核心思想：分治法 —— 递归拆分至单元素，再两两合并有序序列。
- 时间复杂度：平均 / 最坏 / 最好 O(nlogn)
- 空间复杂度：O(n)
- 稳定性：稳定
解题步骤
- 分解：将数组二分，递归拆分至长度 1。
- 合并：双指针遍历两有序子数组，取小元素放入结果。
- 复制剩余：处理任一子数组剩余元素。
蓝桥常考：逆序对统计（高频）、外部排序、分治思想、大数据量稳定排序。
五、快速排序（Quick Sort）
核心思想：分治法 —— 选基准值，分区（小左大右），递归排序子区间。
- 时间复杂度：平均 O(nlogn)，最坏 O(n2)（已序 / 逆序）
- 空间复杂度：O(logn)（递归栈）
- 稳定性：不稳定
解题步骤
- 选基准：随机 / 三数取中选 pivot。
- 分区：遍历数组，小于 pivot 放左，大于放右。
- 递归：对左右子数组重复上述步骤。
蓝桥常考：手写快排、第 K 大 / 小数（Partition）、大数据量排序、复杂度优化。
六、堆排序（Heap Sort）
核心思想：利用完全二叉树的堆结构，建堆后反复取堆顶并调整。
- 时间复杂度：平均 / 最坏 / 最好 O(nlogn)
- 空间复杂度：O(1)
- 稳定性：不稳定
解题步骤
- 建堆：从最后非叶节点向前调整，构建最大 / 最小堆。
- 交换：堆顶与末尾元素交换，确定最大元素位置。
- 调整：堆大小减 1，重新调整堆，重复至有序。
蓝桥常考：TopK 问题、优先级队列、海量数据前 N 大、时间复杂度。
七、桶排序（Bucket Sort）
核心思想：按值范围分桶，桶内排序后合并。
- 时间复杂度：平均 O(n+k)，最坏 O(n2)
- 空间复杂度：O(n+k)
- 稳定性：稳定（桶内用稳定排序）
解题步骤
- 分桶：确定桶数与区间，映射元素至对应桶。
- 桶内排序：对非空桶用插入 / 快排等。
- 合并：按桶序输出所有元素。
蓝桥常考：均匀分布数据、浮点数排序、频率统计、空间换时间。
八、基数排序（Radix Sort）
核心思想：按低位到高位（或反向）逐位用稳定排序（如桶 / 计数）。
- 时间复杂度：O(d×(n+k))（d 为位数，k 为基数）
- 空间复杂度：O(n+k)
- 稳定性：稳定
解题步骤
- 取位：从最低位开始，取当前位数字。
- 分桶：按位值入对应桶（0~9）。
- 收集：按桶序收集，处理更高位，直至最高位。
蓝桥常考：整数 / 字符串排序、大数据量线性时间、位数相关问题。
九、常考题型汇总
- 基础实现：手写冒泡 / 选择 / 插入 / 快排 / 归并。
- 特性辨析：时间 / 空间复杂度、稳定性、适用场景对比。
- 经典应用
- 归并：逆序对（高频）、外部排序
- 快排：第 K 大 / 小、区间排序
- 堆：TopK、优先级队列
- 桶 / 基数：频率统计、大数据线性排序
- 综合题：排序 + 二分、贪心、DP、字符串处理。
十、近五年真题示例（2021–2025）
1. 2022 省赛 PythonB 组 - 数位排序
题目：给定 n 个数，按各位数字和升序，和相同按数值升序。解法：自定义排序键（数字和 + 原数），用快排 / 内置 sort。
2. 2023 国赛 PythonA 组 - 选段排序
题目：选区间排序，使 Aq−Ap 最大。解法：枚举区间 + 排序 + 求值，或预处理前缀最值优化。
3. 2024 省赛 C/C++B 组 - 小朋友排队
题目：相邻交换排序，求最小不高兴度总和。解法：归并排序求逆序对，累加每个元素逆序数。
4. 2025 省赛 C/JavaA 组 - 最短距离
题目：点集排序后求相邻距离和最小。解法：坐标排序后贪心计算。
5. 2021–2025 填空题高频
- 快排基准选择、分区次数
- 归并合并比较次数
- 堆排序调整次数
- 各算法复杂度、稳定性判断
十一、备考建议
- 基础：熟练手写冒泡、插入、选择。
- 重点：快排（Partition）、归并（逆序对）、堆排序（高频核心）。
- 技巧：大数据量优先用内置 sort；均匀分布用桶 / 基数。
- 真题：重点练逆序对、第 K 大、数位排序、区间排序等典型题。
