速成蓝桥杯之排序（二）
一、冒泡排序（Bubble Sort）
核心思想
两两比较，大的往后 “冒”，每轮确定一个最大值。
解题步骤
- 外层循环控制轮数
- 内层循环比较相邻元素
- 逆序则交换
- 可加 flag 优化：某轮无交换直接结束
C++ 模板
void bubbleSort(int a[], int n) { for (int i = 0; i < n; i++) { bool flag = false; for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); flag = true; } } if (!flag) break; } }复杂度
- 时间：最好 O (n)，最坏 / 平均 O (n²)
- 空间：O (1)
- 稳定
常考
- 基础填空、复杂度、稳定性
- 手动模拟排序过程
二、选择排序（Selection Sort）
核心思想
每轮选最小，放到已排序区末尾。
解题步骤
- 找未排序区最小值下标
- 和未排序区第一个交换
- 缩小未排序区间
C++ 模板
void selectionSort(int a[], int n) { for (int i = 0; i < n; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[minIdx]) minIdx = j; } swap(a[i], a[minIdx]); } }复杂度
- O (n²) 无论好坏
- 不稳定
常考
交换次数、与冒泡 / 插入对比
三、插入排序（Insertion Sort）
核心思想
像打牌一样，逐个插入到前面有序区。
解题步骤
- 从第 2 个数开始
- 向前比较，大的后移
- 找到位置插入
C++ 模板
void insertionSort(int a[], int n) { for (int i = 1; i < n; i++) { int x = a[i]; int j = i - 1; while (j >= 0 && a[j] > x) { a[j + 1] = a[j]; j--; } a[j + 1] = x; } }复杂度
- 最好 O (n)，最坏 O (n²)
- 稳定
常考
近乎有序数组效率高、快排 / 归并小规模优化
四、归并排序（Merge Sort）⭐⭐⭐⭐⭐（蓝桥必考）
核心思想
分治：拆分成单元素，再合并两个有序数组。
解题步骤
- 二分递归拆
- 合并两个有序数组
- 用临时数组存结果
C++ 模板
int tmp[100010]; void merge(int a[], int l, int mid, int r) { int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (a[i] <= a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (int p = l; p <= r; p++) a[p] = tmp[p]; } void mergeSort(int a[], int l, int r) { if (l >= r) return; int mid = (l + r) / 2; mergeSort(a, l, mid); mergeSort(a, mid + 1, r); merge(a, l, mid, r); }复杂度
- O(n log n)
- 稳定
常考（超级高频）
- 逆序对统计
- 外部排序
- 分治思想题
五、快速排序（Quick Sort）⭐⭐⭐⭐⭐
核心思想
选基准 pivot，小左大右，递归两边。
解题步骤
- 选基准
- partition 分区
- 递归左右
C++ 模板
void quickSort(int a[], int l, int r) { if (l >= r) return; int i = l, j = r; int pivot = a[l]; while (i < j) { while (i < j && a[j] >= pivot) j--; a[i] = a[j]; while (i < j && a[i] <= pivot) i++; a[j] = a[i]; } a[i] = pivot; quickSort(a, l, i - 1); quickSort(a, i + 1, r); }复杂度
- 平均 O (n log n)，最坏 O (n²)
- 不稳定
常考
- 第 K 大 / 小数
- partition 过程
- 手写快排
六、堆排序（Heap Sort）⭐⭐⭐⭐
核心思想
建大顶堆，每次取堆顶放末尾，再调整堆。
解题步骤
- 建堆
- 交换堆顶与末尾
- 调整堆
C++ 模板
void down(int a[], int u, int n) { int t = u; if (u * 2 <= n && a[u * 2] > a[t]) t = u * 2; if (u * 2 + 1 <= n && a[u * 2 + 1] > a[t]) t = u * 2 + 1; if (t != u) { swap(a[u], a[t]); down(a, t, n); } } void heapSort(int a[], int n) { for (int i = n / 2; i >= 1; i--) down(a, i, n); for (int i = n; i > 1; i--) { swap(a[1], a[i]); down(a, 1, i - 1); } }复杂度
- O(n log n)
- 不稳定
常考
- TopK
- 优先队列
- 堆调整次数
七、桶排序（Bucket Sort）
核心思想
按范围分桶，桶内排序再合并。
C++ 模板（简易版）
const int MAX = 100010; int bucket[MAX]; void bucketSort(int a[], int n) { memset(bucket, 0, sizeof bucket); for (int i = 0; i < n; i++) bucket[a[i]]++; int idx = 0; for (int i = 0; i < MAX; i++) { while (bucket[i]--) a[idx++] = i; } }复杂度
- O(n + k)
- 稳定
常考
范围集中、频率统计
八、基数排序（Radix Sort）
核心思想
按个位、十位、百位… 逐位桶排。
解题步骤
- 取每一位
- 按位入桶
- 收集
常考
大数排序、字符串排序、不比较排序
九、计数排序
本质简化桶排，适合范围小整数。模板同桶排。
十、近五年蓝桥杯排序真题高频考点（2020–2025）
- 归并求逆序对（几乎每年都有）
- 小朋友排队
- 翻转对
- 快排 partition
- 第 K 大数
- 找中位数
- 堆排序 / 优先队列
- 最大 / 最小 K 个数
- 自定义排序
- 数位和排序
- 字符串字典序
- 复杂度与稳定性填空
- 区间排序、贪心 + 排序
- 活动选择、区间覆盖
- 二分 + 排序
- 最接近值、第几个数