排序算法是程序员的基本功，也是面试高频考点。无论是简单的插入排序，还是高效的快速排序、归并排序，理解其核心逻辑与实现细节，能帮我们在实际开发中精准选择合适的排序方案。本文将结合完整的 Java 代码，拆解 11 种经典排序算法的原理、实现、优化与适用场景，带你从 “会用” 到 “吃透” 排序逻辑。

一、排序算法基础认知

在正式讲解算法前，先明确几个核心概念，方便后续对比分析：

• 稳定性：排序后，相同值元素的相对位置是否保持不变（如[2,1,1,3]排序后，两个 1 的顺序是否与原数组一致）。
• 时间复杂度：算法执行时间随数据规模增长的趋势，通常分析最坏、平均和最好情况。
• 空间复杂度：算法执行过程中额外占用的存储空间（不包含原数组本身的存储）。
• 原地排序：是否仅通过 O (1) 额外空间完成排序，无需依赖额外数组或数据结构。

二、核心排序算法详解（附 Java 实现）

本文所有算法均封装在Sort类中，包含完整的排序方法、辅助函数（如swap交换元素），可直接复制到 IDE 中运行测试。

1. 插入排序（Insertion Sort）：简单直观的 “整理扑克牌”

核心思想

类比整理扑克牌：从第二个元素开始，将当前元素插入到前面已排好序的序列中，通过相邻交换调整位置，直到整个数组有序。

实现代码

public void insertionSort(int[] arr) {
    // 从第2个元素（索引1）开始遍历，前面的元素视为已排序
    for (int i = 1; i < arr.length; i++) {
        // 向前比较，找到当前元素的正确位置
        for (int j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                swap(arr, j, j - 1); // 比前一个元素小则交换
            }
        }
    }
}

// 辅助函数：交换数组中两个元素
private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

性能与场景

• 时间复杂度：O (n²)（最坏 / 平均），O (n)（最好，数组已有序）。
• 空间复杂度：O (1)（原地排序）。
• 稳定性：稳定（仅交换相邻元素，相同值不改变相对位置）。
• 适用场景：小规模数据（n≤1000）或接近有序的数据（如数据库查询结果局部排序）。

2. 希尔排序（Shell Sort）：插入排序的 “加速版”

核心思想

插入排序的优化版：通过分组插入排序减少比较和交换次数。先按 “间隔 gap” 将数组分成多个子数组，对每个子数组做插入排序；逐渐缩小 gap（通常每次除以 2），直到 gap=1，此时数组已接近有序，最后做一次插入排序即可。

实现代码

public void ShellSort(int[] arr) {
    int gap = arr.length; // 初始间隔为数组长度
    while (gap > 1) {
        gap /= 2; // 间隔每次减半
        // 对每个分组进行插入排序
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i]; // 暂存当前元素
            int j = i - gap; // 向前找同组的前一个元素
            // 同组内向前比较，比temp大则后移
            while (j >= 0 && arr[j] > temp) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = temp; // 插入temp到正确位置
        }
    }
}

性能与场景

• 时间复杂度：取决于 gap 序列，平均 O (n^1.3)，最坏 O (n²)（gap=1 时退化为插入排序）。
• 空间复杂度：O (1)（原地排序）。
• 稳定性：不稳定（分组交换可能打破相同值的相对位置）。
• 适用场景：中等规模数据（n≤10000），比插入排序效率提升明显。

3. 选择排序（Selection Sort）：“每次选最小”

核心思想

分 “已排序” 和 “未排序” 区间，每次从待排序区间找到最小元素，放到已排序区间的末尾；本文额外实现双向选择排序（同时找最小和最大元素），进一步减少遍历次数。

实现代码

基础版：每次选最小元素

public void selectionSort(int[] arr) {
    // 已排序区间的末尾索引（i从0开始）
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i; // 记录最小元素的索引
        // 遍历待排序区间，找最小元素
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        swap(arr, i, minIndex); // 将最小元素放到已排序区间末尾
    }
}

优化版：双向选择（同时找最小和最大）

