def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 提前退出标志：若本轮无交换，说明已有序
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

选择排序：每次选“最小值”放前

原理：每轮从未排序部分选出最小值，放到已排序部分末尾。

时间复杂度：始终O(n²)
空间复杂度：O(1)
稳定性：不稳定（交换可能打乱相等元素顺序）

? 关键洞察：选择排序交换次数最少（最多n-1次），适合写入成本高的场景（如闪存）。

代码示例（Java）

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // 交换：可能破坏稳定性
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

避坑指南

某金融系统用选择排序处理交易记录，结果相同时间戳的订单顺序被破坏，导致对账失败。修复方案：改用稳定排序，或在比较时加入原索引作为第二关键字。

插入排序：像整理扑克牌一样排序

原理：将数组分为“已排序”和“未排序”两部分，每次从未排序部分取元素，插入到已排序部分的合适位置。

时间复杂度：最优O(n)（已有序），平均/最坏O(n²)
空间复杂度：O(1)
稳定性：稳定

适用场景：小规模数据、近乎有序数据（如日志按时间戳追加）、作为其他算法的子过程（如TimSort）

代码示例（JavaScript）

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        // 将 key 插入到 arr[0..i-1] 中
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

网友实战案例

“在Vue项目中，用插入排序实时排序用户输入的关键词列表（平均长度20），性能远超内置sort——因为数据始终近乎有序！”（@前端小张）

快速排序：分治法的典范

原理：选基准（pivot），分区（将小于基准的放左，大于的放右），递归处理左右子数组。

时间复杂度：平均O(n log n)，最坏O(n²)
空间复杂度：O(log n)（递归栈）
稳定性：不稳定

⚠️ 致命弱点：当数据已有序或大量重复时，退化为O(n²)。解决方法：

• 随机选基准（Randomized QuickSort）
• 数取中（Median-of-Three）：取首、中、尾三个数的中位数作为基准
• 路快排（处理大量重复值）

代码示例（Python）

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 中位数基准
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

网友热议

“面试问‘快排为什么快’？答：缓存友好！它顺序访问数据，CPU预取效率高——比归并排序的随机访问更省时间。”（@算法工程师李工）

归并排序：稳定高效的分治策略

原理：递归地将数组分为两半，分别排序后合并（merge）。

时间复杂度：始终O(n log n)
空间复杂度：O(n)（需额外数组）
稳定性：稳定

适用场景：需要稳定性的场景、链表排序（空间O(1)）、外部排序（大数据文件）

代码示例（Java）

public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; // 等号保证稳定性
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    System.arraycopy(temp, 0, arr, left, temp.length);
}

网友案例

“在处理10GB日志文件时，用归并排序实现外部排序：分块读入内存排序后写回磁盘，再多路归并——这是唯一能处理超大数据的排序方案。”（@大数据工程师）

堆排序：利用堆的性质实现选择排序

原理：构建最大堆（或最小堆）， repeatedly取堆顶（最大/最小值）放入结果数组。

时间复杂度：O(n log n)
空间复杂度：O(1)
稳定性：不稳定

? 核心优势：时间复杂度稳定，且原地排序；适合需要“动态取前K大/小”的场景（如TopK问题）。

代码示例（Python）

import heapq
def heap_sort(arr):
    # 转为最大堆（Python heapq是小顶堆，取反实现）
    max_heap = [-x for x in arr]
    heapq.heapify(max_heap)
    return [-heapq.heappop(max_heap) for _ in range(len(max_heap))]

网友讨论

“堆排序在LeetCode TopK问题中胜出：不需要完全排序，只需维护大小为K的堆，时间O(n log K)。”（@算法刷题党）

计数排序：用空间换时间的整数排序

原理：统计每个值出现次数，通过累加计数确定元素位置。

时间复杂度：O(n + k)（k为数据范围）
空间复杂度：O(k)
稳定性：稳定（可改进为稳定版）

适用场景：数据范围较小的整数（如成绩、年龄、IP地址段）

代码示例（Java）

public static int[] countingSort(int[] arr, int maxVal) {
    int[] count = new int[maxVal + 1];
    int[] output = new int[arr.length];
    // 计数
    for (int num : arr) count[num]++;
    // 累加计数（保证稳定性）
    for (int i = 1; i <= maxVal; i++) count[i] += count[i-1];
    // 反向填充（保持稳定性）
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    return output;
}

网友实测

“排序100万条0~100分的成绩，计数排序耗时0.03秒，快排0.15秒——当k << n时，计数排序碾压其他算法！”（@教育科技公司）

基数排序：按位拆分的稳定排序

原理：从最低位开始，依次按每位数字排序（通常用计数排序作为子过程）。

时间复杂度：O(d(n + k))（d为位数）
空间复杂度：O(n + k)
稳定性：稳定

适用场景：固定长度字符串（如身份证号、手机号）、整数（需转为字符串）

代码示例（Python）

def radix_sort(arr):
    if not arr: return arr
    max_num = max(arr)
    exp = 1  # 个位开始
    while max_num // exp > 0:
        # 用计数排序按当前位排序
        counting_sort_by_digit(arr, exp)
        exp = 10
    return arr
def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0]  n
    count = [0]  10
    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1
    for i in range(1, 10):
        count[i] += count[i-1]
    for i in range(n-1, -1, -1):
        digit = (arr[i] // exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
    for i in range(n):
        arr[i] = output[i]

网友案例

“在数据库索引优化中，对10亿条手机号排序，基数排序比快排快3倍——因为数据范围固定、位数一致！”（@后端架构师）