*稳定指原本数列中相同的元素的相对前后位置在排序后不会被打乱
快速排序（n*lgn 不稳定）：数组中随机选取一个数x（这里选择最后一个），将数组按比x大的和x小的分成两部分，再对剩余两部分重复这个算法直到结束。但在数据量小的时候表现差。
def quick_sort(a)
(x = a.pop) ? quick_sort(a.select{|i| i <= x}) + [x] + quick_sort(a.select{|i| i > x}) : []
end
冒泡排序（n^2 稳定）：如果a[n] > a[n+1] 则调换，冒泡排序一遍后的最大的值会被放在最后，然后依次对前n-1项再进行冒泡排序。
def bubble_sort(a)
(a.length-2).downto(0) {|i| i.times{|j| a[j],a[j+1] = a[j+1],a[j] if a[j]>a[j+1]}}
end
选择排序（n^2 不稳定）：在n中选择最小值插入数组前端，然后再在后n-1项中找最小值放在数组第二个。
def selection_sort(a)
a.length.times do |i|
t = a.index(a[i..-1].min) #select the index of the next smallest element
a[i], a[t] = a[t], a[i] #swap
end
end
插入排序 （n^2 稳定）：在数组开始处新建一个排序好的数组，然后对于之后的每个新扫描的值，插入之前排序好的数组的相应位置。
def insertion_sort(a)
(1...a.length).each do |i|
if a[i-1] > a[i]
temp = a[i] #store the number to be inserted
j = i
while j > 0 and a[j-1] > temp
a[j] = a[j-1] #move every elements in the array which is greater than the inserted number forward
j -= 1
end
a[j] = temp #insert the number
end
end
end