public void newselectionSort(int[] arr) {
    int left = 0; // 已排序区间左边界
    int right = arr.length - 1; // 已排序区间右边界
    while (left < right) {
        int maxIndex = left; // 最大元素索引
        int minIndex = left; // 最小元素索引
        // 遍历当前待排序区间[left, right]
        for (int i = left + 1; i <= right; i++) {
            if (arr[i] < arr[minIndex]) minIndex = i;
            if (arr[i] > arr[maxIndex]) maxIndex = i;
        }
        swap(arr, left, minIndex); // 最小元素放到左边界
        // 注意：若最大元素在左边界，交换后已到minIndex位置
        if (maxIndex == left) maxIndex = minIndex;
        swap(arr, maxIndex, right); // 最大元素放到右边界
        left++;
        right--;
    }
}

性能与场景

• 时间复杂度：O (n²)（最坏 / 平均 / 最好，均需遍历找最值）。
• 空间复杂度：O (1)（原地排序）。
• 稳定性：不稳定（如[3,2,2]，第一次交换后两个 2 的相对位置改变）。
• 适用场景：数据规模小，或需减少交换次数的场景（选择排序交换次数仅 O (n)）。

4. 堆排序（Heap Sort）：利用 “大根堆” 特性

核心思想

基于大根堆（根元素是最大值）的排序：

1. 构建大根堆：从最后一个非叶子节点开始，对每个节点做 “向下调整”，确保堆特性。
2. 提取最大值：每次将根元素（最大值）与堆的最后一个元素交换，缩小堆范围，对新根做向下调整。
3. 重复步骤 2，直到堆为空，数组即有序。

实现代码

public void heapSort(int[] arr) {
    // 1. 构建大根堆：从最后一个非叶子节点开始向下调整
    for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
        siftDown(arr, i, arr.length);
    }
    // 2. 逐步提取最大值，调整堆
    int end = arr.length - 1;
    while (end > 0) {
        swap(arr, 0, end); // 根（最大值）与最后一个元素交换
        siftDown(arr, 0, end); // 对新根向下调整，堆范围缩小为[0, end-1]
        end--;
    }
}

// 辅助函数：向下调整（维持大根堆）
private void siftDown(int[] arr, int parent, int end) {
    int child = 2 * parent + 1; // 左孩子索引
    while (child < end) {
        // 若右孩子存在且比左孩子大，选择右孩子
        if (child + 1 < end && arr[child] < arr[child + 1]) {
            child++;
        }
        // 若孩子比父节点大，交换并继续向下调整
        if (arr[child] > arr[parent]) {
            swap(arr, child, parent);
            parent = child;
            child = 2 * parent + 1;
        } else {
            break; // 父节点比孩子大，调整完成
        }
    }
}

性能与场景

• 时间复杂度：O (n log n)（建堆 O (n)，调整堆 O (n log n)）。
• 空间复杂度：O (1)（原地排序）。
• 稳定性：不稳定（交换根与末尾元素可能打破相同值相对位置）。
• 适用场景：需要 O (n log n) 时间且不允许额外空间的场景（如大数据量内存排序）。

5. 冒泡排序（Bubble Sort）：“大的往后冒”

核心思想

“两两比较，大的往后冒”：每次遍历数组，相邻元素两两比较，前大后小则交换；每轮遍历后，最大元素会 “冒” 到数组末尾。通过标志位优化，可在数组已有序时提前退出。

实现代码

public void bubbleSort(int[] arr) {
    // 外层循环：控制遍历轮数（最多n-1轮）
    for (int i = 0; i < arr.length - 1; i++) {
        boolean isSorted = false; // 标志位：是否已有序
        // 内层循环：遍历未排序区间（每轮后末尾i个元素已有序）
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                isSorted = true; // 发生交换，说明数组未完全有序
            }
        }
        if (!isSorted) break; // 未发生交换，提前退出
    }
}

性能与场景

• 时间复杂度：O (n²)（最坏 / 平均），O (n)（最好，标志位触发提前退出）。
• 空间复杂度：O (1)（原地排序）。
• 稳定性：稳定（仅交换相邻元素，相同值不交换）。
• 适用场景：教学场景（理解排序思想）或极小规模数据，实际开发中很少使用（效率低）。

