所謂排序，即將原來(lái)無(wú)序的一個(gè)序列重新排列成有序的序列。

排序方法中涉及到穩(wěn)定性，所謂穩(wěn)定性，是指待排序的序列中有兩個(gè)或兩個(gè)以上相同的項(xiàng)，在排序前和排序后看這些相同項(xiàng)的相對(duì)位置有沒有發(fā)生變化，如果沒有發(fā)生變化，即該排序方法是穩(wěn)定的，如果發(fā)生變化，則說(shuō)明該排序方法是不穩(wěn)定的。

如果記錄中關(guān)鍵字不能重復(fù)，則排序結(jié)果是唯一的，那么選擇的排序方法穩(wěn)定與否就無(wú)關(guān)緊要了；如果關(guān)鍵字可以重復(fù)，則在選擇排序方法時(shí)，就要根據(jù)具體的需求來(lái)考慮選擇穩(wěn)定還是不穩(wěn)定的排序方法。那么，哪些排序算法是不穩(wěn)定的呢？

“快些選堆”：其中“快”指快速排序，“些”指希爾排序，“選”指選擇排序，“堆”指堆排序，即這四種排序方法是不穩(wěn)定的，其他自然都是穩(wěn)定的。

排序算法分類

1、插入類排序

即在一個(gè)已經(jīng)有序的序列中，插入一個(gè)新的記錄，就好比軍訓(xùn)排隊(duì)，已經(jīng)排好一個(gè)縱隊(duì)，這時(shí)來(lái)了個(gè)新家伙，于是新來(lái)的“插入”這個(gè)隊(duì)伍中的合適位置。這類排序有：直接插入排序、折半插入排序、希爾排序。

2、交換類排序

該類方法的核心是“交換”，即每趟排序，都是通過(guò)一系列的“交換”動(dòng)作完成的，如軍訓(xùn)排隊(duì)時(shí)，教官說(shuō)：你比旁邊的高，你倆交換下，還比下一個(gè)高就繼續(xù)交換。這類排序有：冒泡排序、快速排序。

3、選擇類排序

該方法的核心是“選擇”，即每趟排序都選出一個(gè)最小（或***）的記錄，把它和序列中的***個(gè)（或***一個(gè)）記錄交換，這樣最小（或***）的記錄到位。如軍訓(xùn)排隊(duì)時(shí)，教官選出個(gè)子最小的同學(xué)，讓他和***個(gè)位置的同學(xué)交換，剩下的繼續(xù)選擇。這類排序有：選擇排序、堆排序。

4、歸并類排序

所謂歸并，就是將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)新的有序序列。如軍訓(xùn)排隊(duì)時(shí)，教官說(shuō)：每個(gè)人先和旁邊的人組成二人組，組內(nèi)排好隊(duì)，二人組和旁邊的二人組組成四人組，內(nèi)部再排好隊(duì)，以此類推，直到***全部同學(xué)都?xì)w并到一個(gè)組中并排好序。這類排序有：（二路）歸并排序。

5、基數(shù)類排序

此類方法較為特別，是基于多關(guān)鍵字排序的思想，把一個(gè)邏輯關(guān)鍵字拆分成多個(gè)關(guān)鍵字，如一副撲克牌，按照基數(shù)排序思想可以先按花色排序，則分成4堆，每堆再按A-K的順序排序，使得整副撲克牌最終有序。

排序算法分析

本文主要分析的排序算法有：冒泡排序、選擇排序、插入排序、希爾排序、快速排序、歸并排序、堆排序。

交換算法

由于大部分排序算法中使用到兩個(gè)記錄相互交換的動(dòng)作，因此將交換動(dòng)作單獨(dú)封裝出來(lái)，便于各排序算法使用。

//交換函數(shù) 
Array.prototype.swap = function(i, j) {  
  var temp = this[i];  
   this[i] = this[j];  
   this[j] = temp;  
} 

