Java 全排序算法实现与 不同版本JDK 排序策略解析
本文将完整实现 13 种经典排序算法（冒泡、选择、堆、插入、希尔、归并、归并 + 插入、单边快排、双边快排、计数、桶、基数），并深入分析 Java 不同 JDK 版本对排序算法的选择与优化逻辑。
一、冒泡排序（Bubble Sort）
1.1 介绍
- 基于相邻元素的比较与交换，是一种交换排序。
- 每一轮都会把当前未排序区间的最大值 “冒泡” 到区间尾部。
1.2 代码实现
public class BubbleSort {
public static void bubbleSort(int[] a) {
int j = a.length - 1;
int x = 0;
while (j > 0){
for (int i = 0 ; i < j ; i++){
if (a[i] > a[i + 1]){
int exchange = a[i];
a[i] = a[i+1];
a[i+1] = exchange;
x = i;
}
}
j = x;
}
}
}
- 这里的代码相对传统的冒泡排序进行了优化，已知每次排序都会把最大的交换到最右边，使j右侧的数据保持有序，但是在实际情况下，j 左侧的部分排序可能也已经排序好了，所以这里引入了x变量，用来记录最后一次i交换的位置，那么x右侧肯定是已经排序好了的，j直接等于x来减少不必要的冒泡，优化性能。
1.3性能
-
时间复杂度
- 最坏情况（数组完全逆序）：
O(n²)需要进行n-1轮排序，每轮进行n-i-1次比较和交换。 - 平均情况：
O(n²)随机分布的数组需要大量比较和交换操作。 - 最好情况（数组已有序）：
O(n)优化版（带交换标记或记录最后交换位置）只需一轮比较即可结束。
- 最坏情况（数组完全逆序）：
-
空间复杂度
O(1)属于原地排序，仅需常数级额外空间用于临时变量交换。
-
稳定性
- 稳定。
- 注：稳定性是值相等的元素在排序后，它们的相对顺序和排序前保持一致。
1.4 适用场景
由于时间复杂度较高，冒泡排序仅适合以下特定场景：
-
教学与学习原理简单直观，是理解「交换排序」和「稳定性」的经典入门算法。
-
对稳定性有要求且数据量极小的场景在必须保证稳定性，同时数据量非常小的情况下，可作为简单选择。
二、选择排序（Selection Sort）
2.1介绍
- 每一轮在未排序区间中找到最小值（或最大值）
- 将其与未排序区间的第一个元素交换位置
- 重复上述步骤，直到整个数组有序
2.2 代码实现
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会不会让排序稳定？
- 稳定排序的关键是：相等元素不发生 “跨位置交换”。拿冒泡排序举例子，如果遇到相等的情况是不会进行交换的，再回到选择排序中，这里假定有多个相等的最大值，那么第一次maxIndex定位到的就是第一个最大值，直接交换到最后面，right进行移动，那么后面的最大值肯定就在当前right左侧了，原来的顺序被打乱了，所以说是不稳定的。
- 那么换成>=有没有用？答案是没用。>=的条件看起来是找到了最后一个最大值再插入来保持原来顺序不变，但是我们来举一个反例：如果有多个最大值并且right也是最大值时，我们找到的就是除了right以外的最后一个最大值，但是如果你再给left < right 换成 left <= right就可以保证稳定了，但是这样性能会相对降低，总的来说大部分选择排序都是不稳定的。
2.3性能
-
时间复杂度
- 平均 / 最坏 / 最好都是 O(n²) — 无论数组是否有序，都需要完整遍历未排序区间。
-
空间复杂度
O(1)属于原地排序，仅需常数级额外空间用于临时变量交换。
-
稳定性
- 不稳定。
2.4 适用场景
- 入门理解排序原理：选择排序的逻辑非常直观（“每次选最值放到对应位置”），是理解排序算法的经典入门案例。
- 元素交换开销大：例如元素是大对象，交换时需要拷贝大量数据。选择排序最多只需要
n-1次交换，比冒泡排序（最多n(n-1)/2次交换）的交换次数少得多。
三、插入排序（Insertion Sort）
3.1介绍
- 初始化：默认数组第一个元素为已排序部分，其余为未排序部分。
- 遍历待插入元素：从第二个元素（i=1）开始，逐个处理未排序部分的元素。
- 查找插入位置：将当前元素（key）与已排序部分从后往前比较，大于 key 则后移，腾出位置。
- 插入元素：找到第一个小于等于 key 的位置，将 key 插入该位置的后一位。
- 重复执行，直至所有元素处理完毕。
3.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;
}
}
}
}
- i是未排序的边界，在i的左侧寻找i应该插入的位置，并且提前记录好a[i]的值，j+1与j之间交换，直到num>=a[j]时就可以插入了。
- 这里我们来注意一下等于的情况越往前面的相等值会越先被插入进相等值的队列中，所以是稳定的。
3.3 性能
-
时间复杂度
- 最佳情况（数组已有序）：O (n)只需遍历一次数组，无需移动任何元素。
- 最坏情况（数组逆序）：O (n²)每个元素都需要移动到最前面，需要进行大量的比较和移动操作。
- 平均情况：O (n²)对于随机排列的数组，时间复杂度仍为平方级。
-
空间复杂度
- 原地排序：O (1)只需要常数级的额外空间，仅用临时变量保存待插入元素。
-
稳定性
- 稳定。
3.4 适用场景
-
小规模数据（n < 50）虽然时间复杂度为 O (n²)，但它的常数项非常小，在数据量很小时，实际运行速度比 O (n log n) 的算法（如快速排序）更快。
-
近乎有序的数据当数组本身已经接近有序时，插入排序的时间复杂度会接近 O (n)，效率远超其他算法。
四、希尔排序（Shell Sort）
4.1 介绍
- 确定增量序列（如 n/2→n/4→…→1）。
- 按当前增量 gap 分组，每组为间隔 gap 的元素。
- 对每组执行插入排序。
- 缩小 gap，重复步骤 2-3。
- 当 gap=1 时，对整个数组执行插入排序，完成排序。
- 希尔排序是插入排序的优化版
4.2 代码实现
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 =0 && num < a[i]){
a[i + gap] = a[i];
i-= gap;
}
if (i != low - gap){
a[i+gap] = num;
}
}
}
}
}
- 这里我们先来介绍一下>>，有符号右移运算符，>>>，无符号运算符，在计算机中，数据由二进制储存，在Java中int是一个32位有符号整数类型，第一位为0时代表正数，第一位为1时代表负数，这个就叫有符号，如果我第一位不用来记录数的正负，那么这就是无符号，>>1就是把除了第一位符号位，把二进制的数据整体右移一位，而>>>1就是把整体直接右移一位，最右边补0。
- 那其实>>的效果和/2是一样的，这里为什么要用>>?其实是因为>>1是 CPU 直接支持的二进制移位操作，理论上比
/2的除法运算更直接，并且我们在许多的程序中把/2 ， *2 替换成左移一位，右移一位，这样也更具备通用性，举个例子，我们在二分查找中就会使用到（i+j）>>>1这个语句，当i和j很大时，就可能会出现两个整数相加之后变成负数的情况（运算过程导致符号位由0变1），这样就会导致算出来的结果有误，/2其实底层逻辑就与>>1一样，所以这里就用到了无符号右移符，但是你最终的结果还是会被当做有符号来处理，这样最终结果就可以保证为正数，不会出现溢出的问题。 - 为什么这里gap每次都要>>1，而不是gap--？
- 首先希尔排序是插入排序的优化版，是把一组数据分成小组，在每组内部进行插入排序，每一次>>1就相当在每组的基础上再次划分更小的组，不会打乱之前已经初步排序的结果，而如果换成--，那么时间复杂度就会比较高了，会打乱之前的排序效果。
- 希尔排序相比于插入排序优化在哪里?
- 相比于插入排序需要每次插入都需要移动很多次，希尔的gap可以减少很多次移动，步长大就可以快速减少数组的逆序对，但是要注意的是，因为希尔是有步长的，所以希尔排序是不稳定的，但是插入排序是稳定的，而且如果提供的数组本来就是有序的，插入排序直接遍历一遍O(n)，但是希尔排序还要进行分组来确定，时间复杂度会略高，所以希尔排序更适合无序度高一点的数组。
4.3 性能
-
时间复杂度
- 最佳情况（数组已有序）：当数组已经完全有序时，希尔排序的效率主要取决于增量序列的长度，O(n log n)。
- 最坏情况：O(n²)。
- 平均情况：O(n log n)。
-
空间复杂度
- 希尔排序是原地排序算法，仅需常数级的额外空间，空间复杂度为 O(1)。
-
稳定性
- 不稳定排序。分组排序时，相同元素可能被分到不同子数组，交换后会改变它们的相对位置。
4.4 适用场景
-
中等规模数据排序（n 在 1000~100,000 之间）它比冒泡、插入、选择排序快得多，且实现比快速、归并排序更简单，常数项更小。
-
需要平衡实现复杂度和性能的场景，如果你不想引入快速排序的递归开销，也不想用归并排序的额外空间，希尔排序是性价比之选。
五、成对插入排序（Pair Insertion Sort）
5.1介绍
- 初始化：先处理数组前两个元素，交换使它们有序，为后续成对处理打基础。
- 成对取元素：从第 3 个元素开始，每次取两个元素作为一组（若数组长度为奇数，最后一个元素单独处理）。
- 组内排序：先比较这两个元素，确保组内较小的在前、较大的在后。
- 逆序插入：先把组内较大的元素向前插入到合适位置，再把较小的元素基于前者的插入位置，向前插入到更靠前的合适位置（复用前者的位置信息，减少比较）。
- 收尾处理：若数组长度为奇数，最后单独的那个元素用普通插入排序插入到对应位置。
5.2 代码实现
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;
}
}
- while中的比较都是>没有加上=，每一次插入都会在相同数值的最后一个，保证了数据排序的稳定。
5.3 性能
-
时间复杂度
-
最坏、平均和最好情况均为
O(n²)，与普通插入排序一致。核心优化在于常数项更小：通过成对处理元素，减少了约一半的比较次数，实际运行速度比普通插入排序快 10%~20%。
-
-
空间复杂度
-
仅需常数级临时变量，为
O(1)，属于原地排序。
-
-
稳定性
-
稳定排序，因为在插入过程中，相等元素的相对位置不会改变。
-
5.4 适用场景
- 小数据集排序（
n < 47）这是它最核心的适用场景。在数据量很小时，O(n²)的复杂度劣势不明显，而常数项的优化能显著提升效率。 -
作为复杂排序算法的子过程常用于归并排序、TimSort 等算法的收尾阶段，当递归拆分出的子数组长度小于阈值时，用它来替代普通插入排序。
六、堆排序（Heap Sort）
6.1介绍
- 堆的定义：堆是一种完全二叉树，用数组存储，满足父节点与子节点的固定大小关系。
- 大顶堆：父节点值≥子节点值，堆顶是最大值（用于升序排序）。
- 小顶堆：父节点值≤子节点值，堆顶是最小值（用于降序排序）。
- 数组与堆的索引关系（0 基索引）
节点类型 索引计算 父节点 子节点索引 i 的父节点：(i - 1)/2（向下取整） 左子节点 父节点索引 i 的左子节点：2i + 1 右子节点 父节点索引 i 的右子节点：2i + 2 - 建堆：无序数组 → 大顶堆（根为最大值）。
- 换顶：堆顶（最大值）与堆尾交换，固定最大值到末尾。
- 调堆：对新堆顶执行下沉，重建大顶堆。
- 循环：重复 “换顶 + 调堆”，直到全有序。
6.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 max){
max = array[right];
maxIndex = right;
}
if (maxIndex != parent){
array[maxIndex] = parentVal;
array[parent] = max;
parent = maxIndex;
} else {
break;
}
}
}
}
- 大顶堆的特性是堆顶的元素是最大的，我们先把一个普通的数组转换为堆的数据结构，也就是建堆，对原数组的每个元素进行遍历，进行下潜操作（将父节点与左右孩子进行比较，如果父节点大于左右孩子，那么已经符合堆的特性了，结束下潜操作，如果左右孩子大于父节点，就让最大的一个与父节点进行交换，再将父节点定位到交换的位子上，继续进行下潜操作）。
- 但是建堆之后的数组不一定是有序的，它仅仅是满足了父节点大于孩子节点，我们知道大顶堆的堆顶是最大的，就可以直接把堆顶与数组最后一个进行交换，并且缩小堆的范围，堆范围以后的就是排序好的，交换过来的数据要进行下潜操作（交换了一个对这个节点进行操作就可以了），符合大顶堆特性之后再不断把堆顶和后面交换，直到排序完毕。
- 堆排序是不稳定的，我们就拿一个数据全部相同的堆来说，建堆时不会进行任何下潜操作，但是开始排序时，会把第一个最大值与最后一个交换，这样就破坏了相同值的相对位置，是不稳定的。
6.3 性能
-
时间复杂度
- 最好、最坏、平均情况均为 O(n log n)，是稳定的时间复杂度。
-
空间复杂度
- 仅需常数级辅助空间，为 O(1)，属于原地排序。
-
稳定性
- 不稳定排序，因为交换堆顶和堆尾时，相同值的元素相对位置可能改变。
6.4 适用场景
-
需要稳定时间复杂度的场景当你不希望遇到最坏情况（如快速排序的 O (n²)），堆排序的 O (n log n) 稳定性是优势。
-
动态获取最值的场景当需要频繁获取当前最大值 / 最小值时（如优先级队列）。
七、归并排序（Merge Sort）
7.1介绍
- 拆分：数组从中间递归拆成两半，直到每个子数组仅 1 个元素（天然有序）；
- 合并：将两个有序子数组，按大小顺序合并为一个有序数组；
- 递归：重复 “拆分→合并”，最终合并为完整有序数组。
7.2代码实现
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);
}
}
}
7.3 性能
-
时间复杂度
-
最好、最坏、平均均为 O(n log n)，性能非常稳定，不会出现快速排序那样的最坏情况。
-
-
空间复杂度
- 需要一个辅助数组，为 O(n)，不是原地排序。
-
稳定性
- 稳定排序，合并时可以保证相同值元素的相对位置不变。
7.4 适用场景
- 外部排序（处理超大文件）当数据量超过内存容量时，归并排序是外部排序的首选算法，适合磁盘大数据的排序。
- 对时间复杂度稳定性要求高的场景它的时间复杂度稳定在 O (n log n)，不会像快速排序那样在某些数据下退化到 O (n²)。
八、归并+插入排序（Merge Insertion Sort）
8.1介绍
- 拆分阶段：递归拆分原数组，但不再拆分到子数组长度为 1。
- 切换条件：当子数组长度小于某个阈值时，停止递归，改用插入排序直接排序该子数组。
- 合并阶段：将这些经过插入排序的有序子数组，按归并排序的方式合并成更大的有序数组。
8.2代码实现
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);
}
}
}
8.3 性能
-
时间复杂度
- 整体仍为
O(n log n)，但通过减少递归深度和常数项，实际运行速度比纯归并排序快 10%~20%。
- 整体仍为
-
空间复杂度
O(n)，和纯归并排序一致，需要一个辅助数组。
-
稳定性
- 稳定排序，因为插入排序和归并排序的合并阶段都保证了相同值元素的相对位置不变。
8.4 适用场景
- 通用业务排序场景这是工业级排序库（如 Java
Arrays.sort()）的核心实现方式，适合绝大多数日常业务开发中的排序需求。 - 对性能有较高要求的场景混合排序结合了两种算法的优势，在处理 “不确定规模” 的数据时，比单一算法表现更稳定。
- 需要稳定排序的场景保留了归并排序的稳定性，适合电商订单、学生成绩等需要保持原始相对位置的场景。
九、快速排序（Quick Sort）
9.1 介绍
- 选基准（Pivot）：从数组中选一个元素作为基准（常见选法：数组首元素、尾元素、中间元素、随机元素）。
- 划分区间：用双指针（左指针
left、右指针right）遍历数组，将小于基准的元素移到左半区，大于基准的移到右半区，基准最终落在 “正确的排序位置”。 - 递归排序：分别对左半区（
left~基准前）和右半区（基准后~right）重复步骤 1-2，直到子数组长度 ≤ 1（天然有序）。
9.2 代码实现
import java.util.concurrent.ThreadLocalRandom;
public class E08_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;
}
}
- 这里的快速排序我们用了三种实现方法，第一种是单边快排，第二种是双边，第三种是优化后的双边快排，接下来逐一介绍。
- 单边快排：
- i指向的是比基准大的，j指向的是比基准小的，这里是有快慢指针的思想的，j移动的比较快，当遇到比基准小并且i!=j的情况，进行交换，那为什么会出现i==j的情况呢？这可能是刚开始排序，前面的数据都小于基准，i，j一起移动，保持相等。
- 当i，j不相等的时候就说明j遇到了大于基准的情况，而i停在了第一个比基准大的数，j移动着去寻找比基准小的数来进行交换。
- 我们来详细拆分一下流程，如果刚开始都是比基准小的数，此时i，j保持相等，注意这里是先比较再移动指针，那么当遇到一个比基准大的数，i，j都是指向这个大数的，那么i就会停在这里不动，让j去移动去寻找小的来交换，所以就是为什么i只在arr[j]时自增。
- 那会不会出现i指向的值是比基准小的导致交换错误？i指向比基准小的情况只会在刚开始都是比基准小的数据的时候发生，并且这个时候i==j也不会进行交换，当i，j遇到了比基准大的，它们就不会再相等了，j始终比i快，i++也不会遇到比基准小的数，因为i到j之间是保证都是比基准大的数，j直到遇到了比基准小的才会停，就算j与i之后没有值，也就是j=i+1，经过交换之后，j的位置就是原本i的值，大于基准，而此时i++，得到的依旧大于基准。
- 最后，由于我们取的基准是right，所以要与比基准大的进行交换，也就是i。
- 优化双边快排：
- 与单边快排的区别是i，j从两边开始遍历，并且对基准的挑选进行了优化，这样对一些边界是最大值最小值的情况进行了优化处理，但是要记得把基准值和left进行交换。
- 而且对判断条件进行了优化，变成了i<=j，和比较的时候不再加上=的比较，这种就针对了有多个相同值的情况了，原来的双边快排，只有j遇到等于的情况是会停下来的，i是不会停的，如果一个数组全部都是相同值，那么就会导致j移动的很少，i移动的很多，我们返回的划分坐标偏右，这样我们下一次分区就会很不平衡，理想上我们的划分应该是中间，这样两个划分出来的数组长度差不多，时间复杂度也可以减少，所以优化后我们不再加上=的比较条件，i和j遇到相等的都会停下来，这样划分也会比较均匀。
- 那为什么要变成i<=j，不加等于会怎么样 ？我们来看一下未优化的版本，arr[j]是一定小于等于基准值的arr[i]是一定是大于基准值的，所以不用考虑两个相等的情况，但是优化后的版本，i和j都可以指向相等的情况了，这就出现了i和j可能相等的情况所以要加上=条件。
9.3 性能
-
时间复杂度
- 平均：(O(n log n))。
- 最好：(O(n log n))。
- 最坏：O(n²)（但因为用了随机选基准，这种情况概率极低）。
-
空间复杂度
- 递归栈深度平均为 (O(log n))，最坏为 (O(n))（可通过尾递归优化进一步降低）。
- 补充一下尾递归是什么
- 尾调用：函数的最后一步是调用一个函数。
- 尾递归：尾调用的特殊情况，函数的最后一步是调用自己。
- 一些语言的编译器（scala ,C++）可以对尾调用做优化，把嵌套的调用转换为并行，前面的函数用完了就可以释放空间了，防止爆栈问题。
-
//非尾调用 int c = 函数（） return c; //非尾调用 return 函数（）+1; //尾调用 return 函数（）;
-
稳定性
- 不稳定。
9.4 适用场景
- 处理中等至大规模的无序数组（平均 (O(n log n)) 效率很高）。
- 数组中存在一定重复元素（双路分区能减少重复元素带来的性能损耗）。
十、计数排序（Counting Sort）
10.1 介绍
- 数次数：先查清每个数字出现了多少次。
- 算位置：根据次数，算出每个数字在最终有序数组里该放的位置。
- 填数组：按位置把数字依次填进新数组，得到有序结果。
10.2 代码实现
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);
}
}
- 这里我们采用了两套实现方法，一个是占用少量额外空间但是不保证稳定，一个是占用多一点点额外空间但保证稳定。
- 第一种更利于理解，就是把里面的数据取出来放到额外的计数数组里面统计，然后再按照计数数组放回去，放回去的时候不依赖原数组，所以也是不稳定的。
- 第二种我们count中存放的有所不同，不再是存放对应元素有几个了，而是对应元素的最后一个索引加1的位置，这就是为什么要给count[i]加上count[i-1]，将数据放回的时候依赖了原数组倒序放回，保证了数据的稳定性，然后再把数组拷贝回去。
10.3 性能
-
时间复杂度
- 最好、最坏、平均情况都是 O(n + k)。
n是待排序元素的数量，k是数据的取值范围（max - min + 1）。- 当
k较小时（如学生成绩 0-100），它是线性时间排序，效率远超快排等基于比较的排序。 - 当
k远大于n时（如排序 100 个范围 0-100000 的数），时间和空间效率会大幅下降。
-
空间复杂度
- 稳定版本：O(n + k)，需要额外的输出数组和计数数组。
- 简化版本（如
sort1）：O(k)，仅需计数数组，原地修改原数组。
-
稳定性
- 标准实现（反向填充 + 累计计数）：稳定。
- 简化实现（正向填充计数数组）：不稳定。
10.4 适用场景
-
数据范围较小的整数排序，如学生成绩（0-100）、年龄（0-150）、考试分数等。
-
byte[]、char[]、short[]这些范围小的也适用。
十一、桶排序（Bucket Sort）
11.1 介绍
- 按数据范围与分布，把待排序元素分到若干个 “桶” 中；
- 对每个桶内的元素单独排序（用任意排序算法均可）；
- 按桶的顺序，依次拼接所有桶的有序元素，得到最终结果。
11.2 代码实现
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 [] buckets = new ArrayList[len];
for (int i = 0 ; i < len ; i++){
buckets[i] = new ArrayList<>();
}
for (int age : a) {
buckets[(age - min)/range].addLast(age);
}
int k = 0;
for (ArrayList bucket : buckets) {
Collections.sort(bucket);
for (Integer num : bucket) {
a[k++] = num;
}
}
}
}
-
跟计数排序的区别的是，计数排序相当于一个数据放在一个桶里面，计数排序适合范围小一点的，而桶排序适合范围稍微大一点的。
11.3 性能
-
时间复杂度
- 平均情况：O(n + k)当数据均匀分布时，每个桶内元素数量相近，桶内排序的总代价较低。
- 最佳情况：Θ(n)数据完美均匀分布，每个桶仅含 1 个元素，无需额外桶内排序。
- 最坏情况：O(n²)所有元素集中在同一个桶中，退化为桶内排序算法的时间复杂度（如插入排序）。
-
空间复杂度
- O(n + k)需要额外的空间存储
k个桶和所有元素。- 桶里存放了所有的元素，也就是O（n）再加上k个桶。
- O(n + k)需要额外的空间存储
-
稳定
- 基于桶内排序选择。
11.4 适用场景
- 数据值域较大但分布规律可以通过映射函数将元素均匀分配到桶中。
- 对性能要求较高平均时间复杂度接近线性，在适合场景下比比较型排序更快。
十二、基数排序（Radix Sort）
12.1 介绍
- 从字符串的最低有效位 开始，向第一位（高位）逐位处理；
- 每一轮按当前处理数字，将字符串分配到对应数字的桶中；
- 按桶的顺序（0 到 9）收集所有字符串，完成当前位排序，重复直到所有位处理完毕。
12.2 代码实现
import java.util.ArrayList;
public class RadixSort {
public static void sort(String[] a , int range){
ArrayList[] 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 bucket : buckets) {
for (String string : bucket) {
a[k++] = string;
}
bucket.clear();
}
}
}
}
-
注意基数排序是从最低有效位开始比较的，先保证低位的有序性，这样高位排序就不会破坏低位的有序性。
-
当有些数字过长时，超过int的最大范围时，可以用基数排序来比较，比如电话号码。
12.3 性能
-
时间复杂度
-
最好 / 最坏 / 平均时间复杂度均为
O(d * (n + k))（无数据分布依赖，是稳定的线性时间排序）。 d：待排序数据的位数 / 字符位数（如 11 位手机号的d=11，32 位整数的d=32）。n：待排序数据的数量。k：基数（十进制数k=10，二进制k=2，字符串k=26/256）。
-
-
空间复杂度
- 基数排序是非原地排序，空间复杂度为
O(n + k)： - 需要额外的桶 / 计数数组（大小
k）； - 需要临时数组存储每一轮排序的结果（大小
n）；- 这里的n我们指的是桶的总容量，这些桶相当于一个临时数组暂时存放元素。
- 相比原地排序的快速排序（
O(logn)递归栈）、堆排序（O(1)），基数排序的空间开销更大。
- 基数排序是非原地排序，空间复杂度为
-
稳定性
- 基数排序必须基于稳定排序（计数 / 桶排序）实现，因此它本身是稳定排序（相等元素相对位置不变），这也是它能从低位到高位排序的核心前提。
12.4 适用场景
-
固定长度的数值型数据排序
- 场景：手机号、身份证号、银行卡号、邮编、固定长度整数（如订单编号）；
- 原因：这类数据位数
d固定，基数k小（十进制k=10），能充分发挥O(n)的线性优势，且稳定排序可保留相同前缀数据的相对顺序。
-
大规模数据的外部排序（磁盘排序）
- 场景：数据量远超内存（如 100G 日志中的手机号排序）；
- 原因：基数排序按位分桶，可将数据分批加载到内存处理（每一轮仅处理一位），减少磁盘 I/O 次数；而快速排序 / 归并排序需要频繁内存 - 磁盘交互。
十三、算法复杂度与特性总结
| 排序算法 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|---|
| 冒泡排序 | 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) | 稳定 | 整数 / 字符串数组、大规模数据 |
十四、JDK 7~13 中的排序实现
| 排序目标 | 条件 | 采用算法 |
|---|---|---|
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 |
14.1 int[] long[] float[] double[]
-
小数据集（size < 47）→ 混合插入排序（pair）
- 插入排序的时间复杂度是
O(n²)，但在数据量极小时，其常数项（比较、交换次数）远低于快排、归并排序。 - “pair”（成对插入排序）是对普通插入排序的优化，通过成对处理元素减少约一半的比较次数，在小数据集上效率更高。
- 插入排序的时间复杂度是
-
中等数据集（47 ≤ size < 286）→ 双基准点快排
- 双基准点快排的平均时间复杂度为
O(n log n)，且在均匀分布数据上的性能优于单轴快排。 - 中等规模数据下，快排的
O(n log n)复杂度优势开始显现，同时其常数项开销也能被接受。
- 双基准点快排的平均时间复杂度为
-
大数据集（size ≥ 286）
- 有序度低 → 双基准点快排：快排的随机化基准选择能避免最坏情况，在无序数据上效率稳定。
- 有序度高 → 归并排序：归并排序在处理接近有序的数据时，时间复杂度接近
O(n)，且能避免快排在有序数据下退化为O(n²)的风险。 - 有序度是怎么判断的？
-
排在处理大数据集时，会通过扫描数组统计 “天然有序段（Run）” 的特征来判断有序度。
- 扫描统计：遍历数组，统计连续递增 / 递减子序列（Run）的数量和平均长度。
- 阈值触发：如果扫描发现数组中存在大量长度较长的有序子序列（平均 Run 长度超过预设阈值），则判定为 “有序度高”，并切换为归并排序。
- 核心目的：避免双基准点快排在面对高度有序数据时，因基准选择不佳而导致的性能退化，同时利用归并排序在有序数据上的高效性。
-
14.2 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)效率高得多。
- 计数排序：时间复杂度是
-
从常数项开销看
- 计数排序：不需要元素间的比较和交换，仅通过计数和复制就能完成排序，常数项开销非常低。
- 双基准点快排：需要频繁的比较、交换和递归，常数项开销比计数排序大。
-
从稳定性看
- 计数排序：是稳定排序，能保证相等元素的相对顺序不变，这对业务场景中的多字段排序很重要。
- 双基准点快排：是不稳定排序，无法保证相等元素的相对顺序。
- 对于
14.3 char[] short[]
- 情况和int[]等差不多，这里不再赘述。
size > 3200→ 计数排序char的取值范围是0~65535，short的取值范围是-32768~32767，当数据量超过 3200 时，计数排序的O(n + k)线性复杂度（k≈65536）效率会超过快排的O(n log n)，成为更优选择。
14.4 Object[]
- 默认使用 TimSort 的原因
- 性能优势：TimSort 是一种混合稳定排序（本质上是归并+插入），它能利用数组中天然存在的有序片段（Run），在接近有序的数据上表现出 O (n) 的最优时间复杂度，整体性能远优于传统归并排序。
- 稳定性需求：对
Object[]排序时，稳定性是一个重要特性（比如排序对象时保留相等元素的原始顺序），而 TimSort 是稳定排序，满足这一需求（快速排序并不稳定）。
- 兼容性兜底：在 Java 7 之前，
Arrays.sort(Object[])使用的是传统归并排序。为了保证旧代码在升级后行为完全一致，Java 提供了系统属性-Djava.util.Arrays.useLegacyMergeSort=true作为降级开关。
十五、JDK 14~24 中的排序实现
| 排序目标 | 条件 | 采用算法 |
|---|---|---|
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 |
15.1 int[] long[] float[] double[]
- 我们先来解释一下什么叫位于最左侧，快速排序中会涉及到分区递归的这样一个操作，就有左侧右侧之分。
- 小数据集（size < 44 并位于最左侧）→ 插入排序
- 把最左侧的小片段（
size < 44）单独划分出来，直接用插入排序。这是因为最左侧的数组片段在缓存中更容易被连续访问，插入排序的局部性优势能被最大化。 - 为什么不用混合插入排序 (pin)？
-
当片段位于数组最左侧时，它几乎 100% 已经在 CPU 的 L1/L2 缓存中。普通插入排序的内存访问模式是连续的，能完美利用缓存的局部性。
- PIN 会先对片段进行预扫描和分块，这本身就有一定的初始化开销。对于极小的片段（比如
size < 44），这些额外开销的占比会变得很高，甚至超过它带来的收益。
-
- 把最左侧的小片段（
- 大数据集（递归次数 > 384）→ 堆排序
- 我们在介绍快速排序的时候介绍了一下尾递归，当我们在调用快速排序的时候，调用一个函数就会入栈，当它去递归时，又会有函数入栈，所以当我们调用的函数未出栈，自身的函数始终处于栈的下面，空间无法释放，而此时我们的java语言又无法做尾递归的优化，随着递归次数的增加，会出现爆栈问题。
- 为什么使用堆排序？
- 稳定的时间复杂度：堆排序的时间复杂度在任何情况下都是
O(n log n)，这刚好可以用来兜底快排最坏情况下的O(n²)性能问题。 - 原地排序，无额外空间：堆排序是原地排序算法，仅需常数级别的额外空间（
O(1)），这一点比需要O(n)额外空间的归并排序更有优势。 - 归并排序：虽然时间复杂度稳定，但它需要
O(n)的额外空间来存储临时数据，在处理大数组时会带来明显的内存开销。 - 插入排序 / PIN：这类算法仅在小规模数据下高效，对于触发递归阈值的大数据量场景，时间复杂度会退化为
O(n²)，性能完全无法接受。 - TimSort：它是稳定排序且性能优异，但仅适用于
Object[]，无法直接用于基础类型数组（如int[]、long[]），且同样需要额外空间。
- 稳定的时间复杂度：堆排序的时间复杂度在任何情况下都是
15.2 byte[]
- 为什么阈值从29调整到64？
- 对于
byte[]这种单字节数据，CPU 可以更高效地处理连续内存访问，缓存命中率也更高，这让插入排序在size <= 64的范围内，实际执行速度依然快于计数排序。
- 对于
14.3 char[] short[]
为什么放弃了有序性的判断?- 要检测数组的有序度，需要先遍历整个数组，这会带来
O(n)的时间开销。对于char[]和short[]这类基础类型数组，这个额外的遍历成本，在很多场景下已经超过了 “选择更优算法” 带来的收益。尤其是在数据量较大时，O(n)的检测开销会直接拖累整体性能。 -
计数排序成为更优的兜底选择,
char[]和short[]的取值范围有限（char是 0~65535，short是 -32768~32767），非常适合用计数排序。计数排序的时间复杂度是O(n + k)（k为取值范围），在数据量较大时（比如size > 1750），它的效率远超归并排序或快排。
- 要检测数组的有序度，需要先遍历整个数组，这会带来
- 为什么int这类的数组还有有序性的判断？
int、long、float、double的取值范围极大，远超过char/short/byte，无法用计数排序兜底。