6. 快速排序（Quick Sort）：分治法的 “性能王者”

核心思想

分治法经典实现：

1. 选一个 “基准值”（pivot）。
2. 分区（partition）：将数组分为两部分，左部分＜基准值，右部分＞基准值，基准值放到最终位置。
3. 递归对左右两部分重复步骤 1-2，直到子数组长度为 1。

本文实现递归版（含优化）和非递归版（栈实现），并提供 3 种分区方式：双指针法、挖坑法、Hoare 法。

实现代码

1. 递归版（含两大优化）

// 对外接口：触发快速排序
public void quickSort(int[] arr) {
    quick(arr, 0, arr.length - 1);
}

// 递归核心方法
private void quick(int[] arr, int left, int right) {
    if (left >= right) return; // 子数组长度≤1，直接返回

    // 优化1：小规模子数组（长度≤5）用插入排序（减少递归开销）
    if (right - left <= 5) {
        InsertSortRange(arr, left, right);
        return;
    }

    // 优化2：三数取中（选left、mid、right的中间值做基准，避免有序数组退化）
    // int midIndex = getMiddleNumber(arr, left, right);
    // swap(arr, left, midIndex); // 基准值放到left位置

    // 分区：获取基准值的最终位置（三种分区方式可选）
    int pivot = partitionPointer(arr, left, right); // 双指针法
    // int pivot = partition(arr, left, right); // 挖坑法
    // int pivot = partitionHoare(arr, left, right); // Hoare法

    // 递归排序左分区和右分区
    quick(arr, left, pivot - 1);
    quick(arr, pivot + 1, right);
}

// 辅助1：小规模子数组的插入排序
private void InsertSortRange(int[] arr, int start, int end) {
    for (int i = start + 1; i <= end; i++) {
        for (int j = i; j > start; j--) {
            if (arr[j] < arr[j - 1]) {
                swap(arr, j, j - 1);
            }
        }
    }
}

// 辅助2：三数取中（获取基准值索引）
private int getMiddleNumber(int[] arr, int left, int right) {
    int mid = (left + right) / 2;
    // 比较left、mid、right，返回中间值的索引
    if (arr[left] < arr[right]) {
        if (arr[mid] > arr[right]) return right;
        else if (arr[mid] < arr[left]) return left;
        else return mid;
    } else {
        if (arr[mid] < arr[right]) return right;
        else if (arr[mid] > arr[left]) return left;
        else return mid;
    }
}

2. 三种分区方式

// 分区1：双指针法（推荐，易理解、效率高）
private int partitionPointer(int[] arr, int left, int right) {
    int pivotVal = arr[left]; // 基准值（left位置）
    int pre = left; // 已处理区间的右边界（小于基准值的最后一个元素）
    int cur = left + 1; // 当前遍历元素

    while (cur <= right) {
        // 若当前元素小于基准值，pre后移并交换
        if (arr[cur] < pivotVal && arr[++pre] != arr[cur]) {
            swap(arr, pre, cur);
        }
        cur++;
    }
    swap(arr, pre, left); // 基准值放到pre位置（最终位置）
    return pre;
}

// 分区2：挖坑法
private int partition(int[] arr, int left, int right) {
    int pivotVal = arr[left]; // 基准值，left位置形成“坑”
    while (left < right) {
        // 从右向左找小于基准值的元素，填入左坑
        while (left < right && arr[right] >= pivotVal) right--;
        arr[left] = arr[right]; // 右元素填入左坑，right形成新坑
        // 从左向右找大于基准值的元素，填入右坑
        while (left < right && arr[left] <= pivotVal) left++;
        arr[right] = arr[left]; // 左元素填入右坑，left形成新坑
    }
    arr[left] = pivotVal; // 基准值填入最后一个坑
    return left;
}

// 分区3：Hoare法（快速排序原始分区方式）
private int partitionHoare(int[] arr, int left, int right) {
    int pivotVal = arr[left]; // 基准值
    int pivotIndex = left; // 基准值原始索引

    while (left < right) {
        // 从右向左找小于基准值的元素
        while (left < right && arr[right] >= pivotVal) right--;
        // 从左向右找大于基准值的元素
        while (left < right && arr[left] <= pivotVal) left++;
        swap(arr, left, right); // 交换两个元素
    }
    swap(arr, pivotIndex, left); // 基准值放到最终位置
    return left;
}