插入排序

算法思想：每趟將一個(gè)待排序的關(guān)鍵字，按照其關(guān)鍵字值的大小插入到已經(jīng)排好的部分序列的適當(dāng)位置上，直到插入完成。

//插入排序 
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;  
    }  
} 

算法性能：在內(nèi)層循環(huán)中this[j]=this[j-1]，這句是作為基本操作。考慮最壞情況，即整個(gè)序列是逆序的，則其基本操作總的執(zhí)行次數(shù)為n*(n-1)/2，其時(shí)間復(fù)雜度為O(n*n)。考慮***情況，即整個(gè)序列已經(jīng)有序，則循環(huán)內(nèi)的操作均為常量級(jí)，其時(shí)間復(fù)雜度為O(n)。因此本算法平均時(shí)間復(fù)雜度為O(n*n)。算法所需的額外空間只有一個(gè)value，因此空間復(fù)雜度為O(1)。

希爾排序

算法思想：希爾排序又叫做縮小增量排序，是將待排序的序列按某種規(guī)則分成幾個(gè)子序列，分別對(duì)這幾個(gè)子序列進(jìn)行插入排序，其中這一規(guī)則就是增量。如可以使用增量5、3、1來(lái)分格序列，且每一趟希爾排序的增量都是逐漸縮小的，希爾排序的每趟排序都會(huì)使得整個(gè)序列變得更加有序，等整個(gè)序列基本有序了，再使用一趟插入排序，這樣會(huì)更有效率，這就是希爾排序的思想。

//希爾排序 
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;  
            }  
        }  
    }  
} 

算法性能：希爾排序的時(shí)間復(fù)雜度平均情況為O(nlogn)，空間復(fù)雜度為O(1)。希爾排序的增量取法要注意，首先增量序列的***一個(gè)值一定是1，其次增量序列中的值沒有除1之外的公因子，如8，4，2，1這樣的序列就不要取（有公因子2）。

冒泡排序

算法思想：通過(guò)一系列的“交換”動(dòng)作完成的，首先***個(gè)記錄與第二個(gè)記錄比較，如果***個(gè)大，則二者交換，否則不交換；然后第二個(gè)記錄和第三個(gè)記錄比較，如果第二個(gè)大，則二者交換，否則不交換，以此類推，最終***的那個(gè)記錄被交換到了***，一趟冒泡排序完成。在這個(gè)過(guò)程中，大的記錄就像一塊石頭一樣沉底，小的記錄逐漸向上浮動(dòng)。冒泡排序算法結(jié)束的條件是一趟排序沒有發(fā)生元素交換。

//冒泡排序 
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èi)層循環(huán)的元素交換操作是算法的基本操作。最壞情況，待排序列逆序，則基本操作的總執(zhí)行次數(shù)為(n-1+1)*(n-1)/2=n(n-1)/2，其時(shí)間復(fù)雜度為O(n*n)；***情況，待排序列有序，則時(shí)間復(fù)雜度為O(n)，因此平均情況下的時(shí)間復(fù)雜度為O(n*n)。算法的額外輔助空間只有一個(gè)用于交換的temp，所以空間復(fù)雜度為O(1)。

快速排序

算法思想：以軍訓(xùn)排隊(duì)為例，教官說(shuō)以***個(gè)同學(xué)為中心，比他矮的站他左邊，比他高的站他右邊，這就是一趟快速排序。因此，一趟快速排序是以一個(gè)樞軸，將序列分成兩部分，樞軸的一邊比它小（或小于等于），另一邊比它大（或大于等于）。

//遞歸快速排序 
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);  
} 

算法性能：快速排序***情況下時(shí)間復(fù)雜度為O(nlogn)，待排序列越接近無(wú)序，則該算法效率越高，在最壞情況下時(shí)間復(fù)雜度為O(n*n)，待排序列越接近有序，則該算法效率越低，算法的平均時(shí)間復(fù)雜度為O(nlogn)。就平均時(shí)間而言，快速排序是所有排序算法中***的。該算法的空間復(fù)雜度為O(logn)，快速排序是遞歸進(jìn)行的，需要棧的輔助，因此需要的輔助空間比前面幾類排序方法要多。

