最基礎(chǔ)的算法問題，溫故知新。排序算法的幾個主要指標(biāo)是，時(shí)間復(fù)雜度（最好，最差和平均），空間復(fù)雜度（額外空間）和穩(wěn)定性。本文主要描述八種常見算法：簡單選擇排序、冒泡排序、簡單插入排序、希爾排序、歸并排序、快速排序、堆排序和基數(shù)排序，關(guān)于它們的指標(biāo)統(tǒng)計(jì)可以直接看最后。本文均為基本C++實(shí)現(xiàn)，不使用STL庫。

值得一提的是排序算法的穩(wěn)定性，之前關(guān)注較少。穩(wěn)定性的意思是對于序列中鍵值（Key value）相同的元素，它們在排序前后的相對關(guān)系保持不變。對于int這樣的基本數(shù)據(jù)類型，穩(wěn)定性基本上是沒有意義的，因?yàn)樗逆I值就是元素本身，兩個元素的鍵值相同他們就可以被認(rèn)為是相同的。但對于復(fù)雜的數(shù)據(jù)類型，數(shù)據(jù)的鍵值相同，數(shù)據(jù)不一定相同，比如一個Student類，包括Name和Score兩個屬性，以Score為鍵值排序，這時(shí)候鍵值相同元素間的相對關(guān)系就有意義了。

簡單選擇排序

應(yīng)該是最自然的思路。選擇排序的思想是，從全部序列中選取最小的，與第0個元素交換，然后從第1個元素往后找出最小的，與第一個元素交換，再從第2個元素往后選取最小的，與第2個元素交換，直到選取最后一個元素。

無論如何都要完整地執(zhí)行內(nèi)外兩重循環(huán)，故最好、最差和平均時(shí)間復(fù)雜度都是O(n²)，不需要額外空間。選擇排序是不穩(wěn)定的。

冒泡排序

冒泡排序的思想是，從第0個元素到第n-1個元素遍歷，若前面一個元素大于后面一個元素，則交換兩個元素，這樣可將整個序列中最大的元素冒泡到最后，然后再從第0個到第n-2遍歷，如此往復(fù)，直到只剩一個元素。

void bubbleSort(int a[], int n) {    for (int i = 0; i < n - 1; ++i) {        for (int j = 0; j < n - i - 1; ++j) {            if (a[j] > a[j + 1]) {                int tmp = a[j];                a[j] = a[j + 1];                a[j + 1] = tmp;            }        }    }}

冒泡排序與簡單選擇排序類似，無論如何都要執(zhí)行完兩重循環(huán)，故最好、最壞和平均時(shí)間復(fù)雜度均為O(n²)，不需要額外空間。冒泡排序是穩(wěn)定的。
冒泡排序的一個改進(jìn)是，在內(nèi)層循環(huán)之前設(shè)置一個標(biāo)記變量，用于標(biāo)記循環(huán)是否進(jìn)行了交換，在內(nèi)層循環(huán)結(jié)束時(shí)，若判斷沒有進(jìn)行交換，則說明剩下的序列中，每個元素都小于等于后面一個元素，即已經(jīng)有序，可終止循環(huán)。這樣，冒泡排序的最好時(shí)間復(fù)雜度可以提升到O(n)。

簡單插入排序（Insertion Sort）

思路是類似撲克牌的排序，每次從未排序序列的第一個元素，插入到已排序序列中的合適位置。假設(shè)初始的有序序列為第0個元素（本文描述的序號都從0開始），只有一個元素的序列肯定是有序的，然后從原先序列的第1個元素開始到第n-1個元素遍歷，每次將當(dāng)前元素插入到它之前序列中的合適位置。

兩重循環(huán)，最差和平均時(shí)間復(fù)雜度為O(n²)，最好情況是原序列已有序，則忽略內(nèi)層循環(huán)，時(shí)間復(fù)雜度O(n)。插入排序是穩(wěn)定的。
這里，內(nèi)層循環(huán)我們用的是從后向前遍歷，來找到合適的插入位置，而內(nèi)層循環(huán)所遍歷的，是已排序的數(shù)組，所以我們可以使用二分查找來尋找插入位置，從而使時(shí)間復(fù)雜度提高到O(n*log n)。代碼如下。

// 二分查找改進(jìn)的插入排序void insertionSortBSearch(int a[], n) {    for (int i = 1; i < n; ++i) {         int j, val = a[i];         int begin = 0, end = i - 1;        while (begin < end) {            int mid = begin + (end - begin) / 2;            if (a[mid] > val) {                end = mid - 1;            }            else {                begin = mid;            }        }        for (j = i - 1; j >= begin; --j) {            a[j + 1] = a[j];        }        a[begin] = val;    }}

