萬盛學電腦網

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

Ruby 實現合併排序:分治法、合併步驟、遞歸實作、效能分析

演算法核心

分治法三步驟:

  1. 分解:將陣列對半分割,直到單元素。
  2. 解決:單元素天然有序。
  3. 合併:將兩個有序子陣列合併為一個有序陣列。

完整實作

def merge(arr, left, mid, right)
  left_arr  = arr[left..mid]
  right_arr = arr[mid+1..right]
  # 哨兵值避免邊界檢查
  left_arr  << Float::INFINITY
  right_arr << Float::INFINITY

  i = j = 0
  (left..right).each do |k|
    if left_arr[i] <= right_arr[j]
      arr[k] = left_arr[i]; i += 1
    else
      arr[k] = right_arr[j]; j += 1
    end
  end
end

def merge_sort(arr, left, right)
  return if left >= right
  mid = (left + right) / 2
  merge_sort(arr, left, mid)
  merge_sort(arr, mid+1, right)
  merge(arr, left, mid, right)
end

# 測試
arr = Array.new(13) { rand(100) }
puts "Original: #{arr}"
merge_sort(arr, 0, arr.size-1)
puts "Sorted:   #{arr}"
# Original: [4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70]
# Sorted:   [4, 21, 29, 32, 37, 40, 49, 58, 70, 70, 75, 82, 84]

關鍵技巧:哨兵值

在兩子陣列末尾加入 Float::INFINITY,合併迴圈無需檢查 i < left_arr.size 等邊界條件,簡化邏輯並提升速度。

複雜度分析

指標合併排序快速排序堆積排序
時間 (平均)O(n log n)O(n log n)O(n log n)
時間 (最壞)O(n log n)O(n²)O(n log n)
空間O(n) 輔助陣列O(log n) 堆疊O(1) 原地
穩定性穩定不穩定不穩定

Ruby 語法糖版 (函數式、非原地)

def merge_sort_func(a)
  return a if a.size <= 1
  mid = a.size / 2
  left  = merge_sort_func(a[0...mid])
  right = merge_sort_func(a[mid..-1])
  merge_func(left, right)
end

def merge_func(l, r)
  res = []
  while l.any? && r.any?
    res << (l.first <= r.first ? l.shift : r.shift)
  end
  res + l + r
end

實際專案建議

  • 直接使用 Array#sort (C 實作 Timsort,混合合併+插入,極快且穩定)。
  • 需自定比較器時:arr.sort { |a,b| a.length <=> b.length } 或 arr.sort_by(&:length)。
  • 外部排序 (超大檔案) 才需手寫合併排序 (磁碟分塊排序 + k-way merge)。
copyright © 萬盛學電腦網 all rights reserved