手撕十大排序算法
·
1. 冒泡排序（Bubble Sort）
核心思路
重复遍历数组，每次轮比较相邻元素，若顺序错误则交换，直到无交换发生（数组有序）。大元素会像气泡一样 "浮" 到数组尾部。
示例（排序 [3, 1, 4, 2]）
- 第 1 轮：比较 (3,1)→交换→[1,3,4,2]；比较 (3,4)→不换；比较 (4,2)→交换→[1,3,2,4]（4 已到位）
- 第 2 轮：比较 (1,3)→不换；比较 (3,2)→交换→[1,2,3,4]（3 已到位）
- 第 3 轮：无交换，提前结束
复杂度
- 时间复杂度：
- 最坏 / 平均：O (n²)（完全逆序）
- 最好：O (n)（已排序，加
swapped优化）
- 空间复杂度：O (1)（仅用临时变量）
代码
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false; // 优化：标记是否交换
// 每轮结束后，最后i个元素已排序
for (int j = 0; j < n - 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; // 无交换则数组有序，直接退出
}
}
2. 选择排序（Selection Sort）
核心思路
每轮从未排序部分找到最小（或最大）元素，与未排序部分的第一个元素交换，逐步将数组分为 "已排序" 和 "未排序" 两部分。
示例（排序 [3, 1, 4, 2]）
- 第 1 轮：未排序部分
[3,1,4,2]，最小元素 1，与 3 交换→[1,3,4,2] - 第 2 轮：未排序部分
[3,4,2]，最小元素 2，与 3 交换→[1,2,4,3] - 第 3 轮：未排序部分
[4,3]，最小元素 3，与 4 交换→[1,2,3,4]
复杂度
- 时间复杂度：O (n²)（无论有序与否，都需遍历找最小值）
- 空间复杂度：O (1)（仅用临时变量）
代码
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i; // 记录未排序部分最小值索引
// 遍历未排序部分找最小值
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换最小值到已排序部分末尾
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
3. 插入排序（Insertion Sort）
核心思路
将数组分为 "已排序" 和 "未排序" 两部分，依次从未排序部分取元素，插入到已排序部分的正确位置（类似整理扑克牌）。
示例（排序 [3, 1, 4, 2]）
- 初始：已排序
[3]，未排序[1,4,2] - 插入 1：已排序部分
[3]→1 比 3 小，插入到 3 前→[1,3] - 插入 4：4 比 3 大，直接放末尾→
[1,3,4] - 插入 2：2 比 4 小→移 4→2 比 3 小→移 3→插入 2→
[1,2,3,4]
复杂度
- 时间复杂度：
- 最坏 / 平均：O (n²)（完全逆序，每次插入需移动所有元素）
- 最好：O (n)（已排序，无需移动）
- 空间复杂度：O (1)（仅用临时变量）
代码
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i]; // 待插入元素
int j = i - 1; // 已排序部分的最后一个索引
// 移动已排序元素，为key腾出位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 元素后移
j--;
}
arr[j + 1] = key; // 插入key到正确位置
}
}
4. 希尔排序（Shell Sort）
核心思路
插入排序的优化版：先将数组按间隔（gap） 分组，对每组进行插入排序；逐步缩小间隔（如n/2 → n/4 → ... → 1），最后间隔为 1 时完成排序。
示例（排序 [8, 9, 1, 7, 2, 3, 5, 4]，初始 gap=4）
- gap=4：分为 4 组
[8,2]、[9,3]、[1,5]、[7,4]，每组插入排序→[2,3,1,4,8,9,5,7] - gap=2：分为 2 组
[2,1,8,5]、[3,4,9,7]，每组插入排序→[1,3,2,4,5,7,8,9] - gap=1：整体插入排序→
[1,2,3,4,5,7,8,9]
复杂度
- 时间复杂度：与 gap 选择有关，平均约 O (n¹・³)，最坏 O (n²)（如 gap=1 时退化为插入排序）
- 空间复杂度：O (1)（仅用临时变量）
-
/** * 插入排序的缺点是：如果一个小元素在数组末尾（例如 [10,9,8,7,6,1]）， * 需要依次移动前面所有元素才能将其放到正确位置（移动 5 次）。而希尔排序通过分组解决这个问题： */
代码
public static void shellSort(int[] arr) {
int n = arr.length;
// 初始gap为n/2，逐步缩小
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个分组进行插入排序
for (int i = gap; i < n; i++) {
int key = arr[i];
int j = i;
// 组内元素比较（间隔为gap）
while (j >= gap && arr[j - gap] > key) {
arr[j] = arr[j - gap]; // 组内元素后移
j -= gap;
}
arr[j] = key; // 插入到组内正确位置
}
}
}
5. 归并排序（Merge Sort）
核心思路
分治思想：将数组递归拆分为两个子数组，直到子数组长度为 1（天然有序）；再合并两个有序子数组，最终得到完整有序数组。
示例（排序 [3, 1, 4, 2]）
- 拆分：
[3,1,4,2] → [3,1] 和 [4,2] → [3]、[1] 和 [4]、[2] - 合并：
[3]与[1]→[1,3]；[4]与[2]→[2,4]；[1,3]与[2,4]→[1,2,3,4]
复杂度
- 时间复杂度：O (n log n)（拆分 log n 层，每层合并共 O (n)）
- 空间复杂度：O (n)（需临时数组存储合并结果）
代码
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2; // 中间点拆分
mergeSort(arr, left, mid); // 左子数组排序
mergeSort(arr, mid + 1, right); // 右子数组排序
merge(arr, left, mid, right); // 合并左右子数组
}
}
// 合并两个有序子数组（[left,mid] 和 [mid+1,right]）
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1; // 左子数组长度
int n2 = right - mid; // 右子数组长度
int[] L = new int[n1]; // 临时左数组
int[] R = new int[n2]; // 临时右数组
// 复制数据到临时数组
System.arraycopy(arr, left, L, 0, n1);
System.arraycopy(arr, mid + 1, R, 0, n2);
// 合并临时数组到原数组
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++]; // 取较小值
}
// 复制剩余元素（若有）
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
6. 快速排序（Quick Sort）
核心思路
分治思想：选一个基准值（pivot），将数组分为 "小于基准" 和 "大于基准" 两部分（分区）；递归对两部分排序，最终整体有序。
示例（排序 [3, 1, 4, 2]，选最后一个元素 2 为基准）
- 分区：小于 2 的放左，大于 2 的放右→
[1,2,4,3]（基准 2 到位） - 递归左半
[1]（已有序）和右半[4,3] - 右半选 3 为基准→分区得
[3,4]（基准 3 到位） - 最终：
[1,2,3,4]
复杂度
- 时间复杂度：
- 平均：O (n log n)（均匀分区）
- 最坏：O (n²)（极端不平衡分区，如已排序数组选首尾为基准）
- 空间复杂度：O (log n)~O (n)（递归栈深度，平均 log n，最坏 n）
代码
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 分区，返回基准位置
quickSort(arr, low, pi - 1); // 排序左分区
quickSort(arr, pi + 1, high); // 排序右分区
}
}
// 分区函数：将小于基准的放左，大于基准的放右
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 选最右元素为基准
int i = low - 1; // 小于基准区域的边界（初始为空）
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) { // 当前元素小于等于基准
i++; // 扩大左区域
// 交换到左区域
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准放到左区域末尾（正确位置）
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // 返回基准位置
}
7. 堆排序（Heap Sort）
核心思路
利用大顶堆（父节点≥子节点）特性：
- 构建大顶堆（数组整体满足堆特性）；
- 反复将堆顶（最大值）与末尾元素交换，缩小堆大小并调整堆，直到堆为空。
示例（排序 [3, 1, 4, 2]）
- 构建大顶堆：
[4,2,3,1]（堆顶 4 是最大值） - 交换堆顶 4 和末尾 1→
[1,2,3,4]，调整剩余堆[1,2,3]为大顶堆→[3,2,1] - 交换堆顶 3 和末尾 1→
[1,2,3,4]，调整剩余堆[1,2]为大顶堆→[2,1] - 交换堆顶 2 和末尾 1→
[1,2,3,4]，排序完成
复杂度
- 时间复杂度：O (n log n)（构建堆 O (n)，调整堆 O (n log n)）
- 空间复杂度：O (1)（原地排序，仅用临时变量）
代码
java
运行
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--) {
// 堆顶与当前末尾交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整剩余元素为大顶堆（堆大小减1）
heapify(arr, i, 0);
}
}
// 调整以i为根的子树为大顶堆
private static void heapify(int[] arr, int n, int i) {
int largest = i; // 根节点
int left = 2 * i + 1; // 左子节点索引
int right = 2 * i + 2; // 右子节点索引
// 比较左子节点与根
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 比较右子节点与当前最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 若最大值不是根节点，交换并递归调整
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
8. 计数排序（Counting Sort）
核心思路
非比较排序：适用于整数且范围较小的场景。通过计数每个元素出现的次数，直接计算元素在结果中的位置。
示例（排序 [4, 2, 2, 8, 3, 3, 1]，范围 1~8）
- 计数数组（索引 0~7 对应值 1~8）：
[1,2,2,1,0,0,0,1]（1 出现 1 次，2 出现 2 次，等） - 前缀和数组（累计次数）：
[1,3,5,6,6,6,6,7]（值≤1 的有 1 个，≤2 的有 3 个，等） - 构建结果：倒序遍历原数组，根据前缀和放置元素→
[1,2,2,3,3,4,8]
复杂度
- 时间复杂度：O (n + k)（n 为元素数，k 为值的范围）
- 空间复杂度：O (n + k)（需计数数组和结果数组）
代码
public static void countingSort(int[] arr) {
if (arr.length == 0) return;
// 找最大值和最小值确定范围
int max = arr[0], min = arr[0];
for (int num : arr) {
if (num > max) max = num;
if (num < min) min = num;
}
int range = max - min + 1;
int[] count = new int[range]; // 计数数组
int[] output = new int[arr.length]; // 结果数组
// 计数每个元素出现次数（偏移min使索引非负）
for (int num : arr) {
count[num - min]++;
}
// 计算前缀和（确定元素在output中的位置）
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 倒序遍历原数组，保证稳定性（相同元素顺序不变）
for (int i = arr.length - 1; i >= 0; i--) {
int val = arr[i];
output[count[val - min] - 1] = val; // 放置元素
count[val - min]--; // 减少计数，下次放前一个位置
}
// 复制结果到原数组
System.arraycopy(output, 0, arr, 0, arr.length);
}
总结表
| 算法 | 时间复杂度（平均） | 时间复杂度（最坏） | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模数据 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 小规模数据，交换成本高时 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 基本有序或小规模数据 |
| 希尔排序 | O(n¹·³) | O(n²) | O(1) | 不稳定 | 中等规模数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 大规模数据，需稳定性 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 大规模数据（平均性能最优） |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 大规模数据，空间受限 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | 稳定 | 小范围整数（如年龄、成绩） |
根据数据规模、是否需要稳定排序、空间限制等选择合适算法即可。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
9
0- 0
已为社区贡献2条内容
所有评论(0)