排序算法全解析：实现、对比与时间复杂度
·
排序算法全解析：实现、对比与时间复杂度
从冒泡到快排，一文看懂 10 种经典排序算法
引言
排序算法是计算机科学中最基础、最重要的算法类别之一。无论你是准备面试、优化代码，还是理解底层原理，掌握排序算法都是必经之路。
本文将以 统一结构 —— 思路 + 代码实现 + 复杂度分析 + 稳定性 + 适用场景 —— 逐一讲解 10 种经典排序算法。
第一章：算法总览
1.1 分类
| 分类 | 算法 |
|---|---|
| O(n²) 基础排序 | 冒泡排序、选择排序、插入排序 |
| O(n log n) 高效排序 | 归并排序、快速排序、堆排序 |
| O(n) 线性排序 | 计数排序、桶排序、基数排序 |
| 其他 | 希尔排序、鸡尾酒排序、梳排序 |
1.2 稳定性
- 稳定：相等元素的相对顺序保持不变（冒泡、插入、归并、计数、桶、基数）
- 不稳定：相等元素的相对顺序可能改变（选择、快速、堆、希尔）
1.3 复杂度速查表
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | 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^1.3) | O(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²) | O(log 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+k) | O(n²) | O(n+k) | ✅ |
| 基数排序 | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | ✅ |
第二章：O(n²) 基础排序
2.1 冒泡排序（Bubble Sort）
思路
重复遍历数组，每次比较相邻元素，将较大的"冒泡"到末尾。
可视化
[5, 3, 8, 1, 9]
↓ ↓
[3, 5, 8, 1, 9] ← 5 和 3 交换
↓ ↓
[3, 5, 8, 1, 9] ← 5 和 8 不换
↓ ↓
[3, 5, 1, 8, 9] ← 8 和 1 交换
↓ ↓
[3, 5, 1, 8, 9] ← 8 和 9 不换
最大元素 9 已到位
代码实现
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
// 如果没有交换，说明已经有序
if (!swapped) break;
}
return arr;
}
// 示例
console.log(bubbleSort([5, 3, 8, 1, 9])); // [1, 3, 5, 8, 9]
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
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(n²) | 两重循环 |
| 最坏 | O(n²) | 完全逆序 |
- 空间：O(1)，原地排序
- 稳定：✅ 相等元素不交换
适用场景
- 数据量小（n < 1000）
- 教学演示
- 几乎有序的数据（优化后效率较高）
2.2 选择排序（Selection Sort）
思路
每次从未排序部分选出最小元素，放到已排序部分的末尾。
可视化
[5, 3, 8, 1, 9]
选出最小值 1，与第一位交换
[1, 3, 8, 5, 9]
从剩余部分选出最小值 3（已在第二位）
[1, 3, 8, 5, 9]
从剩余部分选出最小值 5，与第三位交换
[1, 3, 5, 8, 9]
继续...
[1, 3, 5, 8, 9]
代码实现
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx !== i) {
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
}
return arr;
}
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
复杂度分析
| 情况 | 时间复杂度 |
|---|---|
| 最好 | O(n²) |
| 平均 | O(n²) |
| 最坏 | O(n²) |
- 空间：O(1)
- 稳定：❌ 不稳定（交换可能破坏稳定性）
适用场景
- 数据量小
- 对稳定性无要求
- 交换成本高于比较成本时（选择排序交换次数最少）
2.3 插入排序（Insertion Sort）
思路
将元素逐个插入到已排序部分的正确位置，就像打扑克牌理牌。
可视化
[5, 3, 8, 1, 9]
将 3 插入到 [5] 中
[3, 5, 8, 1, 9]
将 8 插入到 [3, 5] 中
[3, 5, 8, 1, 9]
将 1 插入到 [3, 5, 8] 中
[1, 3, 5, 8, 9]
将 9 插入到 [1, 3, 5, 8] 中
[1, 3, 5, 8, 9]
代码实现
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好 | O(n) | 已有序，只需比较 n-1 次 |
| 平均 | O(n²) | 约 n²/4 次比较 |
| 最坏 | O(n²) | 完全逆序 |
- 空间：O(1)
- 稳定：✅ 插入时相等元素不移动
适用场景
- 数据量小（n < 1000）
- 数据几乎有序（此时效率接近 O(n)）
- 作为高级排序算法（如快排）的底层优化
第三章：O(n log n) 高效排序
3.1 归并排序（Merge Sort）
思路
分治思想：将数组分成两半，分别排序，再合并。
[5, 3, 8, 1, 9, 6]
│
▼ 分割
[5, 3, 8] [1, 9, 6]
│ │
▼ ▼
[5, 3] [8] [1, 9] [6]
│ │ │ │
▼ ▼ ▼ ▼
[3,5] [8] [1,9] [6]
│ │
▼ ▼
[3,5,8] [1,6,9]
│
▼ 合并
[1, 3, 5, 6, 8, 9]
代码实现
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
// 处理剩余元素
while (i < left.length) result.push(left[i++]);
while (j < right.length) result.push(right[j++]);
return result;
}
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
原地归并（空间优化）
function mergeSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
const mid = Math.floor((left + right) / 2);
mergeSortInPlace(arr, left, mid);
mergeSortInPlace(arr, mid + 1, right);
mergeInPlace(arr, left, mid, right);
}
function mergeInPlace(arr, left, mid, right) {
const temp = [];
let i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp.push(arr[i++]);
} else {
temp.push(arr[j++]);
}
}
while (i <= mid) temp.push(arr[i++]);
while (j <= right) temp.push(arr[j++]);
for (let k = 0; k < temp.length; k++) {
arr[left + k] = temp[k];
}
}
复杂度分析
| 情况 | 时间复杂度 |
|---|---|
| 最好 | O(n log n) |
| 平均 | O(n log n) |
| 最坏 | O(n log n) |
- 空间：O(n)（额外数组）
- 稳定：✅
适用场景
- 数据量大
- 要求稳定性（如按多个字段排序）
- 链表排序（归并排序对链表非常友好）
- 外部排序（处理无法全部装入内存的数据）
3.2 快速排序（Quick Sort）
思路
分治思想：选择一个基准（pivot），将小于基准的放左边，大于基准的放右边，递归排序左右。
可视化
[5, 3, 8, 1, 9, 6] 基准 = 5
↓ 分区
[3, 1, 5, 8, 9, 6]
左侧 [3,1] 右侧 [8,9,6]
↓ ↓
[1,3] [6,8,9]
│ │
└──────┬─────┘
[1, 3, 5, 6, 8, 9]
代码实现（Lomuto 分区）
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
return arr;
}
// Lomuto 分区方案（选择最后一个元素作为基准）
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort(arr, low, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
Hoare 分区（效率更高）
function partitionHoare(arr, low, high) {
const pivot = arr[Math.floor((low + high) / 2)];
let i = low - 1;
let j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot);
do { j--; } while (arr[j] > pivot);
if (i >= j) return j;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
优化：三数取中
function medianOfThree(arr, low, high) {
const mid = Math.floor((low + high) / 2);
// 将三个数排序，使 arr[mid] 为中位数
if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
if (arr[low] > arr[high]) [arr[low], arr[high]] = [arr[high], arr[low]];
if (arr[mid] > arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]];
// 将中位数放到 high-1 位置（避免参与分区）
[arr[mid], arr[high - 1]] = [arr[high - 1], arr[mid]];
return arr[high - 1];
}
复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好 | O(n log n) | 基准每次都在中间 |
| 平均 | O(n log n) | 随机数据下表现优异 |
| 最坏 | O(n²) | 基准总是最大/最小（如已有序） |
- 空间：O(log n)（递归栈）
- 稳定：❌ 不稳定
适用场景
- 数据量大（通常比归并排序快 2-3 倍）
- 对稳定性无要求
- 随机数据（教科书最优）
- 需要原地排序
3.3 堆排序（Heap Sort）
思路
利用堆（完全二叉树）数据结构：建立最大堆，每次取出堆顶（最大值），放到数组末尾。
可视化
[5, 3, 8, 1, 9, 6]
│
▼ 建堆
9
/ \
6 8
/ \ /
1 3 5
│
▼ 交换堆顶与末尾
[9, 6, 8, 1, 3, 5]
↓ 交换
[5, 6, 8, 1, 3, 9]
↓ 堆化
[8, 6, 5, 1, 3, 9]
↓ 继续...
[1, 3, 5, 6, 8, 9]
代码实现
function heapSort(arr) {
const n = arr.length;
// 1. 建堆（从最后一个非叶子节点开始）
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 2. 排序：将堆顶依次移到末尾
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, n, i) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}
def heap_sort(arr):
n = len(arr)
# 建堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 排序
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
复杂度分析
| 情况 | 时间复杂度 |
|---|---|
| 最好 | O(n log n) |
| 平均 | O(n log n) |
| 最坏 | O(n log n) |
- 空间：O(1)（原地排序）
- 稳定：❌ 不稳定
适用场景
- 数据量大
- 需要 O(n log n) 时间复杂度 + O(1) 空间复杂度
- 不适合链式数据结构（堆需要随机访问）
- 优先队列场景
第四章：O(n) 线性排序
4.1 计数排序（Counting Sort）
思路
统计每个值出现的次数，然后根据计数重建有序数组。
限制： 仅适用于非负整数且范围不大的场景。
可视化
arr = [4, 2, 2, 8, 3, 3, 1]
计数: 值: 0 1 2 3 4 5 6 7 8
次数: 0 1 2 2 1 0 0 0 1
前缀和: 值: 0 1 2 3 4 5 6 7 8
累加:0 1 3 5 6 6 6 6 7
重建: 原数组反向遍历
4 → 位置 6-1=5
2 → 位置 3-1=2
...
结果: [1, 2, 2, 3, 3, 4, 8]
代码实现
function countingSort(arr) {
if (arr.length <= 1) return arr;
// 1. 找到最大值和最小值
let min = arr[0], max = arr[0];
for (let val of arr) {
if (val < min) min = val;
if (val > max) max = val;
}
const range = max - min + 1;
const count = new Array(range).fill(0);
// 2. 计数
for (let val of arr) {
count[val - min]++;
}
// 3. 前缀和
for (let i = 1; i < range; i++) {
count[i] += count[i - 1];
}
// 4. 重建（稳定排序）
const result = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) {
const val = arr[i];
const idx = count[val - min] - 1;
result[idx] = val;
count[val - min]--;
}
return result;
}
def counting_sort(arr):
if len(arr) <= 1:
return arr
min_val, max_val = min(arr), max(arr)
range_val = max_val - min_val + 1
count = [0] * range_val
for val in arr:
count[val - min_val] += 1
for i in range(1, range_val):
count[i] += count[i - 1]
result = [0] * len(arr)
for val in reversed(arr):
idx = count[val - min_val] - 1
result[idx] = val
count[val - min_val] -= 1
return result
复杂度分析
| 情况 | 时间复杂度 |
|---|---|
| 全部 | O(n + k) |
其中 k = 数据范围（max - min + 1）
- 空间：O(k)
- 稳定：✅
适用场景
- 数据范围较小（k 远小于 n）
- 数据是整数（或可以映射为整数）
- 需要线性时间复杂度
4.2 桶排序（Bucket Sort）
思路
将数据分到有限数量的桶中，每个桶单独排序，最后合并。
可视化
arr = [0.42, 0.32, 0.78, 0.51, 0.19, 0.88]
桶 0 (0-0.2): [0.19]
桶 1 (0.2-0.4): [0.32, 0.42]
桶 2 (0.4-0.6): [0.51]
桶 3 (0.6-0.8): [0.78]
桶 4 (0.8-1.0): [0.88]
每个桶内排序 → 合并
[0.19, 0.32, 0.42, 0.51, 0.78, 0.88]
代码实现
function bucketSort(arr, bucketSize = 5) {
if (arr.length <= 1) return arr;
let min = arr[0], max = arr[0];
for (let val of arr) {
if (val < min) min = val;
if (val > max) max = val;
}
// 计算桶数量
const bucketCount = Math.floor((max - min) / bucketSize) + 1;
const buckets = Array.from({ length: bucketCount }, () => []);
// 分桶
for (let val of arr) {
const idx = Math.floor((val - min) / bucketSize);
buckets[idx].push(val);
}
// 每个桶排序（使用插入排序）
const result = [];
for (let bucket of buckets) {
insertionSort(bucket);
result.push(...bucket);
}
return result;
}
// 插入排序（用于桶内排序）
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
def bucket_sort(arr, bucket_size=5):
if len(arr) <= 1:
return arr
min_val, max_val = min(arr), max(arr)
bucket_count = (max_val - min_val) // bucket_size + 1
buckets = [[] for _ in range(bucket_count)]
for val in arr:
idx = (val - min_val) // bucket_size
buckets[idx].append(val)
result = []
for bucket in buckets:
insertion_sort(bucket)
result.extend(bucket)
return result
复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好 | O(n + k) | 数据均匀分布 |
| 平均 | O(n + k) | 每个桶数据量小 |
| 最坏 | O(n²) | 所有数据进同一个桶 |
- 空间：O(n + k)
- 稳定：✅（取决于桶内排序算法）
适用场景
- 数据均匀分布（如 0-1 之间的浮点数）
- 大数据集，可以分桶处理
- 外部排序场景
4.3 基数排序（Radix Sort）
思路
按位排序：从最低位（个位）到最高位，依次使用稳定排序（如计数排序）。
可视化
arr = [170, 45, 75, 90, 802, 24, 2, 66]
按个位排序:
[170, 90, 802, 2, 24, 45, 75, 66]
按十位排序:
[802, 2, 24, 45, 66, 170, 75, 90]
按百位排序:
[2, 24, 45, 66, 75, 90, 170, 802]
结果: [2, 24, 45, 66, 75, 90, 170, 802]
代码实现
function radixSort(arr) {
if (arr.length <= 1) return arr;
// 1. 找到最大值，确定位数
let maxVal = Math.max(...arr);
let maxDigits = String(maxVal).length;
// 2. 从个位到最高位依次排序
for (let digit = 0; digit < maxDigits; digit++) {
arr = countingSortByDigit(arr, digit);
}
return arr;
}
function countingSortByDigit(arr, digit) {
const radix = 10;
const count = new Array(radix).fill(0);
// 计算当前位的值
const getDigit = (num) => {
return Math.floor(Math.abs(num) / Math.pow(10, digit)) % 10;
};
// 计数
for (let val of arr) {
const d = getDigit(val);
count[d]++;
}
// 前缀和
for (let i = 1; i < radix; i++) {
count[i] += count[i - 1];
}
// 重建（稳定排序）
const result = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) {
const val = arr[i];
const d = getDigit(val);
const idx = count[d] - 1;
result[idx] = val;
count[d]--;
}
return result;
}
// 处理负数
function radixSortWithNegative(arr) {
if (arr.length <= 1) return arr;
// 分离负数和正数
const negatives = arr.filter(x => x < 0).map(x => -x);
const positives = arr.filter(x => x >= 0);
// 分别排序后合并
const sortedNeg = radixSort(negatives).map(x => -x).reverse();
const sortedPos = radixSort(positives);
return [...sortedNeg, ...sortedPos];
}
def radix_sort(arr):
if len(arr) <= 1:
return arr
max_val = max(arr)
max_digits = len(str(max_val))
for digit in range(max_digits):
arr = counting_sort_by_digit(arr, digit)
return arr
def counting_sort_by_digit(arr, digit):
radix = 10
count = [0] * radix
def get_digit(num):
return (num // (10 ** digit)) % 10
for val in arr:
count[get_digit(val)] += 1
for i in range(1, radix):
count[i] += count[i - 1]
result = [0] * len(arr)
for val in reversed(arr):
d = get_digit(val)
idx = count[d] - 1
result[idx] = val
count[d] -= 1
return result
复杂度分析
| 情况 | 时间复杂度 |
|---|---|
| 全部 | O(d × (n + k)) |
其中：
-
d = 最大位数
-
k = 基数（通常为 10）
-
空间：O(n + k)
-
稳定：✅
适用场景
- 整数排序（或字符串）
- 位数相对较少
- 需要线性时间复杂度
第五章：其他排序算法
5.1 希尔排序（Shell Sort）
思路
插入排序的改进版：通过增量分组，使数据逐步"基本有序"。
function shellSort(arr) {
const n = arr.length;
// 增量序列（Knuth 序列）
let gap = 1;
while (gap < n / 3) {
gap = gap * 3 + 1;
}
while (gap >= 1) {
for (let i = gap; i < n; i++) {
let temp = arr[i];
let j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap = Math.floor(gap / 3);
}
return arr;
}
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好 | O(n log n) | 较优增量序列 |
| 平均 | O(n^1.3) | 经验值 |
| 最坏 | O(n²) | 某些增量序列 |
- 空间：O(1)
- 稳定：❌
5.2 鸡尾酒排序（Cocktail Shaker Sort）
思路
冒泡排序的双向版本：从左到右冒泡最大，再从右到左冒泡最小。
function cocktailSort(arr) {
let start = 0;
let end = arr.length - 1;
let swapped = true;
while (swapped) {
swapped = false;
// 从左到右（冒泡最大）
for (let i = start; i < end; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
swapped = true;
}
}
end--;
if (!swapped) break;
// 从右到左（冒泡最小）
for (let i = end; i > start; i--) {
if (arr[i] < arr[i - 1]) {
[arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
swapped = true;
}
}
start++;
}
return arr;
}
- 时间复杂度：O(n²)
- 空间：O(1)
- 稳定：✅
5.3 梳排序（Comb Sort）
思路
冒泡排序的改进：使用递减的间隙，消除小值在末尾的"乌龟效应"。
function combSort(arr) {
const n = arr.length;
let gap = n;
let shrink = 1.3;
let sorted = false;
while (!sorted) {
gap = Math.floor(gap / shrink);
if (gap <= 1) {
gap = 1;
sorted = true;
}
for (let i = 0; i + gap < n; i++) {
if (arr[i] > arr[i + gap]) {
[arr[i], arr[i + gap]] = [arr[i + gap], arr[i]];
sorted = false;
}
}
}
return arr;
}
- 时间复杂度：O(n²) 最坏，O(n log n) 平均
- 空间：O(1)
- 稳定：❌
第六章：算法对比与选择指南
6.1 性能对比（n = 10000，随机数据，单位 ms）
| 算法 | 平均耗时 | 相对速度 |
|---|---|---|
| 快速排序 | ~5ms | 1x（基准） |
| 归并排序 | ~8ms | 1.6x |
| 堆排序 | ~12ms | 2.4x |
| 希尔排序 | ~15ms | 3x |
| 插入排序 | ~250ms | 50x |
| 选择排序 | ~400ms | 80x |
| 冒泡排序 | ~500ms | 100x |
6.2 选择指南
数据量 < 50
├── 插入排序（代码简单）
└── 选择排序（交换少）
数据量 50 ~ 1000
├── 插入排序（数据几乎有序）
├── 希尔排序（通用）
└── 快速排序（推荐）
数据量 > 1000
├── 快速排序（随机数据，最快）
├── 归并排序（需要稳定性）
├── 堆排序（空间受限）
└── 计数/桶/基数（整数，范围小）
特定场景
├── 数据几乎有序 → 插入排序
├── 数据范围小（整数）→ 计数排序
├── 数据均匀分布 → 桶排序
├── 固定位数整数 → 基数排序
├── 链表 → 归并排序
└── 需要实时性 → 快速排序（平均最快）
6.3 算法特性对比
| 特性 | 冒泡 | 选择 | 插入 | 希尔 | 归并 | 快速 | 堆 | 计数 | 桶 | 基数 |
|---|---|---|---|---|---|---|---|---|---|---|
| 最好 | O(n) | O(n²) | O(n) | O(n log n) | O(n log n) | O(n log n) | O(n log n) | O(n+k) | O(n+k) | O(d(n+k)) |
| 平均 | O(n²) | O(n²) | O(n²) | O(n^1.3) | O(n log n) | O(n log n) | O(n log n) | O(n+k) | O(n+k) | O(d(n+k)) |
| 最坏 | O(n²) | O(n²) | O(n²) | O(n²) | O(n log n) | O(n²) | O(n log n) | O(n+k) | O(n²) | O(d(n+k)) |
| 空间 | O(1) | O(1) | O(1) | O(1) | O(n) | O(log n) | O(1) | O(k) | O(n+k) | O(n+k) |
| 稳定 | ✅ | ❌ | ✅ | ❌ | ✅ | ❌ | ❌ | ✅ | ✅ | ✅ |
| 原地 | ✅ | ✅ | ✅ | ✅ | ❌ | ✅ | ✅ | ❌ | ❌ | ❌ |
| 适用数据 | 小 | 小 | 小/有序 | 中 | 大 | 大 | 大 | 整数 | 均匀 | 整数/字符串 |
第七章：实战面试题
Q1：为什么快速排序比归并排序快？
- 缓存友好：快排原地操作，归并需要额外数组
- 常数因子：快排的常数因子更小
- 分治策略：快排先分区再递归；归并先递归再合并
Q2：什么时候用插入排序而不是快排？
- 数据量 < 50
- 数据几乎有序（此时插入排序接近 O(n)）
- 作为快排的优化（小数组回退到插入排序）
Q3：如何优化快速排序？
- 三数取中（避免最坏情况）
- 小数组使用插入排序
- 尾递归优化
- 随机化基准
Q4：排序算法稳定性有什么用？
按多个字段排序时：
// 先按年龄排序，再按姓名排序（保持年龄顺序）
// 稳定排序保证同年龄的人仍然按姓名顺序排列
Q5：哪些排序算法可以处理百万级数据？
- 快排（内存充足）
- 归并排序（外部排序版本）
- 桶排序（数据均匀分布时）
第八章：总结
核心记忆
O(n²)：冒泡、选择、插入（简单但慢）
O(n log n)：归并、快排、堆（高效通用）
O(n)：计数、桶、基数（线性但有限制）
时间换空间 vs 空间换时间：
- 快排：时间最优，空间一般
- 归并：时间稳定，空间大
- 堆排：空间最优，时间稳定
学习建议
- 掌握核心 3 种：快排、归并、插入
- 理解分治思想：快排、归并
- 理解线性排序的局限性：计数、桶、基数
- 面试高频：快排、归并、堆排、计数
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
2
0- 0
已为社区贡献3条内容
所有评论(0)