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

Java 八大经典排序算法全解析

news 2025/8/8 11:30:56

1. 冒泡排序（Bubble Sort）

1.1 Java 代码实现

public static void bubble(int[] arr) {// 外层循环控制总共需要进行多少轮冒泡（n-1轮即可）for (int j = 0; j < arr.length - 1; j++) {// 内层循环负责每轮两两比较，将当前未排序部分的最大元素逐渐“冒泡”到末尾// 每完成一轮，末尾一个元素归位，所以内层循环长度逐渐减少for (int i = 0; i < arr.length - 1 - j; i++) {// 比较相邻两个元素，如果前一个比后一个大，则交换，保证较大元素后移if (arr[i] > arr[i + 1]) {int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;}}}
}

1.2 解释说明

冒泡排序是一种最简单直观的排序算法。它通过多次遍历数组，比较相邻元素的大小，若顺序不正确则交换，每轮都能将最大值“冒泡”到末尾。

通俗理解：重的数像气泡一样“浮”到数组后面。

示例：

对数组 [5, 3, 4, 1, 2] 执行冒泡排序，过程如下：

第 1 轮：[3, 4, 1, 2, 5] —— 最大的 5 冒到最后
第 2 轮：[3, 1, 2, 4, 5] —— 次大值 4 冒到倒数第二
...
共执行 n-1 轮，数组最终有序。

1.3复杂度分析

性质	分析
时间复杂度	最坏：O(n²)（完全逆序）最好：O(n)（已经有序）平均：O(n²)
空间复杂度	O(1)，原地排序
稳定性	✅ 稳定排序（相等元素不会交换位置）

✅ 优化建议：可增加“标志位”，当某轮无交换时提前退出循环，避免无意义遍历。

1.4 优劣比较

✅ 优点	❌ 缺点
实现简单、逻辑直观	效率低，最坏和平均都为 O(n²)
稳定性好，不会打乱相同值顺序	不适合大规模数据
可优化为“冒泡 + 提前退出”形式

1.5 适用场景

排序算法的入门学习
数据量小、性能要求不高的场景
对排序结果稳定性有要求（如：多个字段排序）

2. 选择排序（Selection Sort）

2.1 Java 代码实现

public static void select(int[] arr1) {// 外层循环控制每轮选择的起始位置，最终每轮确定一个最小元素的位置for (int i = 0; i < arr1.length - 1; i++) {int min = arr1[i];       // 记录当前轮的最小值，初始为当前位置元素int position = i;        // 记录最小值的位置索引// 内层循环从 i+1 开始遍历，寻找比 min 更小的元素for (int j = i + 1; j < arr1.length; j++) {if (arr1[j] < min) {min = arr1[j];   // 更新最小值position = j;    // 更新最小值索引}}// 将找到的最小值与当前位置元素交换，完成本轮排序arr1[position] = arr1[i];arr1[i] = min;}
}

2.2 解释说明

选择排序是一种直观的排序方法，其核心思想是：

每一轮从“未排序部分”中选出最小值，放到“已排序部分”的末尾。

以数组 [6, 3, 1, 4, 2] 为例，选择排序过程如下：

第 1 轮：选择最小的 1，放到第一个位置 → [1, 3, 6, 4, 2]
第 2 轮：选择次小的 2，放到第二个位置 → [1, 2, 6, 4, 3]
…
共执行 n-1 轮，最终数组有序。

注意：选择排序在寻找最小值时不会立即交换，而是等一轮找完再换，减少了交换次数，但不是稳定排序。

2.3 复杂度分析

性质	分析
时间复杂度	最好、最坏、平均情况都为 O(n²)，与数据初始状态无关
空间复杂度	O(1)，原地排序
稳定性	❌ 不稳定排序（可能交换不相邻的相等元素）

⚠️ 注意：选择排序无论是否已经排好序，仍会进行全量扫描找最小值，因此无法优化为 O(n)。

2.4 优劣比较

✅ 优点	❌ 缺点
实现简单，逻辑清晰	时间复杂度固定为 O(n²)
比冒泡排序交换次数更少	不稳定排序，可能打乱相同值顺序
适合交换代价高、读取代价低的场景	不适合处理大规模数据

2.5 适用场景

数据量小，且对稳定性无要求
交换次数比冒泡排序更少，适用于交换成本高的场景
作为教学用途了解“选择最小值”的策略

3. 插入排序（Insertion Sort）

