1. 简单排序（基础、效率低，适合少量数据）

1. 冒泡排序 BubbleSort
2. 选择排序 SelectSort
3. 插入排序 InsertSort

2. 进阶高效排序（工程常用）

1. 希尔排序 ShellSort（插入优化）
2. 快速排序 QuickSort（实际开发最常用）
3. 归并排序 MergeSort（稳定，适合大数据 / 外部排序）

3. 堆排序 HeapSort（基于堆结构）

1. 堆排序 HeapSort

4. 非比较排序（速度极快，有数值范围限制）

1. 计数排序 CountSort

---

前置统一工具方法

所有示例共用打印数组方法，简化代码：

java

运行

public class SortDemo {
    // 打印数组
    public static void printArr(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2, 7, 1, 6};
        // 此处替换对应排序方法
    }
}

一、冒泡排序 Bubble Sort

通俗理解

像水里气泡往上浮：相邻两个数字两两对比，左边 > 右边就交换，一轮结束最大值沉到末尾；多轮循环，每轮少比较末尾已排好的数字。

特点

• 稳定排序（相等数字相对位置不变）
• 时间复杂度：最坏 O (n²)，最好 O (n)（优化后有序数组一次遍历）
• 适合：数据量很小的场景

java

运行

// 冒泡排序（带优化：有序直接退出）
public static void bubbleSort(int[] arr) {
    int len = arr.length;
    // 外层控制轮数，一共 len-1 轮
    for (int i = 0; i < len - 1; i++) {
        boolean isSorted = true; // 标记本轮是否发生交换
        // 每轮比较到 len-1-i，后面i个已经排好
        for (int j = 0; j < len - 1 - i; j++) {
            // 左边比右边大，交换
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSorted = false;
            }
        }
        // 本轮无交换，说明数组完全有序，直接结束
        if (isSorted) break;
    }
}

调用测试：

java

运行

int[] arr = {5, 3, 8, 4, 2, 7, 1, 6};
bubbleSort(arr);
printArr(arr); // 输出：1 2 3 4 5 6 7 8

二、选择排序 Select Sort

通俗理解

遍历数组找到最小值下标，和当前最左边未排序位置交换；一轮确定一个最小值放前面。

特点

• 不稳定排序
• 时间复杂度固定 O (n²)，无论有序与否都要完整遍历
• 交换次数比冒泡少，但整体依然很慢

java

运行

public static void selectSort(int[] arr) {
    int len = arr.length;
    // i：当前待填充的最小值位置
    for (int i = 0; i < len - 1; i++) {
        int minIndex = i; // 先假设当前i是最小值下标
        // 从i+1往后找真正最小值
        for (int j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换最小值到i位置
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

三、插入排序 Insert Sort

通俗理解

打扑克牌：左手是有序牌，右手拿一张新牌，从后往前对比，插入到合适位置。 数组分为：左边有序区、右边无序区，逐个把无序数字插入有序区。

特点

• 稳定排序
• 数组越接近有序，速度越快；几乎有序数据效率极高
• 时间复杂度最坏 O (n²)，最好 O (n)

java

运行

public static void insertSort(int[] arr) {
    int len = arr.length;
    // 从第二个元素开始（第一个默认有序）
    for (int i = 1; i < len; i++) {
        int temp = arr[i]; // 待插入数字
        int j;
        // 从i-1向前遍历有序区，比temp大就后移
        for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
            arr[j + 1] = arr[j];
        }
        // 腾出的空位放入temp
        arr[j + 1] = temp;
    }
}

四、希尔排序 Shell Sort（插入排序优化版）

通俗理解

插入排序每次只相邻对比，移动成本高；希尔先按间隔 gap分组组内插入排序，逐步缩小 gap 直到 gap=1（普通插入）。 先远距离粗调，再精细微调，大幅减少元素移动次数。

特点

• 不稳定排序
• 效率远高于普通插入，中等数据量表现不错

java

运行

public static void shellSort(int[] arr) {
    int len = arr.length;
    // 初始间隔为长度一半，每次减半
    for (int gap = len / 2; gap > 0; gap /= 2) {
        // 组内插入排序，逻辑和插入排序一致，步长gap
        for (int i = gap; i < len; i++) {
            int temp = arr[i];
            int j;
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
        }
    }
}

五、快速排序 Quick Sort（工程最常用）

通俗理解

分治思想：选一个基准值 pivot，把数组分成两部分：左边全部 ≤ pivot，右边全部 ≥ pivot；再递归排序左右两部分。

特点

• 不稳定排序
• 平均时间复杂度 O (n log n)，绝大多数场景最快
• 最坏 O (n²)（完全有序数组，可通过随机基准优化）
• JDK Arrays.sort () 基础类型底层就是双轴快排

java

运行

// 快排入口
public static void quickSort(int[] arr) {
    quick(arr, 0, arr.length - 1);
}

// 递归处理 [left, right] 区间
private static void quick(int[] arr, int left, int right) {
    if (left >= right) return; // 区间只有一个数，无需排序
    int l = left;
    int r = right;
    int pivot = arr[l]; // 选最左为基准

    while (l < r) {
        // 右指针向左找小于pivot的数
        while (l < r && arr[r] >= pivot) r--;
        arr[l] = arr[r]; // 填到左指针空位

        // 左指针向右找大于pivot的数
        while (l < r && arr[l] <= pivot) l++;
        arr[r] = arr[l]; // 填到右指针空位
    }
    arr[l] = pivot; // 基准归位，l是分割点
    // 递归左区间
    quick(arr, left, l - 1);
    // 递归右区间
    quick(arr, l + 1, right);
}

六、归并排序 Merge Sort

通俗理解

分治：先把数组不断对半拆分，拆到单个元素天然有序；再两两合并有序数组，一层一层合并直到完整数组。

特点

• 稳定排序（唯一稳定的 O (n log n) 排序）
• 时间复杂度稳定 O (n log n)，无最坏情况
• 需要额外辅助数组，占用内存大；适合海量文件外部排序

java

运行

// 归排入口
public static void mergeSort(int[] arr) {
    int[] temp = new int[arr.length]; // 辅助数组，避免反复创建
    merge(arr, 0, arr.length - 1, temp);
}

// 拆分区间
private static void merge(int[] arr, int left, int right, int[] temp) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    merge(arr, left, mid, temp); // 左半拆分
    merge(arr, mid + 1, right, temp); // 右半拆分
    mergeTwo(arr, left, mid, right, temp); // 合并两个有序区间
}

// 合并 [left,mid] 和 [mid+1,right] 两个有序数组
private static void mergeTwo(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left;   // 左数组起点
    int j = mid + 1;// 右数组起点
    int t = 0;      // temp数组指针

    // 两边同时遍历，取较小值放入temp
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t++] = arr[i++];
        } else {
            temp[t++] = arr[j++];
        }
    }
    // 剩余左边元素放入temp
    while (i <= mid) temp[t++] = arr[i++];
    // 剩余右边元素放入temp
    while (j <= right) temp[t++] = arr[j++];

    // 将temp有序数据拷贝回原数组
    t = 0;
    while (left <= right) arr[left++] = temp[t++];
}

