在上一篇文章《Javascript-數組亂序》中我們提到不同浏覽器采用不同的排序算法來實作Array.prototype.sort方法，今天我們一起來學習常見的幾種排序算法。
我們常說的十大經典排序算法有：冒泡排序、選擇排序、插入排序、希爾排序、歸并排序、快速排序、堆排序、計數排序、桶排序、基數排序。
上面的十種排序算法可以分為兩類：
比較類排序：通過比較來決定元素間的相對次序，由于其時間複雜度不能突破 O(nlogn)，是以也稱為非線性時間比較類排序。
非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運作，是以也稱為線性時間非比較類排序。
每個排序算法屬于哪一類如下圖所示：
在上圖中我們标注了每個算法是否穩定，那麼如何區分穩定和不穩定？
穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。
不穩定：如果a原本在b前面，而a=b，排序之後a可能會出現在b的後面。
冒泡排序（Bubble Sort）也是一種簡單直覺的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。
冒泡排序還有一種優化算法，就是立一個 flag，當在一趟序列周遊中元素沒有發生交換，則證明該序列已經有序。但這種改進對于提升性能來說并沒有什麼太大作用。
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
針對所有的元素重複以上的步驟，除了最後一個。
持續每次對越來越少的元素重複上面的步驟1-3，直到沒有任何一對數字需要比較。
JavaScript 代碼實作
選擇排序（Selection sort）是一種簡單直覺的排序算法，無論什麼資料進去都是 O(n²) 的時間複雜度。是以用到它的時候，資料規模越小越好。唯一的好處可能就是不占用額外的記憶體空間了吧。
其算法思想：從數組中選擇最小元素，并将其與第一個元素交換位置。再從數組中剩下的元素中選擇出最小元素，将其與數組的第二個元素交換位置。不斷進行這樣的操作，直到将整個數組排序。
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
重複步驟2，直到所有元素均排序完畢。
JavaScript代碼實作：
插入排序（Insertion sort）是一種最簡單直覺的排序算法，它的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。
插入排序的時間複雜度取決于數組的初始順序，如果數組已經部分有序了，那麼逆序較少，需要的交換次數也就較少，時間複雜度較低。
平均情況下插入排序需要 N^2/4 比較以及 N^2/4 次交換；
最壞的情況下需要 N^2/2 比較以及 N^2/2 次交換，最壞的情況是數組是倒序的；
最好的情況下需要 N-1 次比較和 0 次交換，最好的情況就是數組已經有序了。
從第一個元素開始，該元素可以認為已經被排序；
取出下一個元素，在已經排序的元素序列中從後向前掃描；
如果該元素（已排序）大于新元素，将該元素移到下一位置；
重複步驟3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到該位置後；
重複步驟2~5。
JavaScript代碼實作
對于大規模的數組，插入排序很慢，因為它隻能交換相鄰的元素，每次隻能将逆序數量減1。希爾排序的出現就是為了解決插入排序的這種局限性，它通過交換不相鄰的元素，每次可以将逆序數量減少大于1。
希爾排序(Shell's Sort)，也稱為遞減增量排序算法，是插入排序的一種更高效的改進版本，但希爾排序是非穩定排序算法。
希爾排序使用插入排序對間隔h的序列進行排序。通過不斷減小h，最後令h=1，就可以使得整個數組是有序的。
希爾排序的運作時間達不到平方級别，使用遞增序列1,4,10,20...的希爾排序所需要的比較次數不會超過N的若幹倍乘以遞增序列的長度。後面介紹的進階排序算法隻會比希爾排序快兩倍左右。
選擇一個增量序列 t1, t2, ..., tk，其中ti > tj, tk = 1;
按增量序列個數k，對序列進行k趟排序；
每趟排序，根據對應的增量ti， 将待排序列分割為若幹長度為m的子序列，分别對各子表進行直接插入排序。僅增量因子為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。
javascript實作
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為2-路歸并。
歸并排序是一種穩定的排序方法，和選擇排序一樣，性能不受輸入資料的影響，但表現比選擇排序好很多，因為時間複雜度始終都是O(nlogn)，代價就是需要額外的記憶體空間。
把長度為n的輸入序列分為兩個長度為n/2的子序列；
對這兩個子序列分别采用歸并排序；
将兩個排好序的子序列合并成一個最終的排序序列。
JavaScript
我們先學習上面五種排序算法，另外五種下次再繼續。