排序全家桶:从入门到面试实战_spring全家桶面试题
排序全家桶：从入门到面试实战
1. 全局导图
- o 排序算法家族图谱
- o 复杂度 / 稳定性 / 是否原地 总览
术语速记：
o 稳定性：相等元素相对次序是否保持。o 原地：额外空间 O(1)（或近似如快排递归栈 O(log n)）。o 比较类：复杂度下界 Ω(n log n)；非比较类（计数/桶/基数）可在范围/位数受限时优于 n log n。
2. 入门三件套：冒泡 / 选择 / 插入
2.1 冒泡排序（Bubble Sort）
思路：相邻比较，大的“冒”到右边；每一轮把一个最大值放到末尾。
配图：
# 语言：Python — 冒泡（稳定，原地）
def bubble_sort(a: list[int]) -> None:
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(0, n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped: # 已有序，提前结束
break// 语言：Swift — 冒泡（稳定，原地）
func bubbleSort(_ arr: inout [Int]) {
guard arr.count > 1 else { return }
for i in 0..<(arr.count-1) {
var swapped = false
for j in 0..<(arr.count-1-i) {
if arr[j] > arr[j+1] { arr.swapAt(j, j+1); swapped = true }
}
if !swapped { break }
}
}2.2 选择排序（Selection Sort）
思路：每轮选择最小值放到有序区末（位置 i），一轮只做一次交换。不稳定但原地。
# 语言：Python — 选择（不稳定，原地）
def selection_sort(a: list[int]) -> None:
n = len(a)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j
if min_idx != i:
a[i], a[min_idx] = a[min_idx], a[i]// 语言：Swift — 选择（不稳定，原地）
func selectionSort(_ arr: inout [Int]) {
for i in 0..<arr.count {
var p = i
for j in (i+1)..<arr.count { if arr[j] < arr[p] { p = j } }
if p != i { arr.swapAt(i, p) }
}
}2.3 插入排序（Insertion Sort）
思路：维持已排序前缀，把当前元素向左移动到合适位置。稳定、原地。
配图：
# 语言：Python — 插入（稳定，原地）
def insertion_sort(a: list[int]) -> None:
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key// 语言：Swift — 插入（稳定，原地）
func insertionSort(_ arr: inout [Int]) {
for i in 1..<arr.count {
let key = arr[i]
var j = i - 1
while j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j -= 1
}
arr[j+1] = key
}
}3. 面试三巨头：归并 / 快排 / 堆排
3.1 归并排序（Merge Sort）
思路：分治 + 归并两段有序数组。稳定，但非原地（需要 O(n) 额外空间）。
配图：
# 语言：Python — 归并（稳定，O(n) 额外空间）
def merge_sort(a: list[int]) -> list[int]:
if len(a) <= 1: return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
# 归并两个有序数组
i = j = 0; res = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i]); i += 1
else:
res.append(right[j]); j += 1
res.extend(left[i:]); res.extend(right[j:])
return res// 语言：Swift — 归并（稳定，O(n) 额外空间）
func mergeSort(_ arr: [Int]) -> [Int] {
guard arr.count > 1 else { return arr }
let mid = arr.count / 2
let left = mergeSort(Array(arr[..<mid]))
let right = mergeSort(Array(arr[mid...]))
var i = 0, j = 0, res: [Int] = []
while i < left.count && j < right.count {
if left[i] <= right[j] { res.append(left[i]); i += 1 }
else { res.append(right[j]); j += 1 }
}
if i < left.count { res.append(contentsOf: left[i...]) }
if j < right.count { res.append(contentsOf: right[j...]) }
return res
}3.2 快速排序（Quick Sort）
思路：选基准 pivot，一次分区把小于等于的放左侧，大于的放右侧；递归处理两边。平均 O(n log n)，最坏 O(n^2)；原地、不稳定。
配图：
# 语言：Python — 快排（Lomuto 分区）
import random
def quick_sort(a: list[int]) -> None:
def part(lo, hi) -> int:
pivot = a[hi]
i = lo - 1
for j in range(lo, hi):
if a[j] <= pivot:
i += 1; a[i], a[j] = a[j], a[i]
a[i+1], a[hi] = a[hi], a[i+1]
return i + 1
def sort(lo, hi):
if lo >= hi: return
# 随机化基准，降低最坏概率
p = random.randint(lo, hi)
a[p], a[hi] = a[hi], a[p]
m = part(lo, hi)
sort(lo, m - 1); sort(m + 1, hi)
sort(0, len(a) - 1)// 语言：Swift — 快排（Lomuto 分区）
func quickSort(_ arr: inout [Int]) {
func partition(_ lo: Int, _ hi: Int) -> Int {
let pivot = arr[hi]
var i = lo - 1
if lo <= hi {
for j in lo..<hi {
if arr[j] <= pivot { i += 1; arr.swapAt(i, j) }
}
}
arr.swapAt(i+1, hi)
return i + 1
}
func sort(_ lo: Int, _ hi: Int) {
if lo >= hi { return }
let m = partition(lo, hi)
sort(lo, m-1); sort(m+1, hi)
}
if !arr.isEmpty { sort(0, arr.count-1) }
}3.3 堆排序（Heap Sort）
思路：把数组建成最大堆，循环把堆顶（最大值）与末尾交换并下沉恢复堆。O(n log n)，原地、不稳定。
# 语言：Python — 堆排序（原地，不稳定）
def heap_sort(a: list[int]) -> None:
n = len(a)
def sink(i, size):
while True:
l = 2*i + 1; r = l + 1; largest = i
if l < size and a[l] > a[largest]: largest = l
if r < size and a[r] > a[largest]: largest = r
if largest == i: break
a[i], a[largest] = a[largest], a[i]; i = largest
# build heap
for i in range(n//2 - 1, -1, -1): sink(i, n)
# sort
for end in range(n-1, 0, -1):
a[0], a[end] = a[end], a[0]
sink(0, end)// 语言：Swift — 堆排序（原地，不稳定）
func heapSort(_ arr: inout [Int]) {
let n = arr.count
func sink(_ i0: Int, _ size: Int) {
var i = i0
while true {
let l = 2*i + 1, r = l + 1
var p = i
if l < size && arr[l] > arr[p] { p = l }
if r < size && arr[r] > arr[p] { p = r }
if p == i { break }
arr.swapAt(i, p); i = p
}
}
if n <= 1 { return }
for i in stride(from: n/2 - 1, through: 0, by: -1) { sink(i, n) }
for end in stride(from: n-1, to: 0, by: -1) {
arr.swapAt(0, end)
sink(0, end)
}
}4. 非比较排序：计数 / 桶 / 基数
适用前提：数值范围或位数可控；需要额外空间。
4.1 计数排序（Counting Sort）
思想：统计每个值出现次数，再前缀和定位到稳定位置。稳定、O(n + k)（k 为值域）。
# 语言：Python — 计数排序（非负整数）
def counting_sort(a: list[int]) -> list[int]:
if not a: return []
mx = max(a); cnt = [0]*(mx+1)
for x in a: cnt[x] += 1
for i in range(1, len(cnt)): cnt[i] += cnt[i-1] # 前缀和
res = [0]*len(a)
for x in reversed(a): # 倒序遍历以保证“稳定”
cnt[x] -= 1
res[cnt[x]] = x
return res// 语言：Swift — 计数排序（非负整数）
func countingSort(_ arr: [Int]) -> [Int] {
guard let mx = arr.max(), mx >= 0 else { return arr }
var cnt = Array(repeating: 0, count: mx + 1)
for x in arr { cnt[x] += 1 }
for i in 1..<cnt.count { cnt[i] += cnt[i - 1] }
var res = Array(repeating: 0, count: arr.count)
for x in arr.reversed() {
cnt[x] -= 1
res[cnt[x]] = x
}
return res
}4.2 基数排序（Radix Sort, LSD）
思想：从低位到高位按位稳定排序（桶 + 计数/稳定排序）。
配图：
# 语言：Python — 基数排序（十进制，非负）
def radix_sort_lsd(a: list[int]) -> list[int]:
if not a: return []
m = max(a); exp = 1
out = a[:]
while m // exp > 0:
# 对当前位做计数排序（稳定）
cnt = [0]*10
for x in out:
cnt[(x // exp) % 10] += 1
for i in range(1, 10): cnt[i] += cnt[i-1]
res = [0]*len(out)
for x in reversed(out):
d = (x // exp) % 10
cnt[d] -= 1
res[cnt[d]] = x
out = res
exp *= 10
return out// 语言：Swift — 基数排序（十进制，非负）
func radixSortLSD(_ arr: [Int]) -> [Int] {
guard let m = arr.max(), m >= 0 else { return arr }
var out = arr
var exp = 1
while m / exp > 0 {
var cnt = Array(repeating: 0, count: 10)
for x in out { cnt[(x / exp) % 10] += 1 }
for i in 1..<10 { cnt[i] += cnt[i-1] }
var res = Array(repeating: 0, count: out.count)
for x in out.reversed() {
let d = (x / exp) % 10
cnt[d] -= 1
res[cnt[d]] = x
}
out = res; exp *= 10
}
return out
}5. 常见考点与踩坑
- o 稳定性：插入/归并/计数/（基数在内部排序稳定时）稳定；选择/快排/堆排/希尔不稳定。
- o 原地：归并、计数、基数不是原地；其余大多原地（快排栈 O(log n)）。
- o 快排退化：接近有序时易退化，用随机选枢轴或“三数取中”。
- o 归并的边拷贝：注意“剩余部分直接拼接”。
- o 计数/基数的空间：值域/桶数越大，空间越大；注意内存限制。
- o 整型除法：不同语言的向零取整差异（Python3 需要 int(a/b) 或 //）。
6. 练习题
练习 1｜判断排序的稳定性与是否原地
题目：对以下算法判断“稳定/不稳定”“原地/非原地”：插入、选择、归并、堆、快排、计数。
答案：插入（稳定，原地）；选择（不稳定，原地）；归并（稳定，非原地）；堆（不稳定，原地）；快排（不稳定，原地近似，递归栈 O(log n)）；计数（稳定，非原地）。
理由：是否交换非相邻元素、是否只移动相邻元素；是否需要额外数组/桶。
练习 2｜实现稳定的计数排序
题目：给定非负整数数组，实现稳定计数排序。
思路：见 §4.1，倒序遍历原数组填充到结果数组。
参考代码：已在 §4.1 提供。
练习 3｜快速选择（第 k 小）
题目：返回无序数组中第 k 小元素。
思路：Quickselect：一次分区后只递归到一侧；平均 O(n)。
# 语言：Python — Quickselect（第 k 小，k 从 1 开始）
import random
def quickselect(a: list[int], k: int) -> int:
k -= 1
def part(lo, hi):
p = random.randint(lo, hi)
a[p], a[hi] = a[hi], a[p]
pivot = a[hi]; i = lo - 1
for j in range(lo, hi):
if a[j] <= pivot: i += 1; a[i], a[j] = a[j], a[i]
a[i+1], a[hi] = a[hi], a[i+1]
return i + 1
lo, hi = 0, len(a)-1
while True:
m = part(lo, hi)
if m == k: return a[m]
elif m > k: hi = m - 1
else: lo = m + 1// 语言：Swift — Quickselect（第 k 小，k 从 1 开始）
func quickselect(_ arr0: inout [Int], _ k: Int) -> Int {
var arr = arr0
var lo = 0, hi = arr.count - 1, target = k - 1
func partition(_ lo: Int, _ hi: Int) -> Int {
let pivot = arr[hi]
var i = lo - 1
for j in lo..<hi {
if arr[j] <= pivot { i += 1; arr.swapAt(i, j) }
}
arr.swapAt(i+1, hi)
return i + 1
}
while true {
let m = partition(lo, hi)
if m == target { return arr[m] }
else if m > target { hi = m - 1 }
else { lo = m + 1 }
}
}练习 4｜合并 K 个有序数组
题目：合并 k 个升序数组为一个升序数组。
思路：使用小根堆按头元素合并。复杂度 O(N log k)。
# 语言：Python — 小根堆合并
import heapq
def merge_k_sorted(arrs: list[list[int]]) -> list[int]:
h = []
for i, arr in enumerate(arrs):
if arr: heapq.heappush(h, (arr[0], i, 0))
res = []
while h:
v, i, j = heapq.heappop(h)
res.append(v)
if j + 1 < len(arrs[i]):
heapq.heappush(h, (arrs[i][j+1], i, j+1))
return res// 语言：Swift — 小根堆合并（简易二叉堆）
struct MinHeap<T> {
var a: [T] = []
let less: (T,T)->Bool
init(_ less:@escaping(T,T)->Bool){ self.less=less }
mutating func push(_ x:T){ a.append(x); siftUp(a.count-1) }
mutating func pop() -> T {
let v=a[0]; a[0]=a[a.count-1]; a.removeLast(); if !a.isEmpty { siftDown(0) }; return v
}
var isEmpty: Bool { a.isEmpty }
private mutating func siftUp(_ i0:Int){ var i=i0; while i>0 { let p=(i-1)/2; if less(a[i],a[p]){a.swapAt(i,p); i=p}else{break} } }
private mutating func siftDown(_ i0:Int){ var i=i0; while true{ let l=2*i+1,r=l+1; var p=i
if l<a.count && less(a[l],a[p]){p=l}; if r<a.count && less(a[r],a[p]){p=r}; if p==i{break}; a.swapAt(i,p); i=p } }
}
func mergeKSorted(_ arrs: [[Int]]) -> [Int] {
typealias Node = (val:Int, i:Int, j:Int)
var h = MinHeap<Node> { $0.val < $1.val }
for (i, arr) in arrs.enumerated() where !arr.isEmpty { h.push((arr[0], i, 0)) }
var res:[Int] = []
while !h.isEmpty {
let x = h.pop(); res.append(x.val)
let j = x.j + 1
if j < arrs[x.i].count { h.push((arrs[x.i][j], x.i, j)) }
}
return res
}练习 5｜对近乎有序的数组排序
题目：给定数组中每个元素距离其排序后位置最多为 k，请在 O(n log k) 内排序。
思路：维护大小为 k+1 的小根堆，滑动输出。
# 语言：Python — 几乎有序排序
import heapq
def sort_nearly_sorted(a: list[int], k: int) -> list[int]:
h = a[:k+1]; heapq.heapify(h)
res = []; idx = k + 1
while h:
res.append(heapq.heappop(h))
if idx < len(a):
heapq.heappush(h, a[idx]); idx += 1
return res// 语言：Swift — 几乎有序排序（复用上面的 MinHeap）
func sortNearlySorted(_ arr: [Int], _ k: Int) -> [Int] {
var h = MinHeap<Int>(<)
var res:[Int] = []
var i = 0
while i < min(arr.count, k+1) { h.push(arr[i]); i += 1 }
var j = i
while !h.isEmpty {
res.append(h.pop())
if j < arr.count { h.push(arr[j]); j += 1 }
}
return res
}