*穩定指原本數列中相同的元素的相對前后位置在排序后不會被打亂

快速排序（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 elementa[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 insertedj = iwhile j > 0 and a[j-1] > tempa[j] = a[j-1] #move every elements in the array which is greater than the inserted number forwardj -= 1enda[j] = temp #insert the number endend end

轉載于:https://www.cnblogs.com/lilixu/p/4587307.html

總結

以上是生活随笔為你收集整理的Basic Sorting Algorithms的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。