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])