排序算法

排序是最基本的算法之一，常見的排序算法有插入排序蔫慧、希爾排序挠乳、選擇排序、冒泡排序姑躲、堆排序欲侮、歸并排序及快速排序。每個(gè)排序算法的時(shí)間復(fù)雜度是不同的肋联，但是最優(yōu)的時(shí)間復(fù)雜度是O(NlogN)威蕉。有些排序算法是原址排序（即不需要額外空間），也有一些是非原址排序橄仍，這也是需要注意的特點(diǎn)韧涨。同樣地，還要注意排序算法是否是穩(wěn)定排序侮繁，這有時(shí)候很重要虑粥。這篇文章簡(jiǎn)單地介紹各個(gè)排序算法的思想，然后使用C++實(shí)現(xiàn)各個(gè)排序算法宪哩。

插入排序

插入排序算法思想很簡(jiǎn)單娩贷，就是將元素插入已經(jīng)有序的數(shù)組來(lái)完成排序。假定數(shù)組前i-1位置是有序的锁孟，現(xiàn)在你要將第i個(gè)元素插入這個(gè)有序數(shù)組彬祖，那么可以依次與第i-1,i-2...等位置的元素進(jìn)行比較，直到找出一個(gè)小于該元素的位置j品抽。將j+1至i-1位置元素依次后移一個(gè)位置储笑，然后將該元素放入第j+1位置。此時(shí)前i個(gè)位置是有序的圆恤。重復(fù)這個(gè)過(guò)程至第N個(gè)元素突倍，就可以完成數(shù)組的排序了。

// 插入排序
template <typename Comparable>
void insertionSort(vector<Comparable>& v)
{
    for (int i = 1; i < v.size(); ++i)
    {
        // 先保存當(dāng)前要插入的元素
        Comparable tmp = move(v[i]);
        int j = i;
        for (; j > 0 && tmp < v[j - 1]; --j)
        {
            v[j] = move(v[j - 1]);  // 大于tmp的元素后移
        }
        v[j] = move(tmp);  // 插入正確的位置
    }
}

這里的實(shí)現(xiàn)我們采用泛型模板，泛型參數(shù)Comparable要求支持比較操作符<羽历。同時(shí)我們使用了移動(dòng)語(yǔ)義焊虏，這有利于效率的提升。后面其它算法的實(shí)現(xiàn)我們也都采用這種方式秕磷。從算法的實(shí)現(xiàn)可以看到有兩層循環(huán)炕淮，那么插入排序的復(fù)雜度是O(N^2)。此外跳夭，插入排序?qū)τ趦蓚€(gè)相等的元素，并不會(huì)改變其先后順序们镜，所以是穩(wěn)定排序币叹。同時(shí)其不需要額外空間，也是原址排序模狭。

希爾排序

希爾排序是以提出者（Donald Shell）命名的颈抚。希爾排序與插入排序的思想很相似，但是其使用了一個(gè)遞增序列H1, H2, ..., Ht嚼鹉。希爾排序每個(gè)階段處理這個(gè)遞增序列中的一個(gè)元素Hk贩汉，其進(jìn)行的是Hk間隔排序，就是保證對(duì)于任意的i锚赤，要有A[i] < A[i+Hk]匹舞。每個(gè)階段的排序利用與插入排序相似的思想：處理的位置i是hk, hk + 1, ..., N，而且每個(gè)位置的插入比較位置是i, i - Hk, , i - 2Hk...线脚。希爾排序的一個(gè)特點(diǎn)是赐稽，如果先進(jìn)行Hk間隔排序，那么Hk-1間隔排序后浑侥，Hk間隔仍然保持有序姊舵。這是希爾排序有效的重要保證。對(duì)于遞增序列寓落，常使用的是Ht = floor(N/2)括丁，而且Hk = floor((Hk+1)/2)。

