插入排序
插入排序的灵感也许来自于扑克牌, 将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
可以看到两个算法在对大数组排序时的性能差距