3.1 Java 代码实现

public static void insert(int[] arr2) {// 从第二个元素开始，逐个将当前元素插入到前面已排序序列中合适的位置for (int i = 1; i < arr2.length; i++) {// 从当前元素的前一个位置开始向前比较for (int j = i - 1; j >= 0; j--) {// 如果当前元素比前一个元素小，交换位置if (arr2[j + 1] < arr2[j]) {int temp2 = arr2[j];arr2[j] = arr2[j + 1];arr2[j + 1] = temp2;} else {// 当前元素已找到合适位置，提前退出内层循环break;}}}
}

3.2 解释说明

插入排序就像“抓扑克牌”排序的过程：

假设前面部分是已经排好序的；
每次从无序区取一个元素，与前面有序区从后向前比较；
找到合适位置插入，保持有序。

通俗理解：

就像打扑克牌时从牌堆里抓牌，一张张插入到已有的有序手牌中。

示例（数组 [5, 3, 4, 1, 2]）排序过程：

第 1 次：[3, 5, 4, 1, 2]
第 2 次：[3, 4, 5, 1, 2]
第 3 次：[1, 3, 4, 5, 2]
第 4 次：[1, 2, 3, 4, 5]

3.3 复杂度分析

性质	分析说明
时间复杂度	最坏：O(n²)（完全逆序）最好：O(n)（已排序）平均：O(n²)
空间复杂度	O(1)，原地排序
稳定性	✅ 稳定排序（相等元素不交换）

3.4 优劣比较

优点	缺点
实现简单、稳定性好	时间复杂度较高 O(n²)
对小规模或近乎有序数据性能较好	不适合大规模无序数据
每次插入可直接定位最合适位置	需大量元素移动操作

3.5适用场景

数据基本有序；
元素数量较少；
希望排序过程尽量稳定，避免相等元素乱序；
适用于链表（插入效率高）。

4. 希尔排序（Shell Sort）

4.1 Java 代码实现

public static void shel(int[] arr3) {// 从数组长度一半开始分组，逐渐缩小分组间隔直到为1for (int grp = arr3.length / 2; grp >= 1; grp /= 2) {// 遍历每组中从第grp个元素开始的元素，进行插入排序for (int i = grp; i < arr3.length; i++) {// 对当前元素与组内前面元素比较，步长为grp，实现分组插入排序for (int j = i - grp; j >= 0; j -= grp) {// 若后元素比前元素小，交换，保证组内局部有序if (arr3[j + grp] < arr3[j]) {int temp = arr3[j];arr3[j] = arr3[j + grp];arr3[j + grp] = temp;} else {// 已找到合适位置，提前退出内层循环break;}}}}
}

4.2 解释说明

希尔排序是 插入排序 的一种优化版本，得名于它的发明者 Donald Shell。它通过 将数组按一定间隔分组，对各组分别进行插入排序，从而加快整体排序过程。

核心思想：

将整个数组按一定步长（gap）分成若干个子序列；
对每个子序列进行插入排序；
不断缩小 gap，最终 gap = 1 时再进行一次普通插入排序。

最初 gap 可以设为数组长度的一半，然后每轮缩小为原来的一半，直到 gap 为 1。

以数组 [9, 8, 3, 7, 5, 6, 4, 1] 为例，gap 初始为 4：

第 1 轮 gap=4 → 对 [9, 5], [8, 6], [3, 4], [7, 1] 插入排序

→ [5, 9], [6, 8], [3, 4], [1, 7]

→ [5, 6, 3, 1, 9, 8, 4, 7]

第 2 轮 gap=2 → 对 [5, 3, 9, 4], [6, 1, 8, 7] 插入排序

→ [3, 4, 5, 9], [1, 6, 7, 8]

→ [3, 1, 4, 6, 5, 7, 9, 8]

第 3 轮 gap=1 → 普通插入排序完成收尾。

通俗理解：

原始的插入排序在大规模数据乱序时移动慢；而希尔排序先让远距离元素到差不多的位置，再让相邻元素细排，大大提高了效率。

4.3 复杂度分析

性质	分析说明
最好时间复杂度	O(n log n)（gap 设计合理时）
最坏时间复杂度	O(n²)（gap 退化不理想时）
平均时间复杂度	约 O(n^1.3 ~ n^1.5)，依 gap 而异,可看成O(n log n)
空间复杂度	O(1)，原地排序
稳定性	❌ 不稳定，可能打乱相等元素顺序

