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}"
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
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 | 腳本、原型、程式碼高爾夫 |
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 實作經過高度優化。自行實現僅供演算法學習。