当前位置：首页 > news >正文

速成蓝桥杯之排序（二）

news 2026/5/7 4:35:45

一、冒泡排序（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; } }