Ruby实现的各种排序算法

Heap sort

def heapify(a, idx, size) 
  left_idx = 2 * idx + 1 
  right_idx = 2 * idx + 2 
  bigger_idx = idx 
  bigger_idx = left_idx if left_idx < size && a[left_idx] > a[idx] 
  bigger_idx = right_idx if right_idx < size && a[right_idx] > a[bigger_idx] 
  if bigger_idx != idx 
    a[idx], a[bigger_idx] = a[bigger_idx], a[idx] 
    heapify(a, bigger_idx, size) 
  end 
end 

def build_heap(a) 
  last_parent_idx = a.length / 2 - 1 
  i = last_parent_idx 
  while i >= 0 
    heapify(a, i, a.size) 
    i = i - 1 
  end 
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 = size - 1 
    heapify(a, 0, size) 
  end 
  return a 
end 

Quick sort

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

时间复杂度：Θ(n)

Counting sort

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

Radix sort

def kth_digit(n, i) 
  while(i > 1) 
    n = n / 10 
    i = i - 1 
  end 
  n % 10 
end 
 
def radix_sort(a) 
  max = a.max 
  d = Math.log10(max).floor + 1 
 
  (1..d).each do |i| 
    tmp = [] 
    (0..9).each do |j| 
      tmp[j] = [] 
    end 
 
    a.each do |n| 
      kth = kth_digit(n, i) 
      tmp[kth] << n 
    end 
    a = tmp.flatten 
  end 
  return a 
end 

Bucket sort