Ruby实现的各种排序算法

时间复杂度：θ(n^2)

bubble sort

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 
  return a 
end

selection sort

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

insertion sort

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 
  return a 
end 

 shell sort
 

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

时间复杂度：θ(n*logn)

merge sort

def merge(l, r) 
  result = [] 
  while l.size > 0 and r.size > 0 do 
    if l.first < r.first 
      result << l.shift 
    else 
      result << r.shift 
    end 
  end 
  if l.size > 0 
    result += l 
  end 
  if r.size > 0 
    result += r 
  end 
  return result 
end 
 
def merge_sort(a) 
  return a if a.size <= 1 
  middle = a.size / 2 
  left = merge_sort(a[0, middle]) 
  right = merge_sort(a[middle, a.size - middle]) 
  merge(left, right) 
end 

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

def quick_sort(a) 
  (x=a.pop) ? quick_sort(a.select{|i| i <= x}) + [x] + quick_sort(a.select{|i| i > x}) : [] 
end 
 
def first_number(n) 
  (n * 10).to_i 
end 
 
def bucket_sort(a) 
  tmp = [] 
  (0..9).each do |j| 
    tmp[j] = [] 
  end 
   
  a.each do |n| 
    k = first_number(n) 
    tmp[k] << n 
  end 
 
  (0..9).each do |j| 
    tmp[j] = quick_sort(tmp[j]) 
  end 
 
  tmp.flatten 
end 
 
a = [0.75, 0.13, 0, 0.44, 0.55, 0.01, 0.98, 0.1234567] 
p bucket_sort(a) 
 
# result:  
[0, 0.01, 0.1234567, 0.13, 0.44, 0.55, 0.75, 0.98]