4.4 优劣比较

优点	缺点
改进插入排序效率，适合较大数据量	算法较复杂，不易理解
空间复杂度低（O(1)）	不稳定排序
可用于性能比冒泡/插入更高的排序场合	gap 选择会影响排序性能

4.5 适用场景

中等规模的数据排序；
对空间要求较高（需原地排序）；
在插入排序慢的情况下使用它能显著提高性能。

5. 堆排序（Heap Sort）

5.1 Java 代码实现

// 堆排序
public static void heap(int[] arr) {// 第一步：从最后一个非叶子节点开始，构建大顶堆for (int p = arr.length / 2 - 1; p >= 0; p--) {adjust(arr, p, arr.length);}// 第二步：排序逻辑for (int i = arr.length - 1; i > 0; i--) {// 将堆顶元素（最大值）交换到数组末尾int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 对剩下的元素重新构造大顶堆adjust(arr, 0, i);}
}// 构建堆的辅助方法
public static void adjust(int[] arr, int parent, int length) {int child = 2 * parent + 1; // 左子节点while (child < length) {int rchild = child + 1; // 右子节点// 找出较大的子节点if (rchild < length && arr[rchild] > arr[child]) {child = rchild;}// 如果子节点大于父节点，则交换if (arr[child] > arr[parent]) {int temp = arr[parent];arr[parent] = arr[child];arr[child] = temp;// 继续向下调整parent = child;child = 2 * parent + 1;} else {break;}}
}

5.2 解释说明

堆排序是一种利用堆这种数据结构（通常是大顶堆）进行排序的方法。

大顶堆（Max Heap）：每个父节点都大于等于子节点，堆顶是当前最大的元素。
每次将堆顶最大值取出放到数组末尾，然后重新调整剩余元素为堆结构。

核心思想：

以数组 [4, 6, 8, 5, 9] 为例进行堆排序：

第一步：构建大顶堆

数组下标为：[0, 1, 2, 3, 4]
第一个非叶子节点：(n-1)/2 = 1
从节点 1 开始向上构造堆：
1. 比较节点 1（值6）和它的子节点 3 和 4（值5 和 9），9 最大 → 交换 6 和 9
2. 继续比较新的节点 4（值6）没有子节点，结束
3. 回到节点 0（值4）和子节点 1（现在是9）和2（8）比较 → 9 最大 → 交换 4 和 9
4. 再比较节点 1（值4）和它的子节点（原来的6和5） → 6 最大 → 交换

➡️ 此时堆：[9, 6, 8, 5, 4]

第二步：排序

重复以下操作：

交换堆顶和最后一个元素（最大值放到末尾）
缩小堆的大小（排好序的部分不再动）
重新调整剩下部分为大顶堆

例如：

交换 9 和 4 → [4, 6, 8, 5, 9]
调整为堆 → [8, 6, 4, 5, 9]
交换 8 和 5 → [5, 6, 4, 8, 9]
调整 → [6, 5, 4, 8, 9]
...

直到只剩一个元素，排序完成。

5.3 复杂度分析

属性	值
最好时间复杂度	O(n log n)
最坏时间复杂度	O(n log n)
空间复杂度	O(1)
稳定性	❌ 不稳定（元素可能交换顺序）

5.4 优劣比较

优点	缺点
时间复杂度为 O(n log n)，性能稳定	实现略复杂，理解需要掌握堆结构
不受输入数据的影响，最坏情况也为 O(n log n)	不是稳定排序（相等元素可能交换顺序）
空间复杂度低（O(1)），无需额外空间	对部分场景不如快速排序表现优秀（例如小数据量）
适合数据量较大或对最坏性能有要求的排序	建堆过程和维护堆有一定计算开销

5.5 适用场景

大规模数据排序，尤其在对最坏情况性能有保障要求时；
需要原地排序（in-place），不能使用额外内存；
数据分布不均、已知快速排序表现不佳时，可以作为稳定替代；
对稳定性要求不高的工程场景（如内核排序、数据结构底层实现）；

6. 基数排序（Radix Sort）

6.1 Java 代码实现

