所有排序算法时间复杂度总结
| 排序类别 | 算法 | 最好时间 | 最坏时间 | 平均时间 | 稳定性 | 特点 |
|---|---|---|---|---|---|---|
| 🔁 交换排序 | 冒泡排序 | O(n) | O(n²) | O(n²) | ✅ 稳定 | 优化后对已有序序列可提前终止 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | ❌ 不稳定 | 最坏情况发生在pivot选择不佳 | |
| 📥 插入排序 | 直接插入排序 | O(n) | O(n²) | O(n²) | ✅ 稳定 | ❌ |
| 📤 选择排序 | 简单选择排序 | O(n²) | O(n²) | O(n²) | ❌ 不稳定 | ❌ |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | ❌ 不稳定 | 适合大数据量，原地排序 | |
| 🔀 归并排序 | 归并排序 | O(n log n) | O(n log n) | O(n log n) | ✅ 稳定 | 外部排序首选，需额外空间 |
归并排序的空间复杂度是 O(n)，快速排序空间复杂度是 O(log n)，其余空间复杂度均为 O(1)
归并排序的空间复杂度是 O(n)
归并排序在“合并两个有序子数组”时，需要使用一个 临时数组（temp） 来保存合并结果；
每一层递归，都需要分配新的数组空间 来合并；
最坏情况就是一次性需要和原数组等长的 temp 数组；
所以总体空间复杂度是：O(n)。
快速排序空间复杂度是 O(log n)来自于递归栈调用
每一层只处理一半数组，递归深度就是 log n
每次递归会占用一次函数调用栈空间（函数、参数、局部变量）
所以空间复杂度 = 递归栈深度 = O(log n)（在平均情况下）
如果你在开发中如何选择排序算法？
| 需求场景 | 推荐算法 |
|---|---|
| 小规模 + 要求稳定 | 插入排序 / 冒泡排序 |
| 中等规模 + 快速 + 可接受不稳定 | 快速排序 |
| 大数据 + 稳定性 + 并行性强 | 归并排序 |
| 内存有限 + 追求原地排序 | 堆排序 |
| Top-K 问题 | 堆排序（小顶堆） |
| 链表排序 | 归并排序（特别适配） |
为什么归并排序适合链表？
✅ 1. 不需要随机访问
链表不能像数组那样通过下标
arr[i]随便访问；快排需要频繁地根据下标去访问和交换数据；
归并排序只需要：从头遍历、断链、合并，这对链表来说非常友好！
✅ 2. 拆分链表很容易
拆分链表可以用快慢指针法（slow/fast）找到中点，一断开就是两个子链表；
不需要额外空间，不需要复制数据。
✅ 3. 合并两个有序链表超级高效
合并链表只需要比较当前节点值，然后拼接指针即可；
不需要额外的数组或复制内容；
不涉及移动元素，纯粹操作指针，O(1) 的插入效率！
一、交换排序
1.1 冒泡排序
void bubbleSort(int[] arr) {
boolean swapped;
for (int i = 0; i < arr.length - 1; i++) {
swapped = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换相邻元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true; // 有交换发生
}
}
// 如果本轮遍历中没有发生任何交换，说明已经有序，可以直接退出
if (!swapped) break;
}
}
分析时间复杂度：
| 情况 | 内层是否完整执行 | 时间复杂度 |
|---|---|---|
| 最好情况（已排序） | 只执行一次内层循环，无交换直接退出 | O(n) |
| 最坏情况（完全逆序） | 每次都发生交换，执行 n-1 次完整循环 | O(n^2) |
| 平均情况 | 一般需要多轮交换和比较 | O(n^2) |
1.2 快速排序
方法一：双指针交换法（常用）（Hoare 分区法改进版）
基准元素可以随机选取
核心思想
基准位置不固定，左右指针从两端向中间扫描，直接交换不符合条件的元素，最终通过相遇点分割数组。
基准元素不参与交换，仅在递归时分割左右子数组。
步骤
选择基准：任意位置（如中间、最左、最右元素均可）。
初始化指针：左指针
left从最左开始，右指针right从最右开始。移动与交换：
左指针向右，找到第一个 大于等于 基准的元素。
右指针向左，找到第一个 小于等于 基准的元素。
交换左右指针的值，继续移动，直到
left > right。
分割数组：以右指针位置为分界点（
right），递归处理左右子数组。基准位置：基准元素不固定在某处，分界点由指针相遇位置决定。
代码示例
public void yes(int[] a,int left,int right){
//递归需要终止条件，只有一个元素也不需要排序，所以是等号
if(left>=right){
return;
}
int target= a[left];
int l=left;
int r=right;
while(l<r){
while(l<r&&a[l]<=target){
l++;
}
while(l<r&&a[r]>=target){
r--;
}
if(l<r){
int temp=a[l];
a[l]=a[r];
a[r]=temp;
}
}
// 把 pivot 放在何处会对下面的参数产生影响
a[left] = a[l];
a[l] = target;
yes(a,left,l-1);
yes(a,l+1,right);
}- 最终l和r一定相遇到同一点，所以a[l]或a[r]最终都可以作为基准元素的放置位置
- 就需要先将a[l]位置的元素放置到我们定义的基准元素最初的位置（上面代码中是left）然后再将基准元素的值target赋值到a[l]的位置。
- 最终递归进行基准元素l前面的部分和后面的部分。
时间复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n log n) | 每次都平均划分数组（左右均等） |
| 平均情况 | O(n log n) | 随机输入数据 |
| 最坏情况 | O(n²) | 每次划分极度不平衡（如数组有序，且总选最左为 pivot） |
方法二：基准跟随法（不常用）（填坑法/基准锚定法）
基准元素只能为最右或最左
核心思想
基准元素位置动态变化，始终有一个指针指向当前“坑位”（基准的临时位置）。
交换时切换基准指针，最终将基准填入相遇点。
步骤
选择基准：固定选择一端（如最左元素
arr[low]）。初始化指针：
左指针
left指向基准初始位置（坑位）。右指针
right从最右开始。
移动与填坑：
右指针先向左，找到第一个 小于 基准的元素，将其填入左坑位，此时右指针位置成为新坑位。
左指针向右，找到第一个 大于 基准的元素，将其填入右坑位，此时左指针位置成为新坑位。
重复直到
left == right，将基准值填入最终坑位。
分割数组：以最终坑位为分界点，递归处理左右子数组。
代码示例
public class QuickSortPivotPointer {
public static void quickSort(int[] a, int left, int right) {
if (left >= right) return;
int l = left;
int r = right;
int pivot = a[l]; // 保存基准值
while (l < r) {
// 右指针先走，找比 pivot 小的
while (l < r && a[r] >= pivot) r--;
if (l < r) {
a[l] = a[r]; // 覆盖左边，右边现在成了“坑”
l++;
}
// 左指针走，找比 pivot 大的
while (l < r && a[l] <= pivot) l++;
if (l < r) {
a[r] = a[l]; // 覆盖右边，左边成了“坑”
r--;
}
}
// 相遇时，填入 pivot
a[l] = pivot;
// 递归处理左右部分
quickSort(a, left, l - 1);
quickSort(a, l + 1, right);
}
}
二、归并排序
归并排序的原理
并排序的核心步骤：
分解（Divide）：将数组递归地分成两半，直到每个子数组只剩一个元素（天然有序）。
合并（Merge）：将两个已排序的子数组合并成一个有序数组。
示例（升序排序）：
原始数组：[38, 27, 43, 3, 9, 82, 10]
分解过程：
[38, 27, 43, 3] | [9, 82, 10]
[38, 27] | [43, 3] | [9, 82] | [10]
[38] | [27] | [43] | [3] | [9] | [82] | [10] （每个子数组只剩一个元素）
合并过程：
[27, 38] | [3, 43] | [9, 82] | [10]
[3, 27, 38, 43] | [9, 10, 82]
[3, 9, 10, 27, 38, 43, 82] （最终有序）关键来了：合并两个有序数组，怎么做？
我们以
[3,5,8]和[1,2,9]为例进行合并：初始化指针：
i = 0指向左边数组[3,5,8]
j = 0指向右边数组[1,2,9]用
temp[]临时数组存结果逐步比较并放入 temp：
1. 比较 3 和 1 => 小的是 1，放入 temp 2. 比较 3 和 2 => 小的是 2，放入 temp 3. 比较 3 和 9 => 小的是 3，放入 temp 4. 比较 5 和 9 => 小的是 5，放入 temp 5. 比较 8 和 9 => 小的是 8，放入 temp 6. 剩下 9，放入 temp
时间复杂度（每一步解释）：
每一层拆分是 O(log n) 层；
每一层合并要扫描整个数组 O(n)；
所以总时间复杂度：O(n log n)
空间复杂度：
需要一个临时数组辅助合并：O(n)
稳定性：
稳定排序：不会交换相同值的相对顺序。
public class MergeSort {
public void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // 防止溢出
mergeSort(arr, left, mid); // 递归左半部分
mergeSort(arr, mid + 1, right); // 递归右半部分
merge(arr, left, mid, right); // 合并
}
}
private void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1]; // 临时数组
int i = left, j = mid + 1, k = 0;
// 合并两个有序数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 处理剩余元素
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
// 拷贝回原数组
System.arraycopy(temp, 0, arr, left, temp.length);
}
}
三、选择排序
3.1 直接选择
基本步骤：
每轮从剩下的元素中选出最小值。
把这个最小值和当前起始位置的元素交换。
void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换最小值和当前位置
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
时间复杂度分析：
| 情况 | 比较次数 | 交换次数 | 时间复杂度 |
|---|---|---|---|
| 最好情况（已排好序） | 一样要全比较 | 最多 n 次交换 | O(n^2) |
| 最坏情况（完全逆序） | 同上 | 同上 | O(n^2) |
| 平均情况 | O(n^2) |
🔴 最好情况下仍是 O(n^2)：
因为选择排序无论是否有序，都要扫描剩下所有元素找最小值，比较次数不变。
它不依赖初始顺序，所以无所谓最好或最坏情况，始终是
O(n^2)。
3.2 堆排序
堆排序是什么？
堆排序是一种 基于“堆”这种数据结构实现的选择排序算法，它通过构建一个最大堆（或最小堆），再一个个地“取出堆顶最大值”，放到数组末尾，最终得到一个有序数组。
堆排序适合的场景
大量数据中找 Top K（优先队列思想）
对数据空间敏感（堆排序是原地排序）
不要求稳定排序
什么是“堆”？
二叉堆 是一种 完全二叉树，满足：
最大堆（Max-Heap）：父节点 ≥ 子节点（堆顶是最大值）。
最小堆（Min-Heap）：父节点 ≤ 子节点（堆顶是最小值）。
堆的存储：通常用 数组 存储，索引关系：
父节点
i的左子节点：2i + 1父节点
i的右子节点：2i + 2子节点
i的父节点：(i - 1) / 2
🧠 三、堆排序的核心流程
✅ 步骤如下：
建堆（建最大堆）：
把原数组转换成最大堆。
排序：
每次把堆顶元素（最大值）交换到数组末尾；
然后把剩下的部分重新调整成最大堆；
一直到只剩一个元素为止。
import java.util.Arrays;
public class HeapSort {
// 主函数：进行堆排序
public static void heapSort(int[] arr) {
int n = arr.length;
// 第一步：构建最大堆（从最后一个非叶子节点开始调整）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 第二步：从堆中逐个取出最大元素
for (int i = n - 1; i > 0; i--) {
// 把最大值（堆顶）放到数组末尾
swap(arr, 0, i);
// 重新对前 i 个元素调整成最大堆
heapify(arr, i, 0);
}
}
// 调整以 i 为根节点的子树，使其满足最大堆性质
private static void heapify(int[] arr, int heapSize, int i) {
int largest = i; // 假设当前最大值是根节点
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点比当前最大值还大
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点比当前最大值还大
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点，则交换，并继续向下调整
if (largest != i) {
swap(arr, i, largest);
heapify(arr, heapSize, largest);
}
}
// 辅助函数：交换数组中两个元素
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 测试
public static void main(String[] args) {
int[] arr = {4, 10, 3, 5, 1};
heapSort(arr);
System.out.println(Arrays.toString(arr)); // 输出: [1, 3, 4, 5, 10]
}
}四、插入排序
基本步骤：
从第二个元素开始，向前“扫描”。
如果当前元素小于前面的元素，就不断向前比较并将前面元素后移，直到找到一个合适的位置插入。
void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int current = arr[i];
int j = i - 1;
// 把比 current 大的元素都往后移
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
// 插入到正确位置
arr[j + 1] = current;
}
}
时间复杂度分析：
| 情况 | 比较次数 | 移动次数 | 时间复杂度 |
|---|---|---|---|
| 最好情况（已排好序） | 每次只比较一次 | 0 次移动 | O(n) |
| 最坏情况（完全逆序） | 1+2+...+(n−1)=O(n2)1 + 2 + ... + (n-1) = O(n^2)1+2+...+(n−1)=O(n2) | 同上 | O(n^2) |
| 平均情况 | 约 O(n2)O(n^2)O(n2) | O(n^2) |
🟢 最好情况说明：
当数组已经是升序排列时，每次
arr[j] > current判断都不成立，直接插入，无需移动。所以只做一次比较，没有移动，总复杂度
O(n)。