// 希爾排序
template <typename Comparable>
void shellSort(vector<Comparable>& v)
{
    // 依次處理遞增序列各個(gè)間隔值（從后往前）
    for (int gap = v.size() / 2; gap > 0; gap /= 2)
    {
        // 對(duì)于每個(gè)間隔伶选，進(jìn)行插入排序
        for (int i = gap; i < v.size(); ++i)
        {
            Comparable tmp = move(v[i]);
            int j = i;
            for (; j >= gap && tmp < v[j - gap]; j -= gap)
            {
                v[j] = move(v[j - gap]);
            }
            v[j] = move(tmp);
        }
    }
}

希爾排序的復(fù)雜度并不是那么直接史飞，其與選用的遞增序列有關(guān)，最差狀態(tài)下為O(N^2)仰税，但是如果選用合適的遞增序列祸憋，其復(fù)雜度可以達(dá)到次二次時(shí)間，如O(N^(3/2))肖卧。此外蚯窥，也可以看到希爾排序是原址排序，但不是穩(wěn)定排序。

選擇排序

選擇排序應(yīng)該是最直觀的排序算法拦赠，其將數(shù)組分為排序部分與未排序部分巍沙，每次在未排序部分選出一個(gè)最小值，然后放到排序部分的后面荷鼠。假定數(shù)組前i-1個(gè)位置已經(jīng)有序句携，那么從未排序序列i, i+1,..., N中找到最小值位置j，然后交換位置j與位置i上元素允乐。選擇排序也需要重復(fù)這樣的過(guò)程N-1次矮嫉。

// 選擇排序
template <typename Comparable>
void selectSort(vector<Comparable>& v)
{
    for (int i = 0; i < v.size() - 1; ++i)
    {
        int minIdx = i;
        // 尋找未排序部分的最小值位置
        for (int j = i + 1; j < v.size(); ++j)
        {
            if (v[minIdx] > v[j])
            {
                minIdx = j;
            }
        }
        swap(v[minIdx], v[i]);  // 通過(guò)交換將最小值在正確位置
    }
}

選擇排序的時(shí)間復(fù)雜度為O(N^2)，且是原址排序牍疏。但是選擇排序由于交換蠢笋，導(dǎo)致其是不穩(wěn)定排序方式。

冒泡排序

冒泡排序如其名鳞陨，就是讓數(shù)組元素像水中氣泡一樣逐漸上浮昨寞，從而達(dá)到排序的目的。其也是將數(shù)組分為排序部分與未排序部分厦滤。對(duì)于未排序部分援岩，依次比較相鄰兩個(gè)元素，如果前者大于后者則交換其位置掏导。和選擇排序與插入排序一樣享怀，冒泡排序也應(yīng)該需要N-1次重復(fù)操作，但是有一個(gè)更好的選擇趟咆。那就是在每個(gè)階段凹蜈，記錄一個(gè)flag標(biāo)志，如果沒有進(jìn)行任何一次元素交換忍啸，說(shuō)明未排序部分已經(jīng)有序仰坦，后面就不需要再繼續(xù)冒泡了。

// 冒泡排序
template <typename Comparable>
void bubbleSort(vector<Comparable>& v)
{
    bool flag = true;  // 是否交換過(guò)元素
    for (int i = 0; flag; ++i)
    {
        flag = false;   // 初始為false
        // 向下冒泡
        for (int j = v.size() - 1; j > i; --j)
        {
            if (v[j] < v[j - 1])  // 不是<=计雌，那樣是不穩(wěn)定排序
            {
                swap(v[j], v[j - 1]);
                flag = true;
            }
        }

    }
}

冒泡排序時(shí)間復(fù)雜度也是O(N^2)悄晃，而且是原址排序。冒泡排序也是穩(wěn)定排序凿滤，但是要注意交換條件妈橄。

歸并排序

