萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Ruby 一行程式碼實現快速排序:函數式風格、陣列分割、遞歸組合

核心程式碼

def quick_sort(a)
  return a if a.size < 2
  (x = a.pop) ? quick_sort(a.select { |i| i <= x }) + [x] + quick_sort(a.select { |i| i > x }) : []
end

arr = [72,6,57,88,60,42,83,73,42,48,85]
p quick_sort(arr)  # => [6, 42, 42, 48, 57, 60, 72, 73, 83, 85, 88]

逐步拆解

  1. return a if a.size < 2:基準情況,0 或 1 元素直接返回。
  2. (x = a.pop):取出並移除最後一個元素作為 基準值,賦值給 x,整個表達式值為 x (truthy)。
  3. a.select { |i| i <= x }:小於等於基準值的子陣列。
  4. a.select { |i| i > x }:大於基準值的子陣列。
  5. 遞歸排序兩側,中間插入基準值 [x],陣列連接 +。
  6. : []:理論上不會執行 (因 pop 後 size>=1),保持語法完整。

特點

  • 非原地排序:產生新陣列,原陣列被破壞 (pop)。
  • 函數式風格:無副作用 (除 pop)、宣告式、極度精簡。
  • 效能:平均 O(n log n),最壞 O(n²);記憶體 O(n log n) (遞歸深度 + 中間陣列)。
  • 穩定性:不穩定 (相等元素相對序可能改變)。

改良版:不破壞原陣列、隨機基準值

def quick_sort(a)
  return a if a.size < 2
  pivot = a.sample  # 隨機基準值,避免有序輸入退化
  left, mid, right = a.partition { |x| x <=> pivot }
  quick_sort(left) + mid + quick_sort(right)
end

partition 一次遍歷三分 (小於/等於/大於),比雙重 select 更快。

基準測試

require 'benchmark'
arr = Array.new(10000) { rand(10000) }
Benchmark.bm do |x|
  x.report("quick_sort") { quick_sort(arr.dup) }
  x.report("Array#sort") { arr.sort }
end
# 典型結果: quick_sort ~30ms, Array#sort ~2ms (C 實作優化極致)
copyright © 萬盛學電腦網 all rights reserved