3. 非递归版（栈实现，避免递归栈溢出）

// 非递归版：用栈存储待排序区间的左右边界
public void quickNor(int[] arr, int start, int end) {
    Deque<Integer> stack = new LinkedList<>();
    quickNumPush(arr, start, end, stack); // 初始区间压栈

    while (!stack.isEmpty()) {
        // 栈是LIFO，先压左再压右，弹出时先右后左
        end = stack.pop();
        start = stack.pop();
        quickNumPush(arr, start, end, stack); // 分区并压入新区间
    }
}

// 辅助：分区并将非空区间压栈
private void quickNumPush(int[] arr, int start, int end, Deque<Integer> stack) {
    int pivot = partition(arr, start, end);
    if (pivot > start + 1) { // 左区间非空
        stack.push(start);
        stack.push(pivot - 1);
    }
    if (pivot < end - 1) { // 右区间非空
        stack.push(pivot + 1);
        stack.push(end);
    }
}

性能与场景

• 时间复杂度：O (n log n)（平均），O (n²)（最坏，数组有序时），O (n log n)（最好）。
• 空间复杂度：O (log n)（递归栈）或 O (n)（最坏）；非递归版 O (log n)（栈存储区间）。
• 稳定性：不稳定（分区交换可能打破相同值相对位置）。
• 适用场景：大规模数据（n≥10000），是实际开发中最常用的排序算法之一（如 JDK 的Arrays.sort()对基本类型使用快速排序）。

7. 归并排序（Merge Sort）：稳定的 “分治代表”

核心思想

分治法的另一种实现，核心是 “先分后合”：

1. 分：将数组递归分成两个子数组，直到子数组长度为 1。
2. 合：将两个有序子数组合并成一个有序数组，重复此过程直到合并为完整数组。

本文实现递归版和非递归版，解决递归栈溢出问题。

实现代码

1. 递归版

// 对外接口：触发归并排序
public void mergeSort(int[] arr) {
    mergeSortTmp(arr, 0, arr.length - 1);
}

// 递归拆分数组
private void mergeSortTmp(int[] arr, int left, int right) {
    if (left == right) return; // 子数组长度为1，直接返回
    int mid = (left + right) / 2; // 中间索引
    mergeSortTmp(arr, left, mid); // 拆分左子数组
    mergeSortTmp(arr, mid + 1, right); // 拆分右子数组
    merge(arr, left, mid, right); // 合并两个有序子数组
}

// 核心：合并两个有序子数组[left, mid]和[mid+1, right]
private void merge(int[] arr, int left, int mid, int right) {
    int s1 = left, s2 = mid + 1; // 两个子数组的起始索引
    int e1 = mid, e2 = right; // 两个子数组的结束索引
    int k = 0;
    int[] temp = new int[right - left + 1]; // 临时数组存储合并结果

    // 比较两个子数组元素，按序放入临时数组
    while (s1 <= e1 && s2 <= e2) {
        if (arr[s1] < arr[s2]) {
            temp[k++] = arr[s1++];
        } else {
            temp[k++] = arr[s2++];
        }
    }

    // 处理剩余元素（左子数组未遍历完）
    while (s1 <= e1) temp[k++] = arr[s1++];
    // 处理剩余元素（右子数组未遍历完）
    while (s2 <= e2) temp[k++] = arr[s2++];

    // 将临时数组结果复制回原数组
    for (int i = 0; i < k; i++) {
        arr[left + i] = temp[i];
    }
}

2. 非递归版（迭代实现）