前面所討論的排序算法都是復(fù)雜度為O(N^2)的低效率排序算法。下面的算法都是時(shí)間復(fù)雜度為O(NlogN)的高級(jí)算法翁脆。我們從歸并算法說(shuō)起眷蚓，歸并算法是基于分治策略。歸并算法的基礎(chǔ)是合并兩個(gè)已經(jīng)有序的子數(shù)組反番，將兩個(gè)已經(jīng)有序的子數(shù)組進(jìn)行合并是容易的沙热。比如兩個(gè)有序子數(shù)組A和B叉钥，然后有一個(gè)輸出數(shù)組C。此時(shí)你需要三個(gè)位置索引i篙贸、j和k投队，每次比較A[i]與B[j]，然后將最小者復(fù)制到C[k]爵川，同時(shí)遞增相應(yīng)的位置索引敷鸦。重復(fù)上述過(guò)程知道某一個(gè)子數(shù)組遍歷完，未遍歷完的子數(shù)組剩余部分直接復(fù)制到輸出數(shù)組就完成整個(gè)合并過(guò)程寝贡。利用合并扒披，歸并排序算法的步驟為：（1）將數(shù)組分為兩個(gè)大小相等的子數(shù)組；（2）對(duì)每個(gè)子數(shù)組進(jìn)行排序圃泡，除非子數(shù)組比較小碟案，否則利用遞歸方式完成排序；（3）合并兩個(gè)有序的子數(shù)組洞焙，完成排序。

// 歸并排序的輔助方法：合并兩個(gè)有序數(shù)組
// v為要排序數(shù)組拯啦，tmp為輔助數(shù)組
// left為左子數(shù)組的開始位置澡匪，right為右子數(shù)組的開始位置，end為結(jié)束位置
template <typename Comparable>
void merge(vector<Comparable>& v, vector<Comparable>& tmp, int left,
    int right, int end)
{
    int tmpPos = left;
    int leftEnd = right - 1;
    int num = end - left + 1;  // 總數(shù)

    // 合并兩個(gè)子數(shù)組直到某一個(gè)子數(shù)組遍歷完
    while (left <= leftEnd && right <= end)
    {
        if (v[left] <= v[right])
        {
            tmp[tmpPos++] = move(v[left++]);
        }
        else
        {
            tmp[tmpPos++] = move(v[right++]);
        }
    }

    // 處理左子數(shù)組剩余部分
    while (left <= leftEnd) { tmp[tmpPos++] = move(v[left++]); }
    // 處理右子數(shù)組剩余部分
    while (right <= end) { tmp[tmpPos++] = move(v[right++]); }

    // 合并結(jié)果復(fù)制到原數(shù)組
    while (num > 0)
    {
        v[end] = move(tmp[end]);
        --end;
        --num;
    }
}

// 歸并合并的內(nèi)部調(diào)用函數(shù)
// v為要排序數(shù)組褒链，tmp為輔助數(shù)組
// left要排序數(shù)組部分的開始位置唁情，right是結(jié)束位置
template <typename Comparable>
void mergeSort(vector<Comparable>& v, vector<Comparable>& tmp, 
    int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        // 遞歸處理每個(gè)子數(shù)組
        mergeSort(v, tmp, left, mid);
        mergeSort(v, tmp, mid + 1, right);
        // 合并
        merge(v, tmp, left, mid + 1, right);
    }
}

// 歸并排序
template<typename Comparable>
void mergeSort(vector<Comparable>& v)
{
    vector<Comparable> tmp(v.size());
    mergeSort(v, tmp, 0, v.size() - 1);
}

歸并排序的時(shí)間復(fù)雜度是O(NlogN)，但是其唯一的問題是需要一個(gè)額外的數(shù)組空間甫匹，所以是非原址排序甸鸟。但是其也是穩(wěn)定排序。

堆排序