七、堆排序 Heap Sort

通俗理解

基于大顶堆（父节点 ≥ 左右子节点）：

1. 把数组构建成大顶堆，堆顶是最大值；
2. 堆顶和末尾元素交换，最大值固定到数组尾部；
3. 剩余未排序部分重新调整为大顶堆，重复操作。

特点

• 不稳定排序
• 时间复杂度稳定 O (n log n)，内存占用比归并小

java

运行

public static void heapSort(int[] arr) {
    int len = arr.length;
    // 1. 构建大顶堆，从最后一个非叶子节点倒序遍历
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
    // 2. 堆顶和末尾交换，逐步固定最大值
    for (int i = len - 1; i > 0; i--) {
        // 交换堆顶最大值和末尾
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        // 剩余数组重新调整堆
        adjustHeap(arr, 0, i);
    }
}

// 调整以i为根的堆，len是当前堆有效长度
private static void adjustHeap(int[] arr, int i, int len) {
    int parent = arr[i]; // 父节点值
    // 左子节点下标
    for (int left = 2 * i + 1; left < len; left = 2 * left + 1) {
        // 右子节点存在且更大，切换到右子节点
        if (left + 1 < len && arr[left] < arr[left + 1]) {
            left++;
        }
        // 子节点大于父节点，交换
        if (arr[left] > parent) {
            arr[i] = arr[left];
            i = left;
        } else {
            break;
        }
    }
    arr[i] = parent; // 父节点放到最终正确位置
}

八、计数排序 Count Sort（非比较排序）

通俗理解

不比较大小，利用数字本身做下标：

1. 找到数组最大值，创建计数数组；
2. 统计每个数字出现次数；
3. 按计数顺序回填原数组。

特点

• 速度极快 O (n+k)，k 是数值范围
• 只能排整数，数值跨度极大时浪费内存

java

运行

public static void countSort(int[] arr) {
    if (arr.length == 0) return;
    // 找到最大值确定计数数组长度
    int max = arr[0];
    for (int num : arr) {
        if (num > max) max = num;
    }
    int[] countArr = new int[max + 1];

    // 统计每个数字出现次数
    for (int num : arr) {
        countArr[num]++;
    }
    // 按顺序回填原数组
    int index = 0;
    for (int i = 0; i < countArr.length; i++) {
        while (countArr[i] > 0) {
            arr[index++] = i;
            countArr[i]--;
        }
    }
}

九、排序算法核心对比总结

表格

排序	平均复杂度	稳定性	额外空间	适用场景
冒泡	O(n²)	稳定	O(1)	极小数据、教学
选择	O(n²)	不稳定	O(1)	几乎不用
插入	O(n²)	稳定	O(1)	接近有序小数组
希尔	O(n^1.3)	不稳定	O(1)	中等少量数据
快速	O(n logn)	不稳定	O(logn)	日常开发首选
归并	O(n logn)	稳定	O(n)	需要稳定排序、外部文件排序
堆排序	O(n logn)	不稳定	O(1)	内存有限、不要求稳定
计数排序	O(n+k)	稳定	O(k)	整数、数值范围小

补充开发实用提示

1. Java 内置排序：Arrays.sort()
   • byte/short/int/long 基础类型：双轴快速排序
   • 对象引用类型：TimSort（归并 + 插入结合，稳定）
2. 千万级大数据优先归并；内存紧张选堆排；常规业务数组直接用快排。