希爾排序

希爾排序可以被認(rèn)為是簡單插入排序的一種改進(jìn)。插入排序一個比較耗時(shí)的地方在于需要將元素反復(fù)后移，因?yàn)樗且?為增量進(jìn)行比較的元素的后移可能會進(jìn)行多次。一個長度為n的序列，以1為增量就是一個序列，以2為增量就形成兩個序列，以i為增量就形成i個序列。希爾排序的思想是，先以一個較大的增量，將序列分成幾個子序列，將這幾個子序列分別排序后，合并，在縮小增量進(jìn)行同樣的操作，知道增量為1時(shí)，序列已經(jīng)基本有序，這是進(jìn)行簡單插入排序的效率就會較高。希爾排序的維基詞條上有一個比較好的解釋例子如下：

上面的例子中，我們依次選取了5、3和1為增量，實(shí)際中增量的選取并沒有統(tǒng)一的規(guī)則，唯一的要求就是最后一次迭代的增量需為1。最初的增量選取規(guī)則為，從n/2折半遞減直到1。還有一些關(guān)于希爾排序增量選取的研究，針對不同數(shù)據(jù)有不同的表現(xiàn)，在此不做展開。下面是增量從n/2折半遞減到1的代碼示例。

void shellSort(int a[], int n) {    for (int step = n / 2; step > 0; step /= 2) {        for (int i = step; i < n; ++i) {            int j, val = a[i];            for (j = n - step; j >= 0 && a[j] > val; j -= step) {                a[j + step] = a[j];            }            a[j + 1] = val;        }    }}

希爾排序在簡單插入排序的基礎(chǔ)上做了些改進(jìn)，它的最好及最差時(shí)間復(fù)雜度和簡單插入排序一樣，分別是是O(n)和O(n²)，平均時(shí)間復(fù)雜度試增量選取規(guī)則而定，一般認(rèn)為介于O(n)和O(n²)之間。它不需要額外空間。它是不穩(wěn)定的。

歸并排序

歸并排序的思想是，利用二分的特性，將序列分成兩個子序列進(jìn)行排序，將排序后的兩個子序列歸并（合并），當(dāng)序列的長度為2時(shí)，它的兩個子序列長度為1，即視為有序，可直接合并，即達(dá)到歸并排序的最小子狀態(tài)?；谶f歸的實(shí)現(xiàn)如下：

歸并排序的最好，最壞和平均時(shí)間復(fù)雜度都是O(n*logn)。但需要O(n)的輔助空間。歸并排序是穩(wěn)定的。

快速排序

快速排序可能是最常被提到的排序算法了，快排的思想是，選取第一個數(shù)為基準(zhǔn)，通過一次遍歷將小于它的元素放到它的左側(cè)，將大于它的元素放到它的右側(cè)，然后對它的左右兩個子序列分別遞歸地執(zhí)行同樣的操作。

void quickSortRecursive(int a[], int start, int end) {    if (start >= end)        return;    int mid = a[start];    int left = start + 1, right = end;    while (left < right) {        while (a[left] <= mid && left < right)            ++left;        while (a[right] > mid && left < right)            --right;        swap(a[left], a[right]);    }    if (a[left] <= a[start])        swap(a[left], a[start]);    else        --left;    if (left)        quickSortRecursive(a, start, left - 1);    quickSortRecursive(a, left + 1, end);}void quickSort(int a[], int n) {    quickSortRecursive(a, 0, n - 1);}

快速排序利用分而治之的思想，它的最好和平均實(shí)際復(fù)雜度為O(nlogn)，但是，如果選取基準(zhǔn)的規(guī)則正好與實(shí)際數(shù)值分布相反，例如我們選取第一個數(shù)為基準(zhǔn)，而原始序列是倒序的，那么每一輪循環(huán)，快排都只能把基準(zhǔn)放到最右側(cè)，故快排的最差時(shí)間復(fù)雜度為O(n²)?？炫潘惴ū旧頉]有用到額外的空間，可以說需要的空間為O(1)；對于遞歸實(shí)現(xiàn)，也可以說需要的空間是O(n)，因?yàn)樵谶f歸調(diào)用時(shí)有棧的開銷，當(dāng)然最壞情況是O(n)，平均情況是O(logn)?？焖倥判蚴遣环€(wěn)定的。

堆排序