// 基数排序（LSD：从低位到高位）
public static void radix(int[] arr) {int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) max = arr[i]; // 找最大值}int maxDigit = (max + "").length(); // 最大数字的位数int n = 1; // 每次处理的位数（1, 10, 100...）// 辅助空间：10个桶int[][] bucket = new int[10][arr.length];int[] count = new int[10]; // 每个桶中元素的计数for (int d = 0; d < maxDigit; d++) {// 分配：按当前位放入桶for (int i = 0; i < arr.length; i++) {int digit = (arr[i] / n) % 10;bucket[digit][count[digit]++] = arr[i];}// 收集：从桶中取出到原数组int idx = 0;for (int i = 0; i < 10; i++) {for (int j = 0; j < count[i]; j++) {arr[idx++] = bucket[i][j];}count[i] = 0; // 清空桶计数器}n *= 10; // 处理下一位}
}

6.2 解释说明

基数排序是一种非比较型整数排序算法，适用于位数有限的整数排序。

核心思想：将整数按位切割成不同的数字，然后按每个位数分别进行排序（通常从低位到高位），每次排序保持之前的相对顺序。

例如，对数组 [170, 45, 75, 90, 802, 24, 2, 66] 进行基数排序：

第一次按个位排序：[170, 90, 802, 2, 24, 45, 75, 66]
第二次按十位排序：[802, 2, 24, 45, 66, 170, 75, 90]
第三次按百位排序：[2, 24, 45, 66, 75, 90, 170, 802]

最终得到有序数组。

注意：基数排序依赖“稳定的子排序算法”如计数排序。

6.3 复杂度分析

属性	值
最好时间复杂度	O(n × k)（k 是位数）
最坏时间复杂度	O(n × k)
空间复杂度	O(n + k)
稳定性	✅ 稳定排序

6.4 优劣比较

优点	缺点
非比较型排序，时间复杂度低，适合大数据排序	仅适用于整数或可分割为整数的排序（如字符串）
稳定排序，适合对有重复元素的排序	需要额外空间（桶和辅助数组）
对数据分布不敏感，排序性能稳定	实现逻辑较复杂，理解难度比冒泡、插入等略高

6.5 适用场景

需要对 大量整数 或 等长字符串 进行排序；
希望使用 稳定排序算法；
对排序速度有较高要求，且能接受额外的空间开销；
数据值范围较小但数据量很大，例如银行账单、身份证号排序等。

7. 归并排序（Merge Sort）

7.1 Java 代码实现

// 归并排序的递归拆分函数，将数组分成两部分分别排序后合并
public static void spilt(int[] arr, int left, int right) {// 递归终止条件：当左右索引相等，表示只有一个元素，已经有序，直接返回if (left == right) {return;}// 计算中间索引，避免溢出一般写法是 left + (right - left)/2，这里简单写法也可int mid = (left + right) / 2;// 递归拆分左半部分spilt(arr, left, mid);// 递归拆分右半部分spilt(arr, mid + 1, right);// 合并左右两个有序部分，得到整体有序merge(arr, left, mid, right);
}// 合并两个有序子数组 arr[left..mid] 和 arr[mid+1..right]，使其整体有序
public static void merge(int[] arr, int left, int mid, int right) {int s1 = left;      // 左半部分起始索引int s2 = mid + 1;   // 右半部分起始索引int[] temp = new int[right - left + 1]; // 临时数组，用于存放合并结果int index = 0;      // 临时数组下标// 当左右两部分都还有元素时，选择较小元素放入临时数组while (s1 <= mid && s2 <= right) {if (arr[s1] < arr[s2]) {temp[index++] = arr[s1++];} else {temp[index++] = arr[s2++];}}// 左半部分剩余元素全部放入临时数组while (s1 <= mid) {temp[index++] = arr[s1++];}// 右半部分剩余元素全部放入临时数组while (s2 <= right) {temp[index++] = arr[s2++];}// 将临时数组的数据写回原数组对应区间，实现排序合并for (int i = 0; i < temp.length; i++) {arr[left + i] = temp[i];}
}

7.2 解释说明

归并排序是一种分治思想的典型应用，通过**“分+合”**的方式实现排序。

核心思想：
将原数组不断地对半拆分为左右两个子数组，直到每个子数组仅包含一个元素，然后再两两合并为有序数组。

例如，对数组 [8, 4, 5, 7, 1, 3, 6, 2] 进行归并排序：

拆分成 [8, 4, 5, 7] 和 [1, 3, 6, 2]
再拆成 [8,4] [5,7] ... 直到单个元素
然后归并成 [4,8] [5,7] → [4,5,7,8] 等等
最终输出：[1,2,3,4,5,6,7,8]

