十大经典排序算法（Java 实现）

一、速查表

算法	平均	最坏	最好	空间	稳定
冒泡	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^1.3)	—	—	O(1)	❌
快排	O(n log n)	O(n²)	O(n log n)	O(log n)	❌
归并	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(1)	❌
计数	O(n+k)	O(n+k)	O(n+k)	O(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)	✅

二、快速排序

void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = partition(a, lo, hi);
    quickSort(a, lo, pivot - 1);
    quickSort(a, pivot + 1, hi);
}

int partition(int[] a, int lo, int hi) {
    int p = a[lo];
    int i = lo, j = hi;
    while (i < j) {
        while (i < j && a[j] >= p) j--;
        while (i < j && a[i] <= p) i++;
        swap(a, i, j);
    }
    swap(a, lo, i);
    return i;
}

优化：随机选 pivot、小数组用插入排序。

三、归并排序

void mergeSort(int[] a, int lo, int hi, int[] tmp) {
    if (lo >= hi) return;
    int mid = (lo + hi) >>> 1;
    mergeSort(a, lo, mid, tmp);
    mergeSort(a, mid + 1, hi, tmp);
    merge(a, lo, mid, hi, tmp);
}

稳定，外部排序常用。

四、堆排序

建大顶堆，堆顶与末尾交换，调整堆。

• 原地排序，不稳定。
• 适合 TopK。

五、Java 内置排序

• Arrays.sort(int[])：基本类型用双轴快排。
• Arrays.sort(Object[])：对象用 TimSort（归并 + 插入）。
• Collections.sort：同上。

面试加分

• 什么是稳定？相等元素排序后相对顺序不变。
• 为什么快排平均最快？常数小、缓存友好。