萬盛學電腦網

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

Ruby 八大經典排序算法全實現:從 O(n²) 到 O(n log n) 與線性排序

前言

排序是演算法入門的必修課,亦是面試高頻考點。本文一次性呈現 Ruby 實現的八大排序:冒泡、選擇、插入、希爾、歸併、堆、快速、計數、基數、桶排序,涵蓋比較類與非比較類,並標註時間複雜度,代碼均經驗證可直接運行。

比較類排序(基於元素兩兩比較)

1. 冒泡排序 — Θ(n²)

相鄰元素兩兩比較,大的「冒泡」到右端。雙重迴圈,外層控制輪數,內層推大值。

def bubble_sort(a)
  (a.size - 2).downto(0) do |i|
    (0..i).each do |j|
      a[j], a[j + 1] = a[j + 1], a[j] if a[j] > a[j + 1]
    end
  end
  a
end

2. 選擇排序 — Θ(n²)

每輪在未排序區找最小值,放到有序區尾部。注意:此處實現會修改原陣列並建立新陣列 b。

def selection_sort(a)
  b = []
  a.size.times do
    min = a.min
    b << min
    a.delete_at(a.index(min))
  end
  b
end

3. 插入排序 — Θ(n²)(最佳 O(n))

將未排序元素插入已排序序列適當位置,近似整理撲克牌。

def insertion_sort(a)
  a.each_with_index do |el, i|
    j = i - 1
    while j >= 0
      break if a[j] <= el
      a[j + 1] = a[j]
      j -= 1
    end
    a[j + 1] = el
  end
  a
end

4. 希爾排序 — O(n¹·²⁵) ~ O(n¹·⁵)

插入排序的改進版,按間隔 gap 分組插入,逐步縮小 gap 至 1。

def shell_sort(a)
  gap = a.size
  while gap > 1
    gap /= 2
    (gap...a.size).each do |i|
      j = i
      while j > 0
        if a[j] <= a[j - gap]
          a[j], a[j - gap] = a[j - gap], a[j]
        end
        j -= gap
      end
    end
  end
  a
end

5. 歸併排序 — Θ(n log n)

分治法:遞歸拆分至單元素,再合併兩個有序陣列。穩定、適合鏈表與外部排序。

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

def merge_sort(a)
  return a if a.size <= 1
  mid = a.size / 2
  merge(merge_sort(a[0, mid]), merge_sort(a[mid..-1]))
end

6. 堆排序 — Θ(n log n)

建最大堆,反覆交換堆頂與末尾元素並下沉調整。原地排序、不穩定。

def heapify(a, idx, size)
  left = 2 * idx + 1
  right = 2 * idx + 2
  largest = idx
  largest = left  if left  < size && a[left]  > a[largest]
  largest = right if right < size && a[right] > a[largest]
  if largest != idx
    a[idx], a[largest] = a[largest], a[idx]
    heapify(a, largest, size)
  end
end

def build_heap(a)
  (a.length / 2 - 1).downto(0) { |i| heapify(a, i, a.size) }
end

def heap_sort(a)
  return a if a.size <= 1
  size = a.size
  build_heap(a)
  while size > 0
    a[0], a[size - 1] = a[size - 1], a[0]
    size -= 1
    heapify(a, 0, size)
  end
  a
end

7. 快速排序 — 平均 Θ(n log n),最差 O(n²)

基準值分區,遞歸排序左右子陣列。Ruby 一行式寫法極具表達力。

def quick_sort(a)
  (x = a.pop) ? quick_sort(a.select { |i| i <= x }) + [x] + quick_sort(a.select { |i| i > x }) : []
end

非比較類線性排序(利用鍵值範圍特性)

8. 計數排序 — Θ(n + k)

統計每個值出現次數,按順序展開。適用於小範圍整數。

def counting_sort(a)
  min, max = a.min, a.max
  counts = Array.new(max - min + 1, 0)
  a.each { |n| counts[n - min] += 1 }
  (0...counts.size).flat_map { |i| [i + min] * counts[i] }
end

9. 基數排序 — Θ(d·(n + k))

從低位到高位依次穩定排序(通常用計數排序作子程序)。

def kth_digit(n, k)
  (n / 10**(k - 1)) % 10
end

def radix_sort(a)
  return a if a.empty?
  max = a.max
  d = Math.log10(max).floor + 1
  (1..d).each do |i|
    buckets = Array.new(10) { [] }
    a.each { |n| buckets[kth_digit(n, i)] << n }
    a = buckets.flatten
  end
  a
end

10. 桶排序 — 平均 Θ(n + k)

將 [0, 1) 區間均分桶,各桶內快排再合併。適用均勻分佈浮點數。

def bucket_sort(a)
  return a if a.empty?
  buckets = Array.new(10) { [] }
  a.each { |n| buckets[(n * 10).to_i] << n }
  buckets.each { |b| b.replace(quick_sort(b)) }
  buckets.flatten
end

# 測試
p bucket_sort([0.75, 0.13, 0, 0.44, 0.55, 0.01, 0.98, 0.1234567])
# => [0, 0.01, 0.1234567, 0.13, 0.44, 0.55, 0.75, 0.98]

複雜度總覽表

算法平均時間最差時間空間穩定
冒泡Θ(n²)Θ(n²)O(1)✓
選擇Θ(n²)Θ(n²)O(n)✗
插入Θ(n²)Θ(n²)O(1)✓
希爾~O(n¹·³)O(n²)O(1)✗
歸併Θ(n log n)Θ(n log n)O(n)✓
堆Θ(n log n)Θ(n log n)O(1)✗
快速Θ(n log n)O(n²)O(log n)✗
計數Θ(n+k)Θ(n+k)Θ(n+k)✓
基數Θ(d(n+k))Θ(d(n+k))Θ(n+k)✓
桶Θ(n+k)O(n²)Θ(n+k)✓

總結

Ruby 靈活的語法讓排序邏輯極其精簡。實務中:

  • 小規模或近乎有序資料 → 插入排序
  • 通用高效、穩定 → 歸併排序
  • 原地、不穩定、平均快 → 快速排序
  • 整數小範圍 → 計數/基數排序
  • 浮點數均勻分佈 → 桶排序

理解各算法權衡,才能在實際工程中做出最佳選擇。

copyright © 萬盛學電腦網 all rights reserved