Ruby 算法实战全景

Ruby 算法以简洁优雅的 Block 闭包与链式调用著称：

• select 过滤与分治：用极少行数实现清晰无歧义的快速排序。
• downto 逆向步进：优雅表达动态规划的状态倒序压缩。

---

📊 算法专题与复杂度

算法专题	典型问题 / 算法	核心思想	时间复杂度	空间复杂度
排序	Functional QuickSort / sort	Block 谓词划分 / C 内部排序	$O(n \log n)$	$O(n)$
动态规划	0/1 背包问题	downto 迭代倒序压缩	$O(N \cdot W)$	$O(W)$

---

1. 快速排序算法 (QuickSort with Blocks)

def quick_sort(arr)
  return arr if arr.length <= 1
  pivot = arr[arr.length / 2]
  left = arr.select { |x| x < pivot }
  equal = arr.select { |x| x == pivot }
  right = arr.select { |x| x > pivot }
  quick_sort(left) + equal + quick_sort(right)
end

puts "=== Ruby Functional QuickSort ==="
data = [64, 25, 12, 22, 11]
sorted = quick_sort(data)
raise "Sort error" unless sorted == [11, 12, 22, 25, 64]

puts "Sorted: #{sorted}"
puts "Ruby QuickSort tests passed successfully."

🐳 Docker Verified📋ruby:3.3-alpine

Exit Code: 0

=== Ruby Functional QuickSort ===
Sorted: [11, 12, 22, 25, 64]
Ruby QuickSort tests passed successfully.

---

2. 动态规划：0/1 背包问题

def knapsack(capacity, weights, values)
  dp = Array.new(capacity + 1, 0)
  weights.each_with_index do |w, i|
    capacity.downto(w) do |j|
      dp[j] = [dp[j], dp[j - w] + values[i]].max
    end
  end
  dp[capacity]
end

puts "=== Ruby 0/1 Knapsack DP ==="
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
max_val = knapsack(5, weights, values)
raise "Knapsack error" unless max_val == 7

puts "Max Knapsack Value: #{max_val}"
puts "Ruby Knapsack DP tests passed successfully."

🐳 Docker Verified📋ruby:3.3-alpine

Exit Code: 0

=== Ruby 0/1 Knapsack DP ===
Max Knapsack Value: 7
Ruby Knapsack DP tests passed successfully.