7.3 复杂度分析

属性	值
最好时间复杂度	O(n log n)
最坏时间复杂度	O(n log n)
空间复杂度	O(n)
稳定性	✅ 稳定排序

7.4 优劣比较

优点	缺点
时间复杂度稳定为 O(n log n)	空间复杂度为 O(n)，需额外空间
稳定排序，适用于对象排序（保留顺序）	实现复杂度较高
性能优于简单排序，适合链表、外部排序等场景	递归方式较深时存在栈溢出风险

7.5 适用场景

对稳定性有要求的排序任务；
排序链表或大规模数据（可用于外部排序）；
内存充足，能够接受额外空间开销；
数据量大，但排序性能要求稳定。

8. 快速排序（Quick Sort）

8.1 Java 代码实现

private static void quick(int[] arr, int left, int right) {// 递归终止条件：当区间内元素小于等于1个时，直接返回（已排序）if (left >= right) {return;}// 选择基准值（pivot），这里用区间第一个元素int base = arr[left];// 初始化左右指针int i = left;int j = right;// 通过双指针扫描交换，将比基准值小的放左边，比基准值大的放右边while (i != j) {// 从右向左找第一个小于基准值的元素while (arr[j] >= base && i != j) {j--;}// 从左向右找第一个大于基准值的元素while (arr[i] <= base && i != j) {i++;}// 交换两个指针所指元素，保证左边元素小于基准，右边元素大于基准int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 此时 i 和 j 相遇，将基准值放到指针所在位置（分割点）arr[left] = arr[i];arr[i] = base;// 递归排序基准左侧子数组sort(arr, left, i - 1);// 递归排序基准右侧子数组sort(arr, i + 1, right);
}

8.2 解释说明

快速排序是一种“分而治之”的排序算法，利用递归不断将数组划分为小于和大于基准值的两部分，再分别对这两部分递归排序。

核心思想：
选取一个基准值（如第一个元素），将数组中小于它的放左边，大于它的放右边，然后再对左右子数组递归进行同样操作。

例如，对 [5, 2, 9, 1, 5, 6] 进行快速排序：

选 5 为基准 → [2, 1] [5] [9, 5, 6]
继续对左右子数组排序
最终输出：[1, 2, 5, 5, 6, 9]

8.3 复杂度分析

属性	值
最好时间复杂度	O(n log n)
最坏时间复杂度	O(n²)
空间复杂度	O(log n)
稳定性	❌ 不稳定排序

8.4 优劣比较

优点	缺点
平均时间复杂度为 O(n log n)，常数项小	最坏情况下时间复杂度为 O(n²)
不需要额外空间，原地排序	不稳定排序，可能改变相等元素顺序
排序速度快，尤其对大数组性能优于归并、堆排序	递归过深会引发栈溢出

8.5 适用场景

当排序性能优先考虑，且可以接受不稳定排序；
数据量较大，并且数据分布较随机；
内存空间有限，希望使用原地排序；
可接受最坏情况的优化（如使用“三数取中”或随机化枢轴）。

9.总结

排序算法	时间复杂度	空间复杂度	稳定性	优点	缺点	适用场景
冒泡排序	最坏 O(n²)，最好 O(n)	O(1)	稳定	简单，稳定	效率低	小规模数据，几乎有序数据
选择排序	O(n²)	O(1)	不稳定	交换少，简单	时间复杂度高，不稳定	交换代价高场景，小规模
插入排序	最坏 O(n²)，最好 O(n)	O(1)	稳定	简单，稳定，对近乎有序好	大规模无序数据效率低	小规模或部分有序数据
希尔排序	约 O(n^1.3~n^1.5)	O(1)	不稳定	改进插入排序，效率较好	算法复杂，不稳定	中等规模数据
堆排序	O(n log n)	O(1)	不稳定	稳定性能，不受输入影响	实现复杂，不稳定	大规模数据，对最坏性能要求高
基数排序	O(n × k)	O(n + k)	稳定	非比较排序，效率高	只适合整数，额外空间需求	大量整数排序
归并排序	O(n log n)	O(n)	稳定	稳定，适合链表和外部排序	额外空间，递归复杂	大数据，链表，稳定性需求高
快速排序	平均 O(n log n)	O(log n)	不稳定	平均性能最好，空间低	最坏 O(n²)，不稳定，递归风险	大多数场景，要求速度优先