萬盛學電腦網

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

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)
  pivot = arr[last]
  i = first - 1
  (first...last).each do |j|
    if arr[j] <= pivot
      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(first..last)
  arr[i], arr[last] = arr[last], arr[i]
  partition(arr, first, last)  # 復用標準 partition
end

版本三:Ruby 語法糖隨機化版 (函數式、極簡)

def rqs(a)
  return a if a.size < 2
  i = rand(a.size)
  a[i], a[-1] = a[-1], a[i]  # 隨機基準值換到末尾
  x = a.pop
  rqs(a.select { |v| v <= x }) + [x] + rqs(a.select { |v| v > x })
end

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

三版本對比

版本風格原地排序基準值選擇程式碼行數適用場景
標準命令式/教科書✓固定末尾~25教學、嵌入式、需原地
隨機化命令式+隨機✓隨機~30生產環境、避免最壞情況
語法糖函數式/宣告式✗隨機~8腳本、原型、程式碼高爾夫

效能基準 (10,000 元素)


       user     system      total        real
標準版   0.025      0.000      0.025 (  0.025)
隨機化   0.024      0.000      0.024 (  0.024)
語法糖   0.045      0.000      0.045 (  0.045)
內建sort 0.002      0.000      0.002 (  0.002)

結論:實際專案請直接用 Array#sort 或 Array#sort_by,C 實作經過高度優化。自行實現僅供演算法學習。

copyright © 萬盛學電腦網 all rights reserved