堆排序是利用堆來(lái)進(jìn)行排序兵迅。堆一種特殊的二叉樹抢韭，對(duì)于最大堆來(lái)說(shuō)，其每個(gè)節(jié)點(diǎn)的值都大于或者等于其子節(jié)點(diǎn)的值恍箭】坦В可以使用數(shù)組來(lái)存儲(chǔ)堆：將根節(jié)點(diǎn)放在第一個(gè)數(shù)組位置，根節(jié)點(diǎn)的左右子節(jié)點(diǎn)分別存儲(chǔ)在數(shù)組的第二與第三位置扯夭，然后其左子節(jié)點(diǎn)的左右子節(jié)點(diǎn)放置在第四與第五位置鳍贾，依次類推。如果數(shù)組索引是從0開始的交洗，對(duì)于位置i處的節(jié)點(diǎn)骑科，其左子節(jié)點(diǎn)位置為2*i+1，其右子節(jié)點(diǎn)位置為2*(i+1)构拳。要進(jìn)行堆排序咆爽，首先要建立堆梁棠。要構(gòu)建堆，需要使用一個(gè)”下沉過(guò)程“伍掀，這里我們稱為siftdown：首先將位于根節(jié)點(diǎn)的鍵值與其子節(jié)點(diǎn)的較大鍵值進(jìn)行比較掰茶，如果根節(jié)點(diǎn)的鍵值較小，那么就交換根節(jié)點(diǎn)與子節(jié)點(diǎn)蜜笤，然后對(duì)該子節(jié)點(diǎn)重復(fù)這個(gè)過(guò)程濒蒋，直到到達(dá)葉節(jié)點(diǎn)或者根節(jié)點(diǎn)的鍵值不小于其子節(jié)點(diǎn)的鍵值。假定一個(gè)堆的深度為d把兔，那么首先可以將深度為d-1的節(jié)點(diǎn)使用siftdown過(guò)程沪伙，這樣深度為d-1的子樹滿足堆性質(zhì)，然后對(duì)深度為d-2的節(jié)點(diǎn)使用siftdown過(guò)程县好，······围橡，最后處理堆的根節(jié)點(diǎn)，此時(shí)這個(gè)樹滿足堆性質(zhì)缕贡。一旦我們構(gòu)建好了堆翁授，我們可以在保持堆性質(zhì)的同時(shí)重復(fù)刪除根節(jié)點(diǎn)，得到的這些根節(jié)點(diǎn)是有序的晾咪，從而達(dá)到排序的目的收擦。怎么在刪除根節(jié)點(diǎn)之后還保持堆性質(zhì)呢？這里有一個(gè)技巧谍倦，我們可以交換根節(jié)點(diǎn)與最右子節(jié)點(diǎn)的鍵值塞赂，此時(shí)將堆將縮減一個(gè)元素（最右子節(jié)點(diǎn)），然后對(duì)當(dāng)前根節(jié)點(diǎn)調(diào)用siftdown昼蛀。我們知道最右子節(jié)點(diǎn)恰好是數(shù)組最后的位置宴猾，所以重復(fù)這一過(guò)程，可以達(dá)到原址排序的目的叼旋。

// 返回節(jié)點(diǎn)i的左子節(jié)點(diǎn)位置
inline int leftChild(int i) { return 2 * i + 1; }

// 堆排序輔助函數(shù)
// v是存儲(chǔ)堆的數(shù)組仇哆，i是要下沉的節(jié)點(diǎn)，n代表當(dāng)前堆的大小
template <typename Comparable>
void siftDown(vector<Comparable>& v, int i, int n)
{
    int child;
    Comparable tmp = move(v[i]);  // 記錄要下沉的值
    while (leftChild(i) < n)
    {
        child = leftChild(i); // 左子節(jié)點(diǎn)
        // 尋找最大子節(jié)點(diǎn)
        if (child != n - 1 && v[child] < v[child + 1])
        {
            ++child;
        }
        if (tmp < v[child])  // 子節(jié)點(diǎn)上移
        {
            v[i] = move(v[child]);
            i = child;
        }
        else  // 終止
        {
            break;
        }
    }
    v[i] = move(tmp);  // 下沉到正確位置
}

template <typename Comparable>
void heapSort(vector<Comparable>& v)
{
    // 先建立堆
    for (int i = v.size() / 2 - 1; i >= 0; --i)
    {
        siftDown(v, i, v.size());
    }
    // 重復(fù)刪除根節(jié)點(diǎn)
    for (int i = v.size() - 1; i > 0; --i)
    {
        swap(v[i], v[0]);  // 交換根節(jié)點(diǎn)與最右子節(jié)點(diǎn)
        siftDown(v, 0, i);  // 下沉根節(jié)點(diǎn)
    }
}

堆排序的時(shí)間復(fù)雜度也是O(NlogN)夫植，其不需要額外空間税产，是原址排序。但是由于進(jìn)行了根節(jié)點(diǎn)與最右子節(jié)點(diǎn)的交換偷崩，堆排序是不穩(wěn)定的辟拷。

