经典排序算法总结(包括快速排序，堆排序）

1. 直接插入排序

核心思路

将数组分为「已排序区」和「未排序区」，初始时已排序区只有第一个元素。依次取出未排序区的第一个元素，从已排序区末尾向前遍历，找到第一个小于等于该元素的位置，将其插入，直到所有元素排序完成。

代码实现

#include<stdio.h> #include<iostream> using namespace std; const int N = 105; int a[N]; int main() { int n; scanf("%d", &n); getchar(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); // 直接插入排序核心：将未排序元素插入到已排序区的正确位置 for (int i = 2; i <= n; i++) // 第一个元素默认已排序，从第二个开始 { int t = a[i]; // 保存当前待插入元素 int k; // 从已排序区末尾向前找插入位置 for (k = i - 1; k >= 1; k--) { if (a[k] > t) a[k + 1] = a[k]; // 比t大的元素后移 else break; // 找到第一个<=t的元素，停止 } a[k + 1] = t; // 插入到正确位置 } // 输出结果 for (int i = 1; i <= n; i++) printf("%d ", a[i]); return 0; }

特性总结

• 时间复杂度：最好O(n)（数组已有序）、平均O(n²)、最坏O(n²)
• 空间复杂度：O(1)（就地排序）
• 稳定性：稳定（相等元素相对位置不变）
• 初始序列相关性：有（越有序越快）

2. 冒泡排序（优化版）

核心思路

重复遍历数组，每次比较相邻两个元素，若顺序错误则交换，每轮将当前未排序区的最大元素「冒泡」到末尾。优化点：添加标志位，若某轮无交换，说明数组已有序，提前退出。

代码实现

#include<stdio.h> #include<iostream> using namespace std; const int N = 105; int a[N]; int main() { int n; scanf("%d", &n); getchar(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); // 优化版冒泡排序：添加标志位判断是否已有序 for (int i = 1; i <= n; i++) { bool swapped = false; // 标记本轮是否发生交换 for (int j = 1; j <= n - i; j++) // 每轮将最大元素"冒泡"到末尾 { if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = true; } } if (!swapped) break; // 本轮无交换，数组已有序，提前退出 } for (int i = 1; i <= n; i++) printf("%d ", a[i]); return 0; }

特性总结

• 时间复杂度：最好O(n)（优化后，数组已有序）、平均O(n²)、最坏O(n²)
• 空间复杂度：O(1)（就地排序）
• 稳定性：稳定
• 初始序列相关性：有

3. 简单选择排序

核心思路

将数组分为「已排序区」和「未排序区」，每轮从未排序区中选择最小的元素，与未排序区的第一个元素交换，放到已排序区的末尾，直到所有元素排序完成。

代码实现

#include<stdio.h> #include<iostream> using namespace std; const int N = 105; int a[N]; int main() { int n; scanf("%d", &n); getchar(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); // 简单选择排序核心：每轮选择未排序区的最小元素，放到已排序区末尾 for (int i = 1; i <= n; i++) { int min_idx = i; // 记录最小元素的下标 for (int j = i + 1; j <= n; j++) { if (a[j] < a[min_idx]) min_idx = j; } // 交换当前位置和最小元素的位置 int t = a[i]; a[i] = a[min_idx]; a[min_idx] = t; } for (int i = 1; i <= n; i++) printf("%d ", a[i]); return 0; }

特性总结

• 时间复杂度：最好O(n²)、平均O(n²)、最坏O(n²)（无论是否有序都需遍历）
• 空间复杂度：O(1)（就地排序）
• 稳定性：不稳定（反例：[3, 2, 2, 1]，交换后两个 2 的顺序改变）
• 初始序列相关性：无

4. 希尔排序（缩小增量排序）

核心思路

直接插入排序的改进版。将数组按「增量 d」分组（如 d=n/2, n/4,...1），对每组分别进行直接插入排序；逐渐缩小增量 d，当 d=1 时，整个数组成为一组，进行最后一次直接插入排序。

代码实现

#include<stdio.h> #include<iostream> using namespace std; const int N = 105; int a[N]; int main() { int n; scanf("%d", &n); getchar(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int round = 0; // 希尔排序核心：按增量分组，每组进行直接插入排序，逐渐缩小增量 for (int d = n / 2; d >= 1; d >>= 1) // 希尔原始增量序列：n/2, n/4, ..., 1 { // 对每个增量d，按步长d分组，每组执行直接插入排序 for (int i = d + 1; i <= n; i++) { int t = a[i]; int k; for (k = i - d; k >= 1; k -= d) { if (a[k] > t) a[k + d] = a[k]; else break; } a[k + d] = t; } // 输出每轮排序结果（保留调试输出） round++; printf("第%d轮排序结果：", round); for (int i = 1; i <= n; i++) printf("%d ", a[i]); printf("\n"); } printf("最终结果："); for (int i = 1; i <= n; i++) printf("%d ", a[i]); return 0; }

特性总结

• 时间复杂度：最好O(n)、平均O(n^1.3)、最坏O(n²)（依赖增量序列）
• 空间复杂度：O(1)（就地排序）
• 稳定性：不稳定（分组可能打乱相等元素的相对位置）
• 初始序列相关性：有

5. 快速排序

核心思路

分治思想。选择一个「基准元素」（如最右边元素），用双指针将数组划分为两部分：左边所有元素≤基准，右边所有元素≥基准；然后递归对左右两部分分别排序，直到区间只有一个元素。（我这里用的挖坑法，选基准数后，基准数所在的地方就会变成一个坑，用左边/右边的数字取填这个坑，填完后，那个数字的位置又会变成新坑，最后把基准填回最后一个坑，完成划分）

如果要按中间数作为基准数，在开头加上int mid = (l + r) / 2;swap(a[mid], a[r]);就行。

代码实现

#include<stdio.h> #include<iostream> using namespace std; const int N = 105; int a[N]; // 快速排序核心：分治思想，选择基准划分左右区间 void quick_sort(int l, int r) { if (l >= r) return; // 区间只有一个元素或为空，递归终止 int i = l, j = r; int pivot = a[j]; // 选择最右边元素作为基准 // 双指针划分区间 while (i < j) { // 左指针找比基准大的元素 while (i < j && a[i] <= pivot) i++; if (i < j) { a[j] = a[i]; j--; } // 右指针找比基准小的元素 while (i < j && a[j] >= pivot) j--; if (i < j) { a[i] = a[j]; i++; } } a[i] = pivot; // 将基准放到最终正确位置 // 递归排序左右子区间 quick_sort(l, i - 1); quick_sort(i + 1, r); } int main() { int n; scanf("%d", &n); getchar(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); quick_sort(1, n); for (int i = 1; i <= n; i++) printf("%d ", a[i]); return 0; }

特性总结

• 时间复杂度：最好O(nlogn)、平均O(nlogn)、最坏O(n²)（数组已排序且选首尾为基准时退化）
• 空间复杂度：O(logn)（递归栈深度，最坏 O (n)）
• 稳定性：不稳定（基准交换可能打乱相等元素顺序）
• 初始序列相关性：有

6. 堆排序（大根堆版，输出升序）

核心思路

利用「大根堆」（父节点≥子节点）排序。先将数组构建为大根堆，然后每次将堆顶（最大元素）与当前堆的末尾元素交换，将堆大小减 1，再调整堆顶使其重新满足大根堆性质，重复直到堆为空。

• 大根堆定义：一棵完全二叉树，父节点的值 ≥ 左右孩子的值
• 数组映射（下标从 1 开始，和你代码一致）：
  • 节点i的左孩子：2*i
  • 节点i的右孩子：2*i + 1
  • 节点i的父节点：i/2
• 完全二叉树性质：最后一个非叶子节点是n/2（n 是数组长度）

整个流程：先进行建堆，把整个无序的数组变成合法的大根堆，也就是 for (int i = n / 2; i >= 1; i--) 的循环，然后进入排序阶段，每次把堆顶（最大元素）拿走后，只有堆顶位置不合法，下面的子树还是好的，所以只需要调整堆顶（i=1）就行。因为我们的目的是升序输出数组，所以最大的值要放到最后面去。实际代码需要根据不同场景调整。

代码实现

#include<stdio.h> #include<iostream> using namespace std; const int N = 105; // a[]：堆数组；i：当前要调整的根节点；n：当前堆的大小 void DownAdjust(int a[], int i, int n) { int now = i; // now：当前正在检查的节点（从根i开始） int next; // next：now的孩子节点 int tmp; // 临时变量，用于交换 // 循环条件：now有左孩子（完全二叉树中，有左孩子才可能需要调整） while (now * 2 <= n) { next = now * 2; // 先假设左孩子是较大的那个 // 1. 选左右孩子中【较大】的那个 // 如果有右孩子，且右孩子比左孩子大 → next指向右孩子 if (next + 1 <= n && a[next + 1] > a[next]) next++; // 2. 比较父节点（now）和较大的孩子（next） if (a[now] < a[next]) { // 父节点 < 孩子 → 不满足大根堆，交换它们 tmp = a[next]; a[next] = a[now]; a[now] = tmp; now = next; // 交换后，now移到孩子位置，继续向下检查 // （因为交换可能破坏了下面子树的大根堆性质） } else { break; // 父节点 ≥ 孩子 → 已经满足大根堆，直接停止 } } } int main() { int a[N]; int n; scanf("%d", &n); getchar(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); // 高效建堆：从最后一个非叶子节点开始向下调整，时间复杂度O(n) for (int i = n / 2; i >= 1; i--) DownAdjust(a, i, n); int size = n; // size：当前堆的大小（初始是整个数组） // 堆排序核心：每次将堆顶（最大元素）与末尾元素交换，再调整堆 for (int i = 1; i <= n; i++) { // 1. 交换堆顶（a[1]，最大元素）和当前堆的最后一个元素（a[size]） int t = a[1]; a[1] = a[size]; a[size] = t; size--; // 2. 堆大小减1（刚才交换到末尾的元素已经排好序，不再参与堆调整） DownAdjust(a, 1, size); // 3. 重新调整堆顶，把剩下的元素变回大根堆 } for (int i = 1; i <= n; i++) printf("%d ", a[i]); return 0; }

特性总结

• 时间复杂度：最好O(nlogn)、平均O(nlogn)、最坏O(nlogn)（稳定的 O (nlogn)）
• 空间复杂度：O(1)（就地排序）
• 稳定性：不稳定（堆顶交换可能打乱相等元素顺序）
• 初始序列相关性：无

为什么从n/2开始？

• 完全二叉树中，n/2之后的节点都是叶子节点（没有孩子），叶子本身就是一个合法的堆，不需要调整
• 从最后一个非叶子节点（n/2）开始，从下往上、从右往左依次调整每个父节点
• 这样能保证：调整某个父节点时，它的左右子树已经是大根堆了（符合DownAdjust的前提）

举个完整建堆例子

数组：[3, 1, 4, 2]（n=4）

1. n/2=2→ 从 i=2 开始调整
   • i=2：子树是[1,2]→ 调整后变成[2,1]，数组变为[3,2,4,1]
2. i=1：调整根节点
   • 子树是[3,2,4]→ 选较大孩子 4（右孩子），交换 3 和 4 → 数组变为[4,2,3,1]✅ 建堆完成！现在是大根堆：[4,2,3,1]

核心逻辑（为什么大根堆能排升序？）

1. 大根堆的堆顶（a [1]）是当前堆的最大元素
2. 把最大元素和堆的末尾元素交换 → 最大元素就放到了数组的最后（属于「已排序区」）
3. 堆大小size--，剩下的元素（1~size）重新调整成大根堆
4. 重复这个过程，每次把当前最大的元素放到「已排序区」的前面 → 最终数组是升序

7. 二路归并排序

核心思路

分治思想。将数组递归地分成两半，分别对两半排序；然后用双指针将两个有序子数组合并成一个有序数组（合并时相等元素先取左半部分，保证稳定性）。

代码实现

#include<stdio.h> #include<iostream> using namespace std; const int N = 105; // 归并排序核心：分治+合并 void Merge_sort(int a[], int l, int r) { if (l >= r) return; // 递归终止条件 int mid = l + r >> 1; // 划分中点 // 递归排序左右子数组 Merge_sort(a, l, mid); Merge_sort(a, mid + 1, r); // 合并两个有序子数组 int t[N]; // 临时数组存储合并结果 int k = 0; int i = l, j = mid + 1; // 同时遍历两个子数组，取较小的放入临时数组 while (i <= mid && j <= r) { if (a[i] <= a[j]) // <=保证稳定性 { t[k++] = a[i]; i++; } else { t[k++] = a[j]; j++; } } // 处理剩余元素 while (i <= mid) t[k++] = a[i++]; while (j <= r) t[k++] = a[j++]; // 将临时数组结果复制回原数组 for (int u = 0; u < k; u++) a[l + u] = t[u]; } int main() { int a[N]; int n; scanf("%d", &n); getchar(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); Merge_sort(a, 1, n); for (int i = 1; i <= n; i++) printf("%d ", a[i]); return 0; }

特性总结

• 时间复杂度：最好O(nlogn)、平均O(nlogn)、最坏O(nlogn)（与初始序列无关）
• 空间复杂度：O(n)（非就地排序，需临时数组）
• 稳定性：稳定
• 初始序列相关性：无

8. 计数排序

核心思路

非比较排序。利用数组元素的值作为索引，统计每个值出现的次数；通过计算前缀和确定每个元素在排序后数组中的最终位置；逆序遍历原数组，将元素放入临时数组，保证稳定性。

代码实现

#include<stdio.h> #include<iostream> #include<cstring> using namespace std; const int N = 105; const int MAX_VALUE = 1000; // 根据数据范围调整 int main() { int a[N]; int cnt[MAX_VALUE + 1] = {0}; // 计数数组 int sumcnt[MAX_VALUE + 1] = {0}; // 前缀和数组 int t[N]; // 临时数组存储结果 int n; int maxn = 0; scanf("%d", &n); getchar(); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); cnt[a[i]]++; // 统计每个元素出现次数 if (a[i] > maxn) maxn = a[i]; // 记录最大值 } // 计算前缀和，确定每个元素的最后位置 sumcnt[0] = cnt[0]; for (int i = 1; i <= maxn; i++) sumcnt[i] = sumcnt[i - 1] + cnt[i]; // 逆序遍历原数组，保证排序的稳定性 for (int i = n; i >= 1; i--) { int pos = sumcnt[a[i]]; t[pos] = a[i]; sumcnt[a[i]]--; } // 输出结果 for (int i = 1; i <= n; i++) printf("%d ", t[i]); return 0; }

特性总结

• 时间复杂度：O(n+k)（k 为元素最大值）
• 空间复杂度：O(n+k)（非就地排序）
• 稳定性：稳定
• 初始序列相关性：无
• 适用场景：只能排序整数，且元素取值范围不能太大

9. 基数排序（基于计数排序）

核心思路

非比较排序。按数字的「每一位」排序（从个位到十位、百位...），每一位用稳定的计数排序处理；最终通过多轮排序得到有序数组。

代码实现

#include<stdio.h> #include<iostream> #include<cstring> using namespace std; const int N = 105; // 获取数字num的第d位（d=1:个位, d=10:十位, d=100:百位...） int getDigit(int num, int d) { return (num / d) % 10; } // 获取数组中最大数的位数 int getMaxBit(int a[], int n) { int maxn = 0; for (int i = 1; i <= n; i++) { if (a[i] > maxn) maxn = a[i]; } int bits = 0; while (maxn > 0) { bits++; maxn /= 10; } return bits == 0 ? 1 : bits; // 处理全0数组 } // 针对第d位的稳定计数排序 void countSortByDigit(int a[], int n, int d) { int cnt[10] = {0}; // 每一位只有0-9，计数数组大小为10 int sumcnt[10] = {0}; int t[N] = {0}; // 统计当前位数字出现次数 for (int i = 1; i <= n; i++) { int digit = getDigit(a[i], d); cnt[digit]++; } // 计算前缀和 sumcnt[0] = cnt[0]; for (int i = 1; i < 10; i++) { sumcnt[i] = sumcnt[i - 1] + cnt[i]; } // 逆序遍历保证稳定性 for (int i = n; i >= 1; i--) { int digit = getDigit(a[i], d); int pos = sumcnt[digit]; t[pos] = a[i]; sumcnt[digit]--; } // 复制回原数组 for (int i = 1; i <= n; i++) { a[i] = t[i]; } } int main() { int a[N]; int n; scanf("%d", &n); getchar(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); // 基数排序核心：从低位到高位依次排序 int maxBit = getMaxBit(a, n); int d = 1; for (int i = 1; i <= maxBit; i++) { countSortByDigit(a, n, d); d *= 10; } for (int i = 1; i <= n; i++) printf("%d ", a[i]); return 0; }

特性总结

• 时间复杂度：O(d(n+r))（d 为最大数的位数，r 为基数 10）
• 空间复杂度：O(n+r)（非就地排序）
• 稳定性：稳定
• 初始序列相关性：无
• 适用场景：适合排序整数或字符串，尤其适合元素取值范围大但位数少的情况

经典例题

可以用快速排序变种，快速选择，只选择有目标的那一部分，平均时间复杂度O(n)，最坏O(n^2)，空间复杂度O(logn)。也可以用小根堆实现，但时间复杂度为O(nlogn）故不再赘述。

class Solution { int quick(vector<int>&a,int l,int r,int k) { if(l>=r) return a[l];//只剩一个元素直接返回 int mid=(l+r)/2; swap(a[mid],a[r]);//选中间的数当作基准数 int i=l,j=r; int pivot=a[j]; while(i<j) { while(i<j&&a[i]>=pivot) i++; if(i<j) { a[j]=a[i]; j--; } while(i<j&&a[j]<=pivot) j--; if(i<j) { a[i]=a[j]; i++; } } a[i]=pivot; //只递归目标所在的一侧 int pos=i; int left_cnt=pos-l+1;//检查左边有多少个数字 if(left_cnt==k) {//就是要找的 return a[pos]; } if(k<left_cnt) return quick(a,l,pos-1,k);//目标在左边 else return quick(a,pos+1,r,k-left_cnt);//目标在左边，k减去左边数量 } public: int findKthLargest(vector<int>& nums, int k) { return quick(nums,0,nums.size()-1,k); } };