快速排序的效率和選取的“樞軸”有關(guān)，選取的樞軸越接近中間值，算法效率就越高，因此為了提高算法效率，可以在***次選取“樞軸”時(shí)做文章，如在數(shù)據(jù)堆中隨機(jī)選取3個(gè)值，取3個(gè)值的平均值作為“樞軸”，就如抽樣一般。關(guān)于具體如何提高快速排序算法的效率，在本文不做詳細(xì)介紹了，點(diǎn)到為止。（感興趣的讀者可以自行去研究）

選擇排序

算法思想：該算法的主要?jiǎng)幼骶褪?ldquo;選擇”，采用簡(jiǎn)單的選擇方式，從頭至尾順序掃描序列，找出最小的一個(gè)記錄，和***個(gè)記錄交換，接著從剩下的記錄中繼續(xù)這種選擇和交換，最終使序列有序。

//選擇排序 
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èi)層循環(huán)中的比較視為基本操作，其執(zhí)行次數(shù)為(n-1+1)*(n-1)/2=n(n-1)/2，其時(shí)間復(fù)雜度為O(n*n)，本算法的額外空間只有一個(gè)temp，因此空間復(fù)雜度為O(1)。

堆排序

算法思想：堆是一種數(shù)據(jù)結(jié)構(gòu)，***的理解堆的方式就是把堆看成一棵完全二叉樹，這個(gè)完全二叉樹滿足任何一個(gè)非葉節(jié)點(diǎn)的值，都不大于（或不小于）其左右孩子節(jié)點(diǎn)的值。若父親大孩子小，則這樣的堆叫做大頂堆；若父親小孩子大，這樣的堆叫做小頂堆。根據(jù)堆的定義，其根節(jié)點(diǎn)的值是***（或最小），因此將一個(gè)無(wú)序序列調(diào)整為一個(gè)堆，就可以找出這個(gè)序列的***（或最小）值，然后將找出的這個(gè)值交換到序列的***（或最前），這樣有序序列元素增加1個(gè)，無(wú)序序列中元素減少1個(gè)，對(duì)新的無(wú)序序列重復(fù)這樣的操作，就實(shí)現(xiàn)了序列排序。堆排序中最關(guān)鍵的操作是將序列調(diào)整為堆，整個(gè)排序的過(guò)程就是通過(guò)不斷調(diào)整使得不符合堆定義的完全二叉樹變?yōu)榉隙讯x的完全二叉樹的過(guò)程。

堆排序執(zhí)行過(guò)程（大頂堆）：

（1）從無(wú)序序列所確定的完全二叉樹的***個(gè)非葉子節(jié)點(diǎn)開始，從右至左，從下至上，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行調(diào)整，最終將得到一個(gè)大頂堆。將當(dāng)前節(jié)點(diǎn)（a）的值與其孩子節(jié)點(diǎn)進(jìn)行比較，如果存在大于a值的孩子節(jié)點(diǎn)，則從中選出***的一個(gè)與a交換。當(dāng)a來(lái)到下一層的時(shí)候重復(fù)上述過(guò)程，直到a的孩子節(jié)點(diǎn)值都小于a的值為止。

（2）將當(dāng)前無(wú)序序列中***個(gè)元素，在樹中是根節(jié)點(diǎn)（a）與無(wú)序序列中***一個(gè)元素（b）交換。a進(jìn)入有序序列，到達(dá)最終位置，無(wú)序序列中元素減少1個(gè)，有序序列中元素增加1個(gè)，此時(shí)只有節(jié)點(diǎn)b可能不滿足堆的定義，對(duì)其進(jìn)行調(diào)整。

