用Ruby实现算法--插入排序与快速排序

插入排序

插入排序的灵感也许来自于扑克牌, 将n按照大小插入到0~n-1中, 当左边都排序好了, 整个数组也就排序好了

3 5 1 2 4 7 6 8
3 5 1 2 4 7 6 8
1 3 5 2 4 7 6 8
1 2 3 5 4 7 6 8
1 2 3 4 5 7 6 8
1 2 3 4 5 7 6 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

def insertion_sort(array)
  return n if array.size == 1
  array.each_with_index do |n,i|
    j = i-1
    while array[j] > n && j >= 0
      tmp = array[j]
      array[j] = n
      array[j+1] = tmp
      j -= 1
    end
  end
  array
end

虽然插入排序的的最差时间是O(n^2), 但是对于已经排序好的数组来说, 排序时间只有O(n)

快速排序

快速排序是最简单, 效率最好的通用排序算法之一

快速排序利用了分治法的思想, 取出数组的第一个值, 作为pviot
比pviot小的值放在左边, 大的放在右边
层层递归之后, 数组就排序完成

def quick_sort(array)
  return array if array.size <= 1
  array.shuffle
  left, right = array[1..-1].partition {|n| n <= array.first}
  quick_sort(left) + [array.first] + quick_sort(right)
end

快排的复杂度只有O(n*ln(n)), 与插入排序相比, 速度提高了一个级别
对于已经排序好的数组来说, pviot的取值会导致, 左边的数组的值远远多余右边的数组, 这样会大大降低快排的效率
所以 在排序前打乱数组对快排来说反而是有益的

使用一下代码对插入排序和快速排序测试,

a = Array.new
10000.times {a << rand(999)}
b = a.clone

o = Time.now
insertion_sort a
puts Time.now-o


p = Time.now
quick_sort b
puts Time.now-p

insertion_sort: 2.610087
quick_sort: 0.2639

可以看到两个算法在对大数组排序时的性能差距