快速排序

快速排序與歸并排序有相似之處，其采用的也是分治的策略阐斜∩蓝常快速排序也將數(shù)組劃分為兩部分，但是其劃分是根據(jù)一個(gè)選定的中心點(diǎn)（pivot）谒出，前半部分是小于pivot值隅俘，后半部分大于pivot邻奠。不斷重復(fù)這種策略在每個(gè)子數(shù)組上，即可完成排序为居÷笛纾快速排序的一個(gè)關(guān)鍵點(diǎn)是選擇中心點(diǎn)，選擇中心點(diǎn)后要將原數(shù)組分割成兩部分蒙畴。如果中心點(diǎn)選擇不恰當(dāng)贰镣，那么會(huì)導(dǎo)致分割的兩個(gè)子數(shù)組大小嚴(yán)重不平衡，這樣快速排序的性能就會(huì)惡化膳凝。一個(gè)比較好的策略是選擇數(shù)組最左邊碑隆、最右邊與中心位置的中間值，即Median-of-Three策略：

// 快速排序：選定中心點(diǎn)策略 
// v是排序數(shù)組蹬音，left與right分別是要分割數(shù)組的左右邊界
template <typename Comparable>
const Comparable& median3(vector<Comparable>& v, int left, int right)
{
    int mid = (left + right) / 2;
    if (v[mid] < v[left]) { swap(v[mid], v[left]); }
    if (v[left] > v[right]) { swap(v[left], v[right]); }
    if (v[mid] > v[right]) { swap(v[mid], v[right]); }

    // left位置的值小于等于pivot上煤，right位置的值一定大于等于pivot，
    // 要分割的數(shù)組變成left+1到right-1
    swap(v[mid], v[right - 1]);  // 將pivot放到right-1位置處
    return v[right - 1];
}

這個(gè)選擇中心點(diǎn)的策略很簡(jiǎn)單著淆，但是最后把選擇的中心點(diǎn)存儲(chǔ)在數(shù)組倒數(shù)第二個(gè)位置劫狠，這個(gè)是為分割做準(zhǔn)備的。一旦選定中心點(diǎn)永部，那么就要根據(jù)中心點(diǎn)將數(shù)組分為左右兩部分独泞。一個(gè)比較好的策略是采用左右夾逼。假定要分割的數(shù)組是A[left], A[left+1], ..., A[right]扬舒。此時(shí)記住A[right]此時(shí)存儲(chǔ)的是中心點(diǎn)的值阐肤。我們?cè)O(shè)置兩個(gè)位置索引變量i和j凫佛，i從最左側(cè)left開始讲坎，j從最右側(cè)right-1開始。我們將i向右移動(dòng)愧薛，直到此位置處的值大于或者等于pivot晨炕，同時(shí)我們將j向左移動(dòng)，直到此位置處的值小于或者等于pivot毫炉。如果此時(shí)i還在j的左側(cè)瓮栗，我們交換位置i和位置j處的值。然后重復(fù)上面的過(guò)程直到i出現(xiàn)在j的右側(cè)瞄勾，此時(shí)我們只需要交換位置i與位置right處的值就完成了分割费奸。完成分割后，我們只需要遞歸處理每個(gè)子數(shù)組即可进陡。

// 快速排序輔助函數(shù)
template <typename Comparable>
void quickSort(vector<Comparable>& v, int left, int right)
{
    if (left + 1 < right) // 3個(gè)及以上元素
    {
        Comparable pivot = median3(v, left, right);  // 中心點(diǎn)
        int i = left, j = right - 1;
        while (true)
        {
            while (v[++i] < pivot) {}  // i右移
            while (v[--j] > pivot) {}  // j左移
            if (i < j)
            {
                swap(v[i], v[j]);
            }
            else
            {
                break;
            }
        }
        swap(v[i], v[right - 1]);
        // 對(duì)子數(shù)組遞歸
        quickSort(v, left, i - 1);
        quickSort(v, i + 1, right);
    }
    else if (left < right)  // 兩個(gè)元素
    {
        if (v[left] > v[right]) { swap(v[left], v[right]); }
    }
}