（3）重復(fù)過(guò)程2，直到無(wú)序序列中的元素剩下1個(gè)時(shí)排序結(jié)束。

//堆排序 
Array.prototype.heapSort = function() {  
    for (var i = 1; i < this.length; ++i)  
        {  
        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);  
        }  
    }  
    for (var i = this.length - 1; i > 0; --i)  
    {  
        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]) 
                break;  
            this.swap(j, k);  
        }  
    }  
} 

算法性能：完全二叉樹的高度為[log(n+1)]，即對(duì)每個(gè)節(jié)點(diǎn)調(diào)整的時(shí)間復(fù)雜度為O(logn)，基本操作總次數(shù)是兩個(gè)并列循環(huán)中基本操作次數(shù)相加，則整個(gè)算法時(shí)間復(fù)雜度為O(logn)*n/2+O(logn)*(n-1)，即O(nlogn)。額外空間只有一個(gè)temp，因此空間復(fù)雜度為O(1)。

堆排序的優(yōu)點(diǎn)是適合記錄數(shù)很多的場(chǎng)景，如從1000000個(gè)記錄中選出前10個(gè)最小的，這種情況用堆排序***，如果記錄數(shù)較少，則不提倡使用堆排序。另外，Hash表+堆排序是處理海量數(shù)據(jù)的***組合，關(guān)于海量數(shù)據(jù)處理會(huì)在之后的博文中介紹到。

歸并排序

算法思想：其核心就是“兩兩歸并”，首先將原始序列看成每個(gè)只含有單獨(dú)1個(gè)元素的子序列，兩兩歸并，形成若干有序二元組，則***趟歸并排序結(jié)束，再將這個(gè)序列看成若干個(gè)二元組子序列，繼續(xù)兩兩歸并，形成若干有序四元組，則第二趟歸并排序結(jié)束，以此類推，***只有兩個(gè)子序列，再進(jìn)行一次歸并，即完成整個(gè)歸并排序。

//歸并排序 
Array.prototype.mergeSort = function(s, e, b) {  
    if (s == null) 
        s = 0;  
    if (e == null) 
        e = this.length - 1;  
    if (b == null) 
        b = new Array(this.length);  
    if (s >= e) 
        return;  
    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];  
} 

算法性能：可以選取“歸并操作”作為基本操作，“歸并操作”即為將待歸并表中元素復(fù)制到一個(gè)存儲(chǔ)歸并結(jié)果的表中的過(guò)程，其次數(shù)為要?dú)w并的兩個(gè)子序列中元素個(gè)數(shù)之和。算法總共需要進(jìn)行l(wèi)ogn趟排序，每趟排序執(zhí)行n次基本操作，因此整個(gè)歸并排序中總的基本操作執(zhí)行次數(shù)為nlogn，即時(shí)間復(fù)雜度為O(nlogn)，說(shuō)明歸并排序時(shí)間復(fù)雜度和初始序列無(wú)關(guān)。由于歸并排序需要轉(zhuǎn)存整個(gè)待排序列，因此空間復(fù)雜度為O(n)。

一些結(jié)論

（1）快速排序、希爾排序、歸并排序、堆排序的平均時(shí)間為O(nlogn)，其他的為O(n*n)。

（2）快速排序、希爾排序、選擇排序、堆排序不穩(wěn)定，其他的穩(wěn)定。

（3）經(jīng)過(guò)一趟排序能夠保證一個(gè)元素到達(dá)最終位置的是冒泡排序、快速排序、選擇排序、堆排序。

（4）元素比較次數(shù)和原始序列無(wú)關(guān)的是選擇排序、折半插入排序。

（5）排序趟數(shù)和原始序列有關(guān)的是交換類排序。

（6）直接插入排序和折半插入排序的區(qū)別是尋找插入位置的方式不同，一個(gè)是按順序查找方式，另一個(gè)是按折半查找方式。