算法工程師面試必考項(xiàng)：排序算法

排序是最基本的算法之一，常見的排序算法有插入排序、希爾排序、選擇排序、冒泡排序、堆排序、歸并排序及快速排序。每個(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ù)組來完成排序。假定數(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è)過程至第N個(gè)元素，就可以完成數(shù)組的排序了。

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

這里的實(shí)現(xiàn)我們采用泛型模板，泛型參數(shù)Comparable要求支持比較操作符<。同時(shí)我們使用了移動(dòng)語義，這有利于效率的提升。后面其它算法的實(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&?v)
{
?//?依次處理遞增序列各個(gè)間隔值（從后往前）
?for?(int?gap?=?v.size()?/?2;?gap?>?0;?gap?/=?2)
?{
??//?對(duì)于每個(gè)間隔，進(jìn)行插入排序
??for?(int?i?=?gap;?i???{
???Comparable?tmp?=?move(v[i]);
???int?j?=?i;
???for?(;?j?>=?gap?&&?tmp????{
????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ù)這樣的過程N-1次。

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

選擇排序的時(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)行任何一次元素交換，說明未排序部分已經(jīng)有序，后面就不需要再繼續(xù)冒泡了。

//?冒泡排序
template?<typename?Comparable>
void?bubbleSort(vector&?v)
{
?bool?flag?=?true;??//?是否交換過元素
?for?(int?i?=?0;?flag;?++i)
?{
??flag?=?false;???//?初始為false
??//?向下冒泡
??for?(int?j?=?v.size()?-?1;?j?>?i;?--j)
??{
???if?(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í)算法。我們從歸并算法說起，歸并算法是基于分治策略。歸并算法的基礎(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ù)上述過程知道某一個(gè)子數(shù)組遍歷完，未遍歷完的子數(shù)組剩余部分直接復(fù)制到輸出數(shù)組就完成整個(gè)合并過程。利用合并，歸并排序算法的步驟為：（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&?v,?vector&?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&?v,?vector&?tmp,?
?int?left,?int?right)
{
?if?(left??{
??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&?v)
{
?vector?tmp(v.size());
?mergeSort(v,?tmp,?0,?v.size()?-?1);
}

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

堆排序

堆排序是利用堆來進(jìn)行排序。堆一種特殊的二叉樹，對(duì)于最大堆來說，其每個(gè)節(jié)點(diǎn)的值都大于或者等于其子節(jié)點(diǎn)的值?？梢允褂脭?shù)組來存儲(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è)”下沉過程“，這里我們稱為siftdown：首先將位于根節(jié)點(diǎn)的鍵值與其子節(jié)點(diǎn)的較大鍵值進(jìn)行比較，如果根節(jié)點(diǎn)的鍵值較小，那么就交換根節(jié)點(diǎn)與子節(jié)點(diǎn)，然后對(duì)該子節(jié)點(diǎn)重復(fù)這個(gè)過程，直到到達(dá)葉節(jié)點(diǎn)或者根節(jié)點(diǎn)的鍵值不小于其子節(jié)點(diǎn)的鍵值。假定一個(gè)堆的深度為d，那么首先可以將深度為d-1的節(jié)點(diǎn)使用siftdown過程，這樣深度為d-1的子樹滿足堆性質(zhì)，然后對(duì)深度為d-2的節(jié)點(diǎn)使用siftdown過程，······，最后處理堆的根節(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ù)這一過程，可以達(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&?v,?int?i,?int?n)
{
?int?child;
?Comparable?tmp?=?move(v[i]);??//?記錄要下沉的值
?while?(leftChild(i)??{
??child?=?leftChild(i);?//?左子節(jié)點(diǎn)
??//?尋找最大子節(jié)點(diǎn)
??if?(child?!=?n?-?1?&&?v[child]?1])
??{
???++child;
??}
??if?(tmp?//?子節(jié)點(diǎn)上移
??{
???v[i]?=?move(v[child]);
???i?=?child;
??}
??else??//?終止
??{
???break;
??}
?}
?v[i]?=?move(tmp);??//?下沉到正確位置
}

template?<typename?Comparable>
void?heapSort(vector&?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&?v,?int?left,?int?right)
{
?int?mid?=?(left?+?right)?/?2;
?if?(v[mid]??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ù)上面的過程直到i出現(xiàn)在j的右側(cè)，此時(shí)我們只需要交換位置i與位置right處的值就完成了分割。完成分割后，我們只需要遞歸處理每個(gè)子數(shù)組即可。

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

//?快速排序
template?<typename?Comparable>
void?quickSort(vector&?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&?v,?int?left,?int?right)
{
?for?(int?i?=?1;?i??{
??Comparable?tmp?=?move(v[i]);
??int?j?=?i;
??for?(;?j?>?0?&&?tmp?1];?--j)
??{
???v[j]?=?move(v[j?-?1]);
??}
??v[j]?=?move(tmp);
?}
}
//?快速排序輔助函數(shù)
const?int?SIZE?=?5;
template?<typename?Comparable>
void?quickSort(vector&?v,?int?left,?int?right)
{
?if?(left?+?SIZE??{
??Comparable?pivot?=?median3(v,?left,?right);??//?中心點(diǎn)
??int?i?=?left,?j?=?right?-?1;
??while?(true)
??{
???while?(v[++i]?//?i右移
???while?(v[--j]?>?pivot)?{}??//?j左移
???if?(i????{
????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&?v)
{
?quickSort(v,?0,?v.size()?-?1);
}

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

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

鏈表排序

前面的排序方法我們都是處理是vector，其實(shí)我們都默認(rèn)要排序的是數(shù)組結(jié)構(gòu)，那么元素可以隨機(jī)存?。≧andom 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)只能前向遍歷，這是很大的限制。但是，這并不代表上面的排序算法不能起作用，只不過要進(jìn)行修改。我們先看一下如何使用插入排序來對(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ū)︽湵砼判?，此時(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)
{
?//?無元素或者只有一個(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ù)組的歸并排序不同。

前面說過，僅通過比較的方式來進(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 題解.