Ruby代码片段3 常见算法

这个文件移动到 2，要不要把娱乐移动到这里。

快速排序

# 快速排序的 Ruby 实现

def quick_sort(arr, left = 0, right = arr.length - 1)
  return arr if left >= right
  
  pivot_index = partition(arr, left, right)
  quick_sort(arr, left, pivot_index - 1)
  quick_sort(arr, pivot_index + 1, right)
  
  arr
end

def partition(arr, left, right)
  # 选择最右边的元素作为基准
  pivot = arr[right]
  i = left - 1
  
  (left...right).each do |j|
    if arr[j] <= pivot
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
    end
  end
  
  # 将基准放到正确位置
  arr[i + 1], arr[right] = arr[right], arr[i + 1]
  i + 1
end

二分查找

注意边界条件，很容易弄错。

# 二分查找的 Ruby 实现

def binary_search(arr, target)
  left = 0
  right = arr.length - 1
  
  while left <= right
    mid = left + (right - left) / 2  # 避免溢出
    
    if arr[mid] == target
      return mid  # 找到目标，返回索引
    elsif arr[mid] < target
      left = mid + 1  # 目标在右半部分
    else
      right = mid - 1  # 目标在左半部分
    end
  end
  
  -1  # 未找到
end

最小生成树

最短距离

数值算法

附录

参考资料

• Project Euler
• LeetCode