排序是演算法入門的必修課,亦是面試高頻考點。本文一次性呈現 Ruby 實現的八大排序:冒泡、選擇、插入、希爾、歸併、堆、快速、計數、基數、桶排序,涵蓋比較類與非比較類,並標註時間複雜度,代碼均經驗證可直接運行。
Θ(n²)相鄰元素兩兩比較,大的「冒泡」到右端。雙重迴圈,外層控制輪數,內層推大值。
def bubble_sort(a)
(a.size - 2).downto(0) do |i|
(0..i).each do |j|
a[j], a[j + 1] = a[j + 1], a[j] if a[j] > a[j + 1]
end
end
a
end
Θ(n²)每輪在未排序區找最小值,放到有序區尾部。注意:此處實現會修改原陣列並建立新陣列 b。
def selection_sort(a)
b = []
a.size.times do
min = a.min
b << min
a.delete_at(a.index(min))
end
b
end
Θ(n²)(最佳 O(n))將未排序元素插入已排序序列適當位置,近似整理撲克牌。
def insertion_sort(a)
a.each_with_index do |el, i|
j = i - 1
while j >= 0
break if a[j] <= el
a[j + 1] = a[j]
j -= 1
end
a[j + 1] = el
end
a
end
O(n¹·²⁵) ~ O(n¹·⁵)插入排序的改進版,按間隔 gap 分組插入,逐步縮小 gap 至 1。
def shell_sort(a)
gap = a.size
while gap > 1
gap /= 2
(gap...a.size).each do |i|
j = i
while j > 0
if a[j] <= a[j - gap]
a[j], a[j - gap] = a[j - gap], a[j]
end
j -= gap
end
end
end
a
end
Θ(n log n)分治法:遞歸拆分至單元素,再合併兩個有序陣列。穩定、適合鏈表與外部排序。
def merge(l, r)
result = []
while l.any? && r.any?
result << (l.first < r.first ? l.shift : r.shift)
end
result + l + r
end
def merge_sort(a)
return a if a.size <= 1
mid = a.size / 2
merge(merge_sort(a[0, mid]), merge_sort(a[mid..-1]))
end
Θ(n log n)建最大堆,反覆交換堆頂與末尾元素並下沉調整。原地排序、不穩定。
def heapify(a, idx, size)
left = 2 * idx + 1
right = 2 * idx + 2
largest = idx
largest = left if left < size && a[left] > a[largest]
largest = right if right < size && a[right] > a[largest]
if largest != idx
a[idx], a[largest] = a[largest], a[idx]
heapify(a, largest, size)
end
end
def build_heap(a)
(a.length / 2 - 1).downto(0) { |i| heapify(a, i, a.size) }
end
def heap_sort(a)
return a if a.size <= 1
size = a.size
build_heap(a)
while size > 0
a[0], a[size - 1] = a[size - 1], a[0]
size -= 1
heapify(a, 0, size)
end
a
end
Θ(n log n),最差 O(n²)基準值分區,遞歸排序左右子陣列。Ruby 一行式寫法極具表達力。
def quick_sort(a)
(x = a.pop) ? quick_sort(a.select { |i| i <= x }) + [x] + quick_sort(a.select { |i| i > x }) : []
end
Θ(n + k)統計每個值出現次數,按順序展開。適用於小範圍整數。
def counting_sort(a)
min, max = a.min, a.max
counts = Array.new(max - min + 1, 0)
a.each { |n| counts[n - min] += 1 }
(0...counts.size).flat_map { |i| [i + min] * counts[i] }
end
Θ(d·(n + k))從低位到高位依次穩定排序(通常用計數排序作子程序)。
def kth_digit(n, k)
(n / 10**(k - 1)) % 10
end
def radix_sort(a)
return a if a.empty?
max = a.max
d = Math.log10(max).floor + 1
(1..d).each do |i|
buckets = Array.new(10) { [] }
a.each { |n| buckets[kth_digit(n, i)] << n }
a = buckets.flatten
end
a
end
Θ(n + k)將 [0, 1) 區間均分桶,各桶內快排再合併。適用均勻分佈浮點數。
def bucket_sort(a)
return a if a.empty?
buckets = Array.new(10) { [] }
a.each { |n| buckets[(n * 10).to_i] << n }
buckets.each { |b| b.replace(quick_sort(b)) }
buckets.flatten
end
# 測試
p bucket_sort([0.75, 0.13, 0, 0.44, 0.55, 0.01, 0.98, 0.1234567])
# => [0, 0.01, 0.1234567, 0.13, 0.44, 0.55, 0.75, 0.98]
| 算法 | 平均時間 | 最差時間 | 空間 | 穩定 |
|---|---|---|---|---|
| 冒泡 | Θ(n²) | Θ(n²) | O(1) | ✓ |
| 選擇 | Θ(n²) | Θ(n²) | O(n) | ✗ |
| 插入 | Θ(n²) | Θ(n²) | O(1) | ✓ |
| 希爾 | ~O(n¹·³) | O(n²) | O(1) | ✗ |
| 歸併 | Θ(n log n) | Θ(n log n) | O(n) | ✓ |
| 堆 | Θ(n log n) | Θ(n log n) | O(1) | ✗ |
| 快速 | Θ(n log n) | O(n²) | O(log n) | ✗ |
| 計數 | Θ(n+k) | Θ(n+k) | Θ(n+k) | ✓ |
| 基數 | Θ(d(n+k)) | Θ(d(n+k)) | Θ(n+k) | ✓ |
| 桶 | Θ(n+k) | O(n²) | Θ(n+k) | ✓ |
Ruby 靈活的語法讓排序邏輯極其精簡。實務中:
理解各算法權衡,才能在實際工程中做出最佳選擇。