Ruby 實現三種快速排序變體：標準版、隨機化版、函數式隨機化版

本文展示三種 Ruby 快速排序實作：傳統索引交換版、隨機化基準值版、以及利用 Ruby 語法糖的函數式隨機化版。對比其程式碼風格、效能特性與適用場景。

版本一：標準快速排序（索引交換，教科書式）

def quick_sort(arr, first, last)
  return if first >= last
  mid = partition(arr, first, last)
  quick_sort(arr, first, mid - 1)
  quick_sort(arr, mid + 1, last)
end

def partition(arr, first, last)
  x = arr[last]
  i = first - 1
  (first...last).each do |j|
    if arr[j] <= x
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
    end
  end
  arr[i + 1], arr[last] = arr[last], arr[i + 1]
  i + 1
end

# 使用
arr = Array.new(12) { rand(100) }
puts "Original: #{arr}"
quick_sort(arr, 0, arr.size - 1)
puts "Sorted:   #{arr}"

版本二：隨機化快速排序（避免最壞 O(n²)）

def randomized_quick_sort(arr, first, last)
  return if first >= last
  mid = randomized_partition(arr, first, last)
  randomized_quick_sort(arr, first, mid - 1)
  randomized_quick_sort(arr, mid + 1, last)
end

def randomized_partition(arr, first, last)
  i = rand(last - first + 1) + first
  arr[i], arr[last] = arr[last], arr[i]
  partition(arr, first, last)
end

# partition 同版本一

版本三：函數式隨機化版（語法糖極致）

def randomized_quick_sort_func(a)
  return a if a.size < 2
  i = rand(a.size)
  a[i], a[-1] = a[-1], a[i]
  x = a.pop
  randomized_quick_sort_func(a.select { |v| v <= x }) + [x] + randomized_quick_sort_func(a.select { |v| v > x })
end

# 使用
arr = Array.new(12) { rand(100) }
puts "Original: #{arr}"
puts "Sorted:   #{randomized_quick_sort_func(arr)}"

三版本對比

關鍵差異解析

• 原地 vs 複製：版本一二修改原陣列，版本三建立新陣列（函數式不可變風格）。
• 隨機化關鍵：rand(last-first+1)+first 等概率選取索引，與最後元素交換，再呼叫標準分區。
• 語法糖：版本三使用 a.pop、select、三元運算子、陣列連接 +，將分治邏輯壓縮為單一表達式。

生產環境建議

# 直接使用內建排序 (Timsort, O(n log n) 最壞情況, 穩定)
arr.sort                    # 數值/字串預設排序
arr.sort_by { |x| x.key }   # 依鍵排序 (Schwartzian transform)
arr.sort { |a,b| a <=> b }  # 自定比較

三版本快速排序適合演算法學習、面試準備、程式碼高爾夫。實際專案請信任 Array#sort。