堆排序利用的是二叉樹的思想，所謂堆就是一個完全二叉樹，完全二叉樹的意思就是，除了葉子節(jié)點(diǎn)，其它所有節(jié)點(diǎn)都有兩個子節(jié)點(diǎn)，這樣子的話，完全二叉樹就可以用一個一塊連續(xù)的內(nèi)存空間（數(shù)組）來存儲，而不需要指針操作了。堆排序分兩個流程，首先是構(gòu)建大頂堆，然后是從大頂堆中獲取按逆序提取元素。
首先是大頂堆，大頂堆即一個完全二叉樹，的每一個節(jié)點(diǎn)都大于它的所有子節(jié)點(diǎn)。大頂堆可以按照從上到下從左到右的順序，用數(shù)組來存儲，第i個節(jié)點(diǎn)的父節(jié)點(diǎn)序號為(i-1)/2，左子節(jié)點(diǎn)序號為2i+1，右子節(jié)點(diǎn)序號為2(i+1)。構(gòu)建大頂堆的過程即從后向前遍歷所有非葉子節(jié)點(diǎn)，若它小于左右子節(jié)點(diǎn)，則與左右子節(jié)點(diǎn)中最大的交換，然后遞歸地對原最大節(jié)點(diǎn)做同樣的操作。下面是一個較好的示意圖來自bubkoo：

構(gòu)建大頂堆示意圖

從大頂堆逆序提取元素使其有序示意圖

堆排序的整個過程中充分利用的二分思想，它的最好、最壞和平均時(shí)間復(fù)雜度都是O(nlogn)。堆排序不需要額外的空間。堆排序的交換過程不連續(xù)，顯然是不穩(wěn)定的。

基數(shù)排序

基數(shù)排序是一種典型的空間換時(shí)間的排序方法。以正整數(shù)為例，將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位（個位）排序一直到最高位排序完成以后，數(shù)列就變成一個有序序列。
對正整數(shù)我們常以10為基數(shù)，每一位可以為0到9，對于其它數(shù)據(jù)類型如字符串，我們可以進(jìn)一步拓展基數(shù)，基數(shù)越大越占空間，但時(shí)間更快，如果有一段足夠長的內(nèi)存空間，也就是說基數(shù)為無窮大，那就足夠表示所有出現(xiàn)的數(shù)值，我們就可以通過一次遍歷就實(shí)現(xiàn)排序，當(dāng)然實(shí)現(xiàn)上這是不可能的（對已知輸入范圍的數(shù)據(jù)是可能的，而且非常有用的，可以用這種思想來模擬一個簡單的hash函數(shù)）。

int maxBit(int a[], int n){    int maxData = a[0];         for (int i = 1; i < n; ++i)    {        if (maxData < a[i]) {            maxData = a[i];        }       }    int d = 1;    int p = 10;    while (maxData >= p)    {        maxData /= 10;        ++d;    }    return d;}void radixsort(int a[], int n){    int d = maxBit(a, n);    int *tmp = new int[n];    int *count = new int[10];    int i, j, k;    int radix = 1;    for (i = 1; i <= d; i++, radix *= 10)    {        for (j = 0; j < 10; j++) {            count[j] = 0;        }           for (j = 0; j < n; j++)        {            k = (a[j] / radix) % 10;            count[k]++;        }        for (j = 1; j < 10; j++) {            count[j] = count[j - 1] + count[j];        }           for (j = n - 1; j >= 0; j--)        {            k = (a[j] / radix) % 10;            tmp[count[k] - 1] = a[j];            count[k]--;        }        for (j = 0; j < n; j++) {            a[j] = tmp[j];        }    }    delete[]tmp;    delete[]count;}

基數(shù)排序的最好，最好、最壞和平均時(shí)間復(fù)雜度都是O(n*k)，其中n是數(shù)據(jù)大小，k是所選基數(shù)。它需要O(n+k)的額外空間。它是穩(wěn)定的。

八種排序算法總結(jié)

上面介紹了最常提到的八種排序算法，最基礎(chǔ)的是選擇和插入，基于選擇和插入分別改進(jìn)出了冒泡和希爾。基于二分思想又提出了歸并、快排和堆排序。最后基于數(shù)據(jù)的分布特征，提出了基數(shù)排序。這些排序算法的主要指標(biāo)總結(jié)如下。

參考

排序算法時(shí)間復(fù)雜度：https://www./time-complexities-of-all-sorting-algorithms/
排序算法穩(wěn)定性：https://www./stability-in-sorting-algorithms/