详细实现了冒泡、选择、插入、希尔、堆、归并、快排、计数、桶、基数等 13 种经典排序算法，提供完整 Java 代码与性能分析。深入解析 JDK 7 至 24 版本中 Arrays.sort() 针对不同数据类型（int[], byte[], Object[] 等）的底层策略，包括混合插入排序、双基准点快排、TimSort 及堆排序切换机制。涵盖算法稳定性、时空复杂度及适用场景，帮助开发者掌握 Java 排序原理及工业级实现逻辑。
{
{
a.length - ;
;
(j > ) {
( ; i < j; i++) {
(a[i] > a[i + ]) {
a[i];
a[i] = a[i + ];
a[i + ] = exchange;
x = i;
}
}
j = x;
}
}
}
O(n²)，需要进行 n-1 轮排序，每轮进行 n-i-1 次比较和交换。O(n²)，随机分布的数组需要大量比较和交换操作。O(n)，优化版（带交换标记或记录最后交换位置）只需一轮比较即可结束。O(1)，属于原地排序，仅需常数级额外空间用于临时变量交换。由于时间复杂度较高，冒泡排序仅适合以下特定场景：
public class SelectionSort {
public static void sort(int[] a) {
int len = a.length;
for (int right = len - 1; right > 0; right--) {
int max = a[right];
int maxIndex = right;
for (int left = 0; left < right; left++) {
int num = a[left];
if (num > max) {
max = num;
maxIndex = left;
}
}
if (maxIndex != right) {
a[maxIndex] = a[right];
a[right] = max;
}
}
}
}
num > max 改成 num >= max 会不会让排序稳定？
left <= right 就可以保证稳定了，但是这样性能会相对降低，总的来说大部分选择排序都是不稳定的。O(n²) — 无论数组是否有序，都需要完整遍历未排序区间。O(1)，属于原地排序，仅需常数级额外空间用于临时变量交换。n-1 次交换，比冒泡排序（最多 n(n-1)/2 次交换）的交换次数少得多。public class InsertionSort {
public static void sort(int[] a) {
int len = a.length;
for (int i = 1; i < len; i++) {
int num = a[i];
int j = i - 1;
while (j >= 0 && num < a[j]) {
a[j + 1] = a[j];
j--;
}
if (j != i - 1) {
a[j + 1] = num;
}
}
}
}
O(n)，只需遍历一次数组，无需移动任何元素。O(n²)，每个元素都需要移动到最前面，需要进行大量的比较和移动操作。O(n²)，对于随机排列的数组，时间复杂度仍为平方级。O(1)，只需要常数级的额外空间，仅用临时变量保存待插入元素。O(n²)，但它的常数项非常小，在数据量很小时，实际运行速度比 O(n log n) 的算法（如快速排序）更快。O(n)，效率远超其他算法。public class ShellSort {
public static void sort(int[] a) {
int len = a.length;
for (int gap = len >> 1; gap >= 1; gap = gap >> 1) {
for (int low = gap; low < len; low++) {
int num = a[low];
int i = low - gap;
while (i >= 0 && num < a[i]) {
a[i + gap] = a[i];
i -= gap;
}
if (i != low - gap) {
a[i + gap] = num;
}
}
}
}
}
/2 的除法运算更直接，并且我们在许多的程序中把/2，*2 替换成左移一位，右移一位，这样也更具备通用性，举个例子，我们在二分查找中就会使用到（i+j）>>>1 这个语句，当 i 和 j 很大时，就可能会出现两个整数相加之后变成负数的情况（运算过程导致符号位由 0 变 1），这样就会导致算出来的结果有误，/2 其实底层逻辑就与>>1 一样，所以这里就用到了无符号右移符，但是你最终的结果还是会被当做有符号来处理，这样最终结果就可以保证为正数，不会出现溢出的问题。O(n log n)。O(n²)。O(n log n)。O(1)。public class PairInsertionSort {
public static void sort(int[] arr) {
int n = arr.length;
// 先处理前两个元素，确保有序
if (n >= 2 && arr[0] > arr[1]) {
swap(arr, 0, 1);
}
// 从第 3 个元素开始，成对处理
for (int i = 2; i < n; i += 2) {
// 取出当前对的两个元素
int a = arr[i];
int b = (i + 1 < n) ? arr[i + 1] : Integer.MAX_VALUE;
// 确保 a <= b，把较小的放在前面
if (a > b) {
int temp = a;
a = b;
b = temp;
}
// 先插入较大的元素 b
int posB = i - 1;
while (posB >= 0 && arr[posB] > b) {
arr[posB + 1] = arr[posB];
posB--;
}
arr[posB + 1] = b;
// 再插入较小的元素 a
int posA = posB - 1;
while (posA >= 0 && arr[posA] > a) {
arr[posA + 1] = arr[posA];
posA--;
}
arr[posA + 1] = a;
}
// 如果数组长度是奇数，单独处理最后一个元素
if (n % 2 != 0) {
int last = arr[n - 1];
int pos = n - 2;
while (pos >= 0 && arr[pos] > last) {
arr[pos + 1] = arr[pos];
pos--;
}
arr[pos + 1] = last;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
O(n²)，与普通插入排序一致。核心优化在于常数项更小：通过成对处理元素，减少了约一半的比较次数，实际运行速度比普通插入排序快 10%~20%。O(1)，属于原地排序。n < 47）：这是它最核心的适用场景。在数据量很小时，O(n²) 的复杂度劣势不明显，而常数项的优化能显著提升效率。数组与堆的索引关系（0 基索引）
| 节点类型 | 索引计算 |
|---|---|
| 父节点 | 子节点索引 i 的父节点：(i - 1)/2（向下取整） |
| 左子节点 | 父节点索引 i 的左子节点：2i + 1 |
| 右子节点 | 父节点索引 i 的右子节点：2i + 2 |
public class HeapSort {
public static void sort(int[] a) {
int len = a.length;
heapify(a, len);
for (int right = len - 1; right > 0; right--) {
int max = a[0];
a[0] = a[right];
a[right] = max;
down(a, 0, right);
}
}
public static void heapify(int[] array, int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
down(array, i, size);
}
}
private static void down(int[] array, int parent, int size) {
while (true) {
int maxIndex = parent;
int parentVal = array[parent];
int max = parentVal;
int left = parent * 2 + 1;
int right = left + 1;
if (left < size && array[left] > max) {
max = array[left];
maxIndex = left;
}
if (right < size && array[right] > max) {
max = array[right];
maxIndex = right;
}
if (maxIndex != parent) {
array[maxIndex] = parentVal;
array[parent] = max;
parent = maxIndex;
} else {
break;
}
}
}
}
O(n log n)，是稳定的时间复杂度。O(1)，属于原地排序。O(n²)），堆排序的 O(n log n) 稳定性是优势。public class MergeSort {
public static void sort(int[] a) {
int len = a.length;
int[] a2 = new int[len];
split(a, a2, 0, len - 1);
}
private static void split(int[] a1, int[] a2, int left, int right) {
if (left == right) {
return;
}
int m = (right + left) >>> 1;
split(a1, a2, left, m);
split(a1, a2, m + 1, right);
merge(a1, a2, left, m, m + 1, right);
System.arraycopy(a2, left, a1, left, right - left + 1);
}
private static void merge(int[] a1, int[] a2, int left1, int right1, int left2, int right2) {
int k = left1;
while (left1 <= right1 && left2 <= right2) {
int num1 = a1[left1];
int num2 = a1[left2];
if (num1 <= num2) {
a2[k] = num1;
left1++;
} else {
a2[k] = num2;
left2++;
}
k++;
}
if (left1 <= right1) {
System.arraycopy(a1, left1, a2, k, right1 - left1 + 1);
} else {
System.arraycopy(a1, left2, a2, k, right2 - left2 + 1);
}
}
}
O(n log n)，性能非常稳定，不会出现快速排序那样的最坏情况。O(n)，不是原地排序。O(n log n)，不会像快速排序那样在某些数据下退化到 O(n²)。public class MergeInsertionSort {
public static void sort(int[] a) {
int len = a.length;
int[] a2 = new int[len];
split(a, a2, 0, len - 1);
}
private static void split(int[] a1, int[] a2, int left, int right) {
if (right - left <= 32) {
insertion(a1, left, right);
return;
}
int m = (right + left) >> 1;
split(a1, a2, left, m);
split(a1, a2, m + 1, right);
merge(a1, a2, left, m, m + 1, right);
System.arraycopy(a2, left, a1, left, right - left + 1);
}
public static void insertion(int[] a, int left, int right) {
for (int i = left + 1; i < right; i++) {
int num = a[i];
int j = i - 1;
while (j >= left && num < a[j]) {
a[j + 1] = a[j];
j--;
}
if (j != i - 1) {
a[j + 1] = num;
}
}
}
private static void merge(int[] a1, int[] a2, int left1, int right1, int left2, int right2) {
int k = left1;
while (left1 <= right1 && left2 <= right2) {
int num1 = a1[left1];
int num2 = a1[left2];
if (num1 <= num2) {
a2[k] = num1;
left1++;
} else {
a2[k] = num2;
left2++;
}
k++;
}
if (left1 <= right1) {
System.arraycopy(a1, left1, a2, k, right1 - left1 + 1);
} else {
System.arraycopy(a1, left2, a2, k, right2 - left2 + 1);
}
}
}
O(n log n)，但通过减少递归深度和常数项，实际运行速度比纯归并排序快 10%~20%。O(n)，和纯归并排序一致，需要一个辅助数组。Arrays.sort()）的核心实现方式，适合绝大多数日常业务开发中的排序需求。left、右指针 right）遍历数组，将小于基准的元素移到左半区，大于基准的移到右半区，基准最终落在'正确的排序位置'。left~基准前）和右半区（基准后~right）重复步骤 1-2，直到子数组长度 ≤ 1（天然有序）。import java.util.concurrent.ThreadLocalRandom;
public class QuickSort {
public static void sort(int[] a) {
quick(a, 0, a.length - 1);
}
private static void quick(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int p = partition1(arr, left, right);
quick(arr, left, p - 1);
quick(arr, p + 1, right);
}
/**
* 单边
*
* @param arr 数组
* @param left 左边界
* @param right 右边界
* @return 结果
*/
private static int partition1(int[] arr, int left, int right) {
int pv = arr[right];
int i = left;
int j = left;
while (j < right) {
int now = arr[j];
if (now < pv) {
if (i != j) {
arr[j] = arr[i];
arr[i] = now;
}
i++;
}
j++;
}
arr[right] = arr[i];
arr[i] = pv;
return i;
}
/**
* 双边
*
* @param arr 数组
* @param left 左边界
* @param right 右边界
* @return 结果
*/
private static int partition2(int[] arr, int left, int right) {
int i = left + 1;
int j = right;
int pv = arr[left];
while (i < j) {
while (i < j && arr[j] > pv) {
j--;
}
while (i < j && arr[i] <= pv) {
i++;
}
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
arr[left] = arr[j];
arr[j] = pv;
return j;
}
/**
* 优化后的双边
*
* @param arr 数组
* @param left 左边界
* @param right 右边界
* @return 结果
*/
private static int partition3(int[] arr, int left, int right) {
int i = left + 1;
int j = right;
int index = left + ThreadLocalRandom.current().nextInt(right - left + 1);
int pv = arr[index];
arr[index] = arr[left];
arr[left] = pv;
while (i <= j) {
while (i <= j && arr[j] > pv) {
j--;
}
while (i <= j && arr[i] < pv) {
i++;
}
if (i < j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i++;
j--;
}
}
arr[left] = arr[j];
arr[j] = pv;
return j;
}
}
O(n log n)。O(n log n)。O(n²)（但因为用了随机选基准，这种情况概率极低）。O(log n)，最坏为 O(n)（可通过尾递归优化进一步降低）。//非尾调用
int c = 函数();
return c;
//非尾调用
return 函数() + 1;
//尾调用
return 函数();
O(log n)。O(n log n)。O(n log n) 效率很高）。public class CountingSort {
/**
* 占用空间少但不保证稳定
*
* @param a
*/
public static void sort1(int[] a) {
int max = a[0];
int min = a[0];
int len = a.length;
for (int i = 0; i < len; i++) {
int now = a[i];
if (now > max) {
max = now;
}
if (now < min) {
min = now;
}
}
len = max - min + 1;
int[] count = new int[len];
for (int v : a) {
count[v - min]++;
}
int k = 0;
for (int i = 0; i < len; i++) {
while (count[i] > 0) {
a[k] = min + i;
count[i]--;
k++;
}
}
}
/**
* 占用空间多一点但保证稳定
*
* @param a
*/
public static void sort2(int[] a) {
int max = a[0];
int min = a[0];
int len = a.length;
for (int i = 0; i < len; i++) {
int now = a[i];
if (now > max) {
max = now;
}
if (now < min) {
min = now;
}
}
int countLen = max - min + 1;
int[] count = new int[countLen];
for (int v : a) {
count[v - min]++;
}
for (int i = 1; i < countLen; i++) {
count[i] += count[i - 1];
}
int[] out = new int[len];
for (int i = len - 1; i >= 0; i--) {
int num = a[i];
int index = num - min;
out[count[index] - 1] = num;
count[index]--;
}
System.arraycopy(out, 0, a, 0, len);
}
}
O(n + k)。n 是待排序元素的数量，k 是数据的取值范围（max - min + 1）。k 较小时（如学生成绩 0-100），它是线性时间排序，效率远超快排等基于比较的排序。k 远大于 n 时（如排序 100 个范围 0-100000 的数），时间和空间效率会大幅下降。O(n + k)，需要额外的输出数组和计数数组。sort1）：O(k)，仅需计数数组，原地修改原数组。byte[]、char[]、short[] 这些范围小的也适用。import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
public static void sort(int[] a, int range) {
int max = a[0];
int min = a[0];
for (int num : a) {
if (num > max) {
max = num;
} else if (num < min) {
min = num;
}
}
int len = (max - min) / range + 1;
ArrayList<Integer>[] buckets = new ArrayList[len];
for (int i = 0; i < len; i++) {
buckets[i] = new ArrayList<>();
}
for (int age : a) {
buckets[(age - min) / range].add(age);
}
int k = 0;
for (ArrayList<Integer> bucket : buckets) {
Collections.sort(bucket);
for (Integer num : bucket) {
a[k++] = num;
}
}
}
}
O(n + k)，当数据均匀分布时，每个桶内元素数量相近，桶内排序的总代价较低。Θ(n)，数据完美均匀分布，每个桶仅含 1 个元素，无需额外桶内排序。O(n²)，所有元素集中在同一个桶中，退化为桶内排序算法的时间复杂度（如插入排序）。O(n + k)，需要额外的空间存储 k 个桶和所有元素。
import java.util.ArrayList;
public class RadixSort {
public static void sort(String[] a, int range) {
ArrayList<String>[] buckets = new ArrayList[10];
for (int i = 0; i < 10; i++) {
buckets[i] = new ArrayList<>();
}
for (int i = range - 1; i >= 0; i--) {
for (String string : a) {
buckets[string.charAt(i) - '0'].add(string);
}
int k = 0;
for (ArrayList<String> bucket : buckets) {
for (String string : bucket) {
a[k++] = string;
}
bucket.clear();
}
}
}
}
O(d * (n + k))（无数据分布依赖，是稳定的线性时间排序）。d：待排序数据的位数 / 字符位数（如 11 位手机号的 d=11，32 位整数的 d=32）。n：待排序数据的数量。k：基数（十进制数 k=10，二进制 k=2，字符串 k=26/256）。O(n + k)：
O(log n) 递归栈）、堆排序（O(1)），基数排序的空间开销更大。O(n) 的线性优势，且稳定排序可保留相同前缀数据的相对顺序。| 排序算法 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 | 入门教学 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 入门教学，交换次数比冒泡排序少 |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 | 小规模数据、几乎有序数据，交换次数比冒泡排序少 |
| 希尔排序 | O(n log n) | O(n²) | O(n log n) | O(1) | 不稳定 | 中大规模数据、平衡实现复杂度和性能 |
| 成对插入排序 | O(n²) | O(n²) | O(n²) | O(1) | 稳定 | 小数据排序，复杂排序算法的子过程 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 中大规模数据、需要稳定时间复杂度、动态获取最值 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 中大规模数据、需稳定性场景 |
| 归并 + 插入排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 中大规模数据、对性能要求高、需要稳定性场景 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 | 中大规模数据（平均高效） |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n+k) | 稳定 | k（数值范围）较小 |
| 桶排序 | O(n + k) | O(n²) | O(n) | O(n + k) | 稳定 | 分布均匀的数组、大规模数据 |
| 基数排序 | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 | 整数 / 字符串数组、大规模数据 |
| 排序目标 | 条件 | 采用算法 |
|---|---|---|
int[] long[] float[] double[] | size < 47 | 混合插入排序 (pair) |
size < 286 | 双基准点快排 | |
| 有序度低 | 双基准点快排 | |
| 有序度高 | 归并排序 | |
byte[] | size <= 29 | 插入排序 |
size > 29 | 计数排序 | |
char[] short[] | size < 47 | 插入排序 |
size < 286 | 双基准点快排 | |
| 有序度低 | 双基准点快排 | |
| 有序度高 | 归并排序 | |
size > 3200 | 计数排序 | |
Object[] | -Djava.util.Arrays.useLegacyMergeSort=true | 传统归并排序 |
| 默认 | TimSort |
int[] long[] float[] double[]O(n²)，但在数据量极小时，其常数项（比较、交换次数）远低于快排、归并排序。O(n log n)，且在均匀分布数据上的性能优于单轴快排。O(n log n) 复杂度优势开始显现，同时其常数项开销也能被接受。O(n)，且能避免快排在有序数据下退化为 O(n²) 的风险。byte[]size ≤ 29）→ 插入排序
O(n²)，但在数据量极小时，其常数项（比较、交换次数）远低于计数排序。byte 类型的取值范围仅为 -128~127，但计数排序仍需创建大小为 256 的计数数组，在极小数据量下，这个初始化和清理的开销会抵消算法本身的优势。size > 29）→ 计数排序
O(n + k)（此处 k=256），因为 k 是常数，时间复杂度可近似为 O(n)，远优于插入排序的 O(n²)。byte 这种取值范围固定的类型，是效率最优的选择，且属于稳定排序。byte[] 这类取值范围极小的数组，计数排序的线性时间复杂度、低常数项开销和稳定性，让它成为了比快排更优的选择。O(n + k)，这里 k=256 是个极小的常数，所以时间复杂度几乎就是 O(n)，属于线性时间。O(n log n)，在 n 较大时，O(n) 比 O(n log n) 效率高得多。char[] short[]size > 3200 → 计数排序
char 的取值范围是 0~65535，short 的取值范围是 -32768~32767，当数据量超过 3200 时，计数排序的 O(n + k) 线性复杂度（k≈65536）效率会超过快排的 O(n log n)，成为更优选择。Object[]O(n) 的最优时间复杂度，整体性能远优于传统归并排序。Object[] 排序时，稳定性是一个重要特性（比如排序对象时保留相等元素的原始顺序），而 TimSort 是稳定排序，满足这一需求（快速排序并不稳定）。Arrays.sort(Object[]) 使用的是传统归并排序。为了保证旧代码在升级后行为完全一致，Java 提供了系统属性 -Djava.util.Arrays.useLegacyMergeSort=true 作为降级开关。| 排序目标 | 条件 | 采用算法 |
|---|---|---|
int[] long[] float[] double[] | size < 44 并位于最左侧 | 插入排序 |
| size < 65 并不是最左侧 | 混合插入排序 (pin) | |
| 有序度低 | 双基准点快排 | |
| 递归次数超过 384 | 堆排序 | |
| 对于整个数组或非最左侧 size > 4096，有序度高 | 归并排序 | |
byte[] | size <= 64 | 插入排序 |
| size > 64 | 计数排序 | |
char[] short[] | size < 44 | 插入排序 |
| 再大 | 双基准点快排 | |
| 递归次数超过 384 | 计数排序 | |
| size > 1750 | 计数排序 | |
Object[] | -Djava.util.Arrays.useLegacyMergeSort=true | 传统归并排序 |
| 默认 | TimSort |
int[] long[] float[] double[]size < 44）单独划分出来，直接用插入排序。这是因为最左侧的数组片段在缓存中更容易被连续访问，插入排序的局部性优势能被最大化。size < 44），这些额外开销的占比会变得很高，甚至超过它带来的收益。O(n log n)，这刚好可以用来兜底快排最坏情况下的 O(n²) 性能问题。O(1)），这一点比需要 O(n) 额外空间的归并排序更有优势。O(n) 的额外空间来存储临时数据，在处理大数组时会带来明显的内存开销。O(n²)，性能完全无法接受。Object[]，无法直接用于基础类型数组（如 int[]、long[]），且同样需要额外空间。byte[]byte[] 这种单字节数据，CPU 可以更高效地处理连续内存访问，缓存命中率也更高，这让插入排序在 size <= 64 的范围内，实际执行速度依然快于计数排序。char[] short[]为什么放弃了有序性的判断？
O(n) 的时间开销。对于 char[] 和 short[] 这类基础类型数组，这个额外的遍历成本，在很多场景下已经超过了'选择更优算法'带来的收益。尤其是在数据量较大时，O(n) 的检测开销会直接拖累整体性能。char[] 和 short[] 的取值范围有限（char 是 0short 是 -32768O(n + k)（k 为取值范围），在数据量较大时（比如 size > 1750），它的效率远超归并排序或快排。int、long、float、double 的取值范围极大，远超过 char/short/byte，无法用计数排序兜底。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online