// 快速排序
template <typename Comparable>
void quickSort(vector<Comparable>& v)
{
    quickSort(v, 0, v.size() - 1);
}

遞歸時(shí)愿阐，要分兩種情況，三個(gè)及以上元素時(shí)繼續(xù)調(diào)用快速排序趾疚，但是兩個(gè)元素時(shí)缨历，必須要單獨(dú)處理以蕴。因?yàn)檫x定中心點(diǎn)需要三個(gè)及以上元素。其實(shí)辛孵，快速排序?qū)τ谛?shù)組優(yōu)勢(shì)并不是很明顯丛肮，當(dāng)數(shù)組較小時(shí)，可以使用其它排序算法處理魄缚，比如插入排序：

// 插入排序
template <typename Comparable>
void insertionSort(vector<Comparable>& v, int left, int right)
{
    for (int i = 1; i < v.size(); ++i)
    {
        Comparable tmp = move(v[i]);
        int j = i;
        for (; j > 0 && tmp < v[j - 1]; --j)
        {
            v[j] = move(v[j - 1]);
        }
        v[j] = move(tmp);
    }
}
// 快速排序輔助函數(shù)
const int SIZE = 5;
template <typename Comparable>
void quickSort(vector<Comparable>& v, int left, int right)
{
    if (left + SIZE < right) 
    {
        Comparable pivot = median3(v, left, right);  // 中心點(diǎn)
        int i = left, j = right - 1;
        while (true)
        {
            while (v[++i] < pivot) {}  // i右移
            while (v[--j] > pivot) {}  // j左移
            if (i < j)
            {
                swap(v[i], v[j]);
            }
            else
            {
                break;
            }
        }
        swap(v[i], v[right - 1]);
        // 對(duì)子數(shù)組遞歸
        quickSort(v, left, i - 1);
        quickSort(v, i + 1, right);
    }
    else 
    {
        insertionSort(v, left, right);
    }
}

// 快速排序
template <typename Comparable>
void quickSort(vector<Comparable>& v)
{
    quickSort(v, 0, v.size() - 1);
}

快速排序的時(shí)間復(fù)雜度平均為O(NlogN)宝与，但是最差時(shí)也表現(xiàn)為O(N^2)。其次鲜滩，快速排序也是原址排序伴鳖，但是其是不穩(wěn)定的。

大部分排序算法這里算是介紹完了徙硅，從比較上來(lái)看榜聂，這些排序算法最優(yōu)性能為O(NlogN)。但是大家可以發(fā)現(xiàn)一個(gè)事實(shí)嗓蘑，這些算法都是通過(guò)比較來(lái)完成的须肆，而且已經(jīng)證明O(NlogN)是所有利用比較來(lái)進(jìn)行排序的算法的一個(gè)下限。還有一點(diǎn)要說(shuō)明桩皿，這些排序算法都有一個(gè)前提豌汇，那就是要排序的數(shù)組可以全部讀進(jìn)內(nèi)存。但是當(dāng)要排序的元素量非常大時(shí)泄隔，可能無(wú)法一下子將所有元素放進(jìn)內(nèi)存拒贱，此時(shí)需要外部排序算法。感興趣可以去了解佛嬉。

鏈表排序

前面的排序方法我們都是處理是vector逻澳，其實(shí)我們都默認(rèn)要排序的是數(shù)組結(jié)構(gòu)，那么元素可以隨機(jī)存扰弧（Random Access）斜做。但是，我們知道有些結(jié)構(gòu)是不支持隨機(jī)存取的湾揽，比如鏈表結(jié)構(gòu)瓤逼。這里我們簡(jiǎn)單地討論單鏈表結(jié)構(gòu)：

// 單鏈表節(jié)點(diǎn)
class ListNode
{
public:
    int val;
    ListNode* next;
    ListNode(int value, ListNode* nt = nullptr)
        :val{value}, next{nt}
    {}
};