public void mergeSortNoR(int[] arr) {
    int gap = 1; // 初始子数组长度为1（有序）
    while (gap < arr.length) {
        // 每次合并两个长度为gap的子数组
        for (int i = 0; i < arr.length; i += gap * 2) {
            int left = i;
            int mid = left + gap - 1;
            // 处理边界：若mid超出数组长度，调整为最后一个索引
            if (mid >= arr.length) mid = arr.length - 1;
            int right = mid + gap;
            // 处理边界：若right超出数组长度，调整为最后一个索引
            if (right >= arr.length) right = arr.length - 1;
            merge(arr, left, mid, right); // 合并子数组
        }
        gap *= 2; // 子数组长度翻倍
    }
}

性能与场景

• 时间复杂度：O (n log n)（最坏 / 平均 / 最好，拆分和合并均为 O (n log n)）。
• 空间复杂度：O (n)（临时数组存储合并结果）。
• 稳定性：稳定（合并时相同值按原顺序放入临时数组）。
• 适用场景：需要稳定排序的大规模数据（如电商订单按 “价格 + 时间” 排序），或外部排序（数据存放在磁盘，需分块处理）。

8. 计数排序（Count Sort）：非比较排序的 “速度黑马”

核心思想

非比较排序，基于 “统计频率” 实现：

1. 找出数组的最小值和最大值，确定统计数组的长度（max - min + 1）。
2. 统计每个元素出现的频率，存入统计数组。
3. 根据统计数组的频率，将元素按序放回原数组。

实现代码

public void countSort(int[] arr) {
    if (arr.length == 0) return;

    // 1. 找出数组的最小值和最大值
    int minV = arr[0];
    int maxV = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < minV) minV = arr[i];
        if (arr[i] > maxV) maxV = arr[i];
    }

    // 2. 初始化统计数组，统计每个元素的频率
    int len = maxV - minV + 1;
    int[] count = new int[len];
    for (int i = 0; i < arr.length; i++) {
        int index = arr[i] - minV; // 映射到统计数组的索引（避免负索引）
        count[index]++;
    }

    // 3. 根据频率将元素放回原数组
    int j = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] != 0) {
            arr[j] = i + minV; // 恢复原元素值
            count[i]--;
            j++;
        }
    }
}

性能与场景

• 时间复杂度：O (n + k)（n 为数组长度，k 为 max - min + 1）。
• 空间复杂度：O (k)（统计数组的空间）。
• 稳定性：可稳定（需额外处理相同值的顺序）。
• 适用场景：元素值范围小的整数数组（如学生成绩、年龄排序），或作为基数排序的子排序。

三、11 种排序算法性能对比

排序算法	时间复杂度（平均）	时间复杂度（最坏）	空间复杂度	稳定性	原地排序	适用场景
插入排序	O(n²)	O(n²)	O(1)	稳定	是	小规模 / 接近有序数据
希尔排序	O(n^1.3)	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²)	O(log n)	不稳定	是	大规模数据，追求效率
快速排序（非递归）	O(n log n)	O(n²)	O(log n)	不稳定	是	大规模数据，避免递归溢出
归并排序（递归）	O(n log n)	O(n log n)	O(n)	稳定	否	大规模数据，需稳定排序
归并排序（非递归）	O(n log n)	O(n log n)	O(n)	稳定	否	大规模数据，避免递归溢出
堆排序	O(n log n)	O(n log n)	O(1)	不稳定	是	大规模数据，不允许额外空间
计数排序	O(n + k)	O(n + k)	O(k)	可稳定	否	元素范围小的整数数组

四、总结与实践建议

1. 小规模数据（n≤1000）：优先选择插入排序（接近有序时）或选择排序（交换成本高时）。
2. 中等规模数据（1000＜n≤10000）：希尔排序效率优于简单排序，且无需额外空间。
3. 大规模数据（n≥10000）：
   • 无需稳定排序：快速排序（平均效率最高）或堆排序（无额外空间）。
   • 需要稳定排序：归并排序。
4. 特殊场景：
   • 元素值范围小：计数排序（速度最快）。
   • 外部排序（数据存磁盘）：归并排序（分块处理友好）。

掌握这些排序算法的核心逻辑，不仅能应对面试中的算法题，更能在实际开发中根据数据特点选择最优方案，写出高效、优雅的代码。建议大家将文中代码复制到 IDE 中运行测试，通过调试逐步理解每一步的执行过程，真正将排序算法内化为自己的技能。