所謂排序，即将原來無序的一個序列重新排列成有序的序列。
排序方法中涉及到穩定性，所謂穩定性，是指待排序的序列中有兩個或兩個以上相同的項，在排序前和排序後看這些相同項的相對位置有沒有發生變化，如果沒有發生變化，即該排序方法是穩定的，如果發生變化，則說明該排序方法是不穩定的。
如果記錄中關鍵字不能重複，則排序結果是唯一的，那麼選擇的排序方法穩定與否就無關緊要了；如果關鍵字可以重複，則在選擇排序方法時，就要根據具體的需求來考慮選擇穩定還是不穩定的排序方法。那麼，哪些排序算法是不穩定的呢？
“快些選堆”：其中“快”指快速排序，“些”指希爾排序，“選”指選擇排序，“堆”指堆排序，即這四種排序方法是不穩定的，其他自然都是穩定的。
排序算法分類
1、插入類排序
即在一個已經有序的序列中，插入一個新的記錄，就好比軍訓排隊，已經排好一個縱隊，這時來了個新家夥，于是新來的“插入”這個隊伍中的合适位置。這類排序有：直接插入排序、折半插入排序、希爾排序。
2、交換類排序
該類方法的核心是“交換”，即每趟排序，都是通過一系列的“交換”動作完成的，如軍訓排隊時，教官說：你比旁邊的高，你倆交換下，還比下一個高就繼續交換。這類排序有：冒泡排序、快速排序。
3、選擇類排序
該方法的核心是“選擇”，即每趟排序都選出一個最小（或最大）的記錄，把它和序列中的第一個（或最後一個）記錄交換，這樣最小（或最大）的記錄到位。如軍訓排隊時，教官選出個子最小的同學，讓他和第一個位置的同學交換，剩下的繼續選擇。這類排序有：選擇排序、堆排序。
4、歸并類排序
所謂歸并，就是将兩個或兩個以上的有序序列合并成一個新的有序序列。如軍訓排隊時，教官說：每個人先和旁邊的人組成二人組，組内排好隊，二人組和旁邊的二人組組成四人組，内部再排好隊，以此類推，直到最後全部同學都歸并到一個組中并排好序。這類排序有：（二路）歸并排序。
5、基數類排序
此類方法較為特别，是基于多關鍵字排序的思想，把一個邏輯關鍵字拆分成多個關鍵字，如一副撲克牌，按照基數排序思想可以先按花色排序，則分成4堆，每堆再按a-k的順序排序，使得整副撲克牌最終有序。
排序算法分析
本文主要分析的排序算法有：冒泡排序、選擇排序、插入排序、希爾排序、快速排序、歸并排序、堆排序。
交換算法
由于大部分排序算法中使用到兩個記錄互相交換的動作，是以将交換動作單獨封裝出來，便于各排序算法使用。
//交換函數
array.prototype.swap = function(i, j) {
var temp = this[i];
this[i] = this[j];
this[j] = temp;
}
插入排序
算法思想：每趟将一個待排序的關鍵字，按照其關鍵字值的大小插入到已經排好的部分序列的适當位置上，直到插入完成。
//插入排序
array.prototype.insertionsort = function() {
for (var i = 1; i < this.length; ++i)
{
var j = i,
value = this[i];
while (j > 0 && this[j - 1] > value)
{
this[j] = this[j - 1];
--j;
}
this[j] = value;
}
算法性能：在内層循環中this[j]=this[j-1]，這句是作為基本操作。考慮最壞情況，即整個序列是逆序的，則其基本操作總的執行次數為n*(n-1)/2，其時間複雜度為o(n*n)。考慮最好情況，即整個序列已經有序，則循環内的操作均為常量級，其時間複雜度為o(n)。是以本算法平均時間複雜度為o(n*n)。算法所需的額外空間隻有一個value，是以空間複雜度為o(1)。
希爾排序
算法思想：希爾排序又叫做縮小增量排序，是将待排序的序列按某種規則分成幾個子序列，分别對這幾個子序列進行插入排序，其中這一規則就是增量。如可以使用增量5、3、1來分格序列，且每一趟希爾排序的增量都是逐漸縮小的，希爾排序的每趟排序都會使得整個序列變得更加有序，等整個序列基本有序了，再使用一趟插入排序，這樣會更有效率，這就是希爾排序的思想。
//希爾排序
array.prototype.shellsort = function() {
for (var step = this.length >> 1; step > 0; step >>= 1)
for (var i = 0; i < step; ++i)
for (var j = i + step; j < this.length; j += step)
{
var k = j, value = this[j];
while (k >= step && this[k - step] > value)
{
this[k] = this[k - step];
k -= step;
}
this[k] = value;
}
算法性能：希爾排序的時間複雜度平均情況為o(nlogn)，空間複雜度為o(1)。希爾排序的增量取法要注意，首先增量序列的最後一個值一定是1，其次增量序列中的值沒有除1之外的公因子，如8，4，2，1這樣的序列就不要取（有公因子2）。
冒泡排序
算法思想：通過一系列的“交換”動作完成的，首先第一個記錄與第二個記錄比較，如果第一個大，則二者交換，否則不交換；然後第二個記錄和第三個記錄比較，如果第二個大，則二者交換，否則不交換，以此類推，最終最大的那個記錄被交換到了最後，一趟冒泡排序完成。在這個過程中，大的記錄就像一塊石頭一樣沉底，小的記錄逐漸向上浮動。冒泡排序算法結束的條件是一趟排序沒有發生元素交換。
//冒泡排序
array.prototype.bubblesort = function() {
for (var i = this.length - 1; i > 0; --i)
for (var j = 0; j < i; ++j)
if (this[j] > this[j + 1])
this.swap(j, j + 1);
算法性能：最内層循環的元素交換操作是算法的基本操作。最壞情況，待排序列逆序，則基本操作的總執行次數為(n-1+1)*(n-1)/2=n(n-1)/2，其時間複雜度為o(n*n)；最好情況，待排序列有序，則時間複雜度為o(n)，是以平均情況下的時間複雜度為o(n*n)。算法的額外輔助空間隻有一個用于交換的temp，是以空間複雜度為o(1)。
快速排序
算法思想：以軍訓排隊為例，教官說以第一個同學為中心，比他矮的站他左邊，比他高的站他右邊，這就是一趟快速排序。是以，一趟快速排序是以一個樞軸，将序列分成兩部分，樞軸的一邊比它小（或小于等于），另一邊比它大（或大于等于）。
//遞歸快速排序
array.prototype.quicksort = function(s, e) {
if (s == null)
s = 0;
if (e == null)
e = this.length - 1;
if (s >= e)
return;
this.swap((s + e) >> 1, e);
var index = s - 1;
for (var i = s; i <= e; ++i)
if (this[i] <= this[e]) this.swap(i, ++index);
this.quicksort(s, index - 1);
this.quicksort(index + 1, e);
算法性能：快速排序最好情況下時間複雜度為o(nlogn)，待排序列越接近無序，則該算法效率越高，在最壞情況下時間複雜度為o(n*n)，待排序列越接近有序，則該算法效率越低，算法的平均時間複雜度為o(nlogn)。就平均時間而言，快速排序是所有排序算法中最好的。該算法的空間複雜度為o(logn)，快速排序是遞歸進行的，需要棧的輔助，是以需要的輔助空間比前面幾類排序方法要多。
快速排序的效率和選取的“樞軸”有關，選取的樞軸越接近中間值，算法效率就越高，是以為了提高算法效率，可以在第一次選取“樞軸”時做文章，如在資料堆中随機選取3個值，取3個值的平均值作為“樞軸”，就如抽樣一般。關于具體如何提高快速排序算法的效率，在本文不做詳細介紹了，點到為止。（感興趣的讀者可以自行去研究）
選擇排序
算法思想：該算法的主要動作就是“選擇”，采用簡單的選擇方式，從頭至尾順序掃描序列，找出最小的一個記錄，和第一個記錄交換，接着從剩下的記錄中繼續這種選擇和交換，最終使序列有序。
//選擇排序
array.prototype.selectionsort = function() {
for (var i = 0; i < this.length; ++i)
var index = i;
for (var j = i + 1; j < this.length; ++j)
if (this[j] < this[index])
index = j;
this.swap(i, index);
算法性能：将最内層循環中的比較視為基本操作，其執行次數為(n-1+1)*(n-1)/2=n(n-1)/2，其時間複雜度為o(n*n)，本算法的額外空間隻有一個temp，是以空間複雜度為o(1)。
堆排序
算法思想：堆是一種資料結構，最好的了解堆的方式就是把堆看成一棵完全二叉樹，這個完全二叉樹滿足任何一個非葉節點的值，都不大于（或不小于）其左右孩子節點的值。若父親大孩子小，則這樣的堆叫做大頂堆；若父親小孩子大，這樣的堆叫做小頂堆。根據堆的定義，其根節點的值是最大（或最小），是以将一個無序序列調整為一個堆，就可以找出這個序列的最大（或最小）值，然後将找出的這個值交換到序列的最後（或最前），這樣有序序列元素增加1個，無序序列中元素減少1個，對新的無序序列重複這樣的操作，就實作了序列排序。堆排序中最關鍵的操作是将序列調整為堆，整個排序的過程就是通過不斷調整使得不符合堆定義的完全二叉樹變為符合堆定義的完全二叉樹的過程。
堆排序執行過程（大頂堆）：
（1）從無序序列所确定的完全二叉樹的第一個非葉子節點開始，從右至左，從下至上，對每個節點進行調整，最終将得到一個大頂堆。将目前節點（a）的值與其孩子節點進行比較，如果存在大于a值的孩子節點，則從中選出最大的一個與a交換。當a來到下一層的時候重複上述過程，直到a的孩子節點值都小于a的值為止。
（2）将目前無序序列中第一個元素，在樹中是根節點（a）與無序序列中最後一個元素（b）交換。a進入有序序列，到達最終位置，無序序列中元素減少1個，有序序列中元素增加1個，此時隻有節點b可能不滿足堆的定義，對其進行調整。
（3）重複過程2，直到無序序列中的元素剩下1個時排序結束。
//堆排序
array.prototype.heapsort = function() {
for (var j = i, k = (j - 1) >> 1; k >= 0; j = k, k = (k - 1) >> 1)
if (this[k] >= this[j])
break;
this.swap(j, k);
this.swap(0, i);
for (var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1)
if (k == i || this[k] < this[k - 1])
--k;
if (this[k] <= this[j])
算法性能：完全二叉樹的高度為[log(n+1)]，即對每個節點調整的時間複雜度為o(logn)，基本操作總次數是兩個并列循環中基本操作次數相加，則整個算法時間複雜度為o(logn)*n/2+o(logn)*(n-1)，即o(nlogn)。額外空間隻有一個temp，是以空間複雜度為o(1)。
堆排序的優點是适合記錄數很多的場景，如從1000000個記錄中選出前10個最小的，這種情況用堆排序最好，如果記錄數較少，則不提倡使用堆排序。另外，hash表+堆排序是處理海量資料的絕佳組合，關于海量資料處理會在之後的博文中介紹到。
歸并排序
算法思想：其核心就是“兩兩歸并”，首先将原始序列看成每個隻含有單獨1個元素的子序列，兩兩歸并，形成若幹有序二進制組，則第一趟歸并排序結束，再将這個序列看成若幹個二進制組子序列，繼續兩兩歸并，形成若幹有序四元組，則第二趟歸并排序結束，以此類推，最後隻有兩個子序列，再進行一次歸并，即完成整個歸并排序。
//歸并排序
array.prototype.mergesort = function(s, e, b) {
if (b == null)
b = new array(this.length);
var m = (s + e) >> 1;
this.mergesort(s, m, b);
this.mergesort(m + 1, e, b);
for (var i = s, j = s, k = m + 1; i <= e; ++i)
b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++];
for (var i = s; i <= e; ++i)
this[i] = b[i];
算法性能：可以選取“歸并操作”作為基本操作，“歸并操作”即為将待歸并表中元素複制到一個存儲歸并結果的表中的過程，其次數為要歸并的兩個子序列中元素個數之和。算法總共需要進行logn趟排序，每趟排序執行n次基本操作，是以整個歸并排序中總的基本操作執行次數為nlogn，即時間複雜度為o(nlogn)，說明歸并排序時間複雜度和初始序列無關。由于歸并排序需要轉存整個待排序列，是以空間複雜度為o(n)。
一些結論
（1）快速排序、希爾排序、歸并排序、堆排序的平均時間為o(nlogn)，其他的為o(n*n)。
（2）快速排序、希爾排序、選擇排序、堆排序不穩定，其他的穩定。
（3）經過一趟排序能夠保證一個元素到達最終位置的是冒泡排序、快速排序、選擇排序、堆排序。
（4）元素比較次數和原始序列無關的是選擇排序、折半插入排序。
（5）排序趟數和原始序列有關的是交換類排序。
（6）直接插入排序和折半插入排序的差別是尋找插入位置的方式不同，一個是按順序查找方式，另一個是按折半查找方式。
作者：twobin
來源：51cto