鏈表結(jié)構(gòu)只能前向遍歷，這是很大的限制库物。但是霸旗，這并不代表上面的排序算法不能起作用，只不過(guò)要進(jìn)行修改戚揭。我們先看一下如何使用插入排序來(lái)對(duì)一個(gè)鏈表排序诱告。對(duì)于插入排序，關(guān)鍵的是要找到插入點(diǎn)位置毫目，鏈表只能前向遍歷蔬啡，所以必須從頭節(jié)點(diǎn)找到插入點(diǎn)位置诲侮，而不能采用之前的策略。實(shí)現(xiàn)就很簡(jiǎn)單了：

// 從鏈表頭節(jié)點(diǎn)開始尋找插入點(diǎn)位置
ListNode* findInsertPos(ListNode* head, int x)
{
    ListNode* prev = nullptr;
    for (ListNode* cur = head; cur != nullptr && cur->val <= x;
        prev = cur, cur = cur->next)
        ;
    return prev;
}

// 使用插入排序?qū)︽湵磉M(jìn)行排序
void insertionSortList(ListNode* & head)
{
    //// 啞巴節(jié)點(diǎn)
    ListNode dummy{ INT_MIN }; // 不要執(zhí)行dummy.next = head
    // 每次處理一個(gè)節(jié)點(diǎn)
    for (ListNode* cur = head; cur != nullptr;)
    {
        ListNode* pos = findInsertPos(&dummy, cur->val);  // 確定插入位置
        // 插入此位置
        ListNode* tmp = cur->next;
        cur->next = pos->next;
        pos->next = cur;
        cur = tmp;
    }
    head = dummy.next;
}

上面的插入排序算法的時(shí)間復(fù)雜度還是O(N^2)箱蟆，并且不要額外空間沟绪。我們也可以使用歸并排序?qū)︽湵砼判颍藭r(shí)的復(fù)雜度為O(NlogN)空猜。具體實(shí)現(xiàn)如下：

// 歸并兩個(gè)有序鏈表
ListNode* mergeList(ListNode* l1, ListNode* l2)
{
    // 啞巴節(jié)點(diǎn)
    ListNode dummy{ 0 };
    ListNode* cur = &dummy;
    // 處理公共部分
    for (; l1 != nullptr && l2 != nullptr;
        cur = cur->next)
    {
        if (l1->val <= l2->val)
        {
            cur->next = l1;
            l1 = l1->next;
        }
        else
        {
            cur->next = l2;
            l2 = l2->next;
        }
    }
    // 處理l1剩余部分
    while (l1 != nullptr) { cur->next = l1; l1 = l1->next; cur = cur->next; }
    // 處理l2剩余部分
    while (l2 != nullptr) { cur->next = l2; l2 = l2->next; cur = cur->next; }
    return dummy.next;
}

// 歸并排序鏈表
void mergeSortList(ListNode* & head)
{
    // 無(wú)元素或者只有一個(gè)元素
    if (head == nullptr || head->next == nullptr) return;
    // 利用快慢指針找到中間節(jié)點(diǎn)
    ListNode* slow = head, *fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr)
    {
        fast = fast->next->next;
        slow = slow->next;
    }

    // 根據(jù)中間節(jié)點(diǎn)分割鏈表
    fast = slow;
    slow = slow->next;
    fast->next = nullptr;

    mergeSortList(head);   // 處理前半部分
    mergeSortList(slow);   // 處理后半部分
    head = mergeList(head, slow);  // 歸并
}

可以看到绽慈，鏈表的歸并排序不需要額外存儲(chǔ)空間，這與數(shù)組的歸并排序不同辈毯。

前面說(shuō)過(guò)坝疼，僅通過(guò)比較的方式來(lái)進(jìn)行排序的算法，其效率不可能優(yōu)于O(NlogN)谆沃。但是也是存在可以在線性時(shí)間內(nèi)完成排序的算法钝凶，如桶排序與基數(shù)排序。路漫漫其修遠(yuǎn)兮唁影，感興趣的繼續(xù)探索吧耕陷！

Reference

[1] Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, fourth edition, 2013.
[2] Richard E. Neapolitan, Foundations of Algorithms, fifth edition, 2016.
[3] LeetCode 題解.