各種排序算法的穩(wěn)定性和時(shí)間復(fù)雜度小結(jié)

1、選擇排序、快速排序、希爾排序、堆排序不是穩(wěn)定的排序算法， 冒泡排序、插入排序、歸并排序和基數(shù)排序是穩(wěn)定的排序算法。冒泡法：這是最原始， 也是眾所周知的最慢的算法了。 他的名字的由來因?yàn)樗墓ぷ骺磥硐笫敲芭荩?復(fù) 雜度為 O(n*n) 。當(dāng)數(shù)據(jù)為正序，將不會(huì)有交換。復(fù)雜度為O(0)。直接插入排序： O(n*n)選擇排序： O(n*n)快速排序：平均時(shí)間復(fù)雜度 log2(n)*n ，所有內(nèi)部排序方法中最高好的，大多數(shù)情況下總是最好 的。歸并排序： log2(n)*n堆排序： log2(n)*n希爾排序：算法的復(fù)雜度為 n 的 1.2 次冪這里我沒有給出行為的分析，因?yàn)檫@個(gè)很簡單，我們直接來分析算法

2、： 首先我們考慮最理想的情況1.數(shù)組的大小是 2 的冪，這樣分下去始終可以被 2整除。假設(shè)為 2的 k 次方，即 k=log2(n) 。 2.每次我們選擇的值剛好是中間值，這樣，數(shù)組才可以被等分。第一層遞歸，循環(huán) n 次，第二層循環(huán) 2*(n/2)所以共有 n+2(n/2)+4(n/4)+.+n*(n/n) = n+n+n+.+n=k*n=log2(n)*n 所以算法復(fù)雜度為 O(log2(n)*n) 其他的情況只會(huì)比這種情況差，最差的情況是每次選擇到的 middle 都是最小值或最大值，那么 他將變成交換法 (由于使用了遞歸， 情況更糟) 。但是你認(rèn)為這種情況發(fā)生的幾率有多大？呵 呵，你完全

3、不必?fù)?dān)心這個(gè)問題。實(shí)踐證明，大多數(shù)的情況，快速排序總是最好的。如果你擔(dān)心這個(gè)問題， 你可以使用堆排序， 這是一種穩(wěn)定的 O(log2(n)*n) 算法， 但是通常情況下 速度要慢 于快速排序(因?yàn)橐亟M堆) 。這幾天筆試了好幾次了，連續(xù)碰到一個(gè)關(guān)于常見排序算法穩(wěn)定性判別的問題，往往還是多選， 對(duì)于我以及和我一樣拿不準(zhǔn)的同學(xué)可不是一個(gè)能輕易下結(jié)論的題目，當(dāng)然如果你筆試之前已經(jīng) 記住了數(shù)據(jù)結(jié)構(gòu)書上哪些是穩(wěn)定的，哪些不是穩(wěn)定的，做起來應(yīng)該可以輕松搞定。本文是針對(duì)老是記不住這個(gè)或者想真正明白到底為什么是穩(wěn)定或者不穩(wěn)定的人準(zhǔn)備的。2 個(gè)相等的數(shù)其首先，排序算法的穩(wěn)定性大家應(yīng)該都知道，通俗地講就是能保證排

4、序前在簡單形式化一下， 如果 Ai = Aj,在序列的前后位置順序和排序后它們兩個(gè)的前后位置順序相同。Ai 原來在位置前，排序后 Ai 還是要在 Aj 位置前。其次，說一下穩(wěn)定性的好處。排序算法如果是穩(wěn)定的，那么從一個(gè)鍵上排序，然后再從另 一個(gè)鍵上排序，第一個(gè)鍵排序的結(jié)果可以為第二個(gè)鍵排序所用?；鶖?shù)排序就是這樣，先按低位 排序，逐次按高位排序，低位相同的元素其順序再高位也相同時(shí)是不會(huì)改變的。另外，如果排 序算法穩(wěn)定， 對(duì)基于比較的排序算法而言， 元素交換的次數(shù)可能會(huì)少一些 (個(gè)人感覺， 沒有證實(shí) )?；氐街黝}，現(xiàn)在分析一下常見的排序算法的穩(wěn)定性，每個(gè)都給出簡單的理由。(1) 冒泡排序冒泡排序就

5、是把小的元素往前調(diào)或者把大的元素往后調(diào)。 比較是相鄰的兩個(gè)元素比較， 交換也發(fā)生在這兩個(gè)元素之間。所以，如果兩個(gè)元素相等，我想你是不會(huì)再無聊地把他們倆交 換一下的；如果兩個(gè)相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個(gè)相鄰起來，這 時(shí)候也不會(huì)交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。(2) 選擇排序選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的，比如給第一個(gè)位置選擇最小的，在剩余元 素里面給第二個(gè)元素選擇第二小的，依次類推，直到第 n-1 個(gè)元素，第 n 個(gè)元素不用選擇了， 因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了。那么，在一趟選擇，如果當(dāng)前元素比一個(gè)元素小，而該小的 元素又出

6、現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。比較拗口，舉 個(gè)例子，序列 5 8 5 2 9， 我們知道第一遍選擇第 1個(gè)元素 5會(huì)和2交換，那么原序列中 2個(gè) 5 的相對(duì)前后順序就被破壞了，所以選擇排序不是一個(gè)穩(wěn)定的排序算法。(3) 插入排序插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上， 一次插入一個(gè)元素。 當(dāng)然， 剛開始這個(gè)有 序的小序列只有 1 個(gè)元素，就是第一個(gè)元素。比較是從有序序列的末尾開始，也就是想要插入 的元素和已經(jīng)有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到 找到它該插入的位置。如果碰見一個(gè)和插入元素相等的，那么插入元素把想插入的元素放在相

7、 等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后 的順序，所以插入排序是穩(wěn)定的。(4) 快速排序快速排序有兩個(gè)方向， 左邊的 i 下標(biāo)一直往右走， 當(dāng) ai <= acenter_index ，其中 center_index 是中樞元素的數(shù)組下標(biāo)，一般取為數(shù)組第 0 個(gè)元素。而右邊的 j 下標(biāo)一直往左走，當(dāng) aj > acenter_index 。如果 i 和 j 都走不動(dòng)了， i <= j, 交換 ai 和 aj, 重復(fù)上面的過程，直到 i>j 。 交 換 aj 和 acenter_index ，完成一趟快速排序。在中樞元素和aj

8、交換的時(shí)候，很有可能把前面的元素的穩(wěn)定性打亂， 比如序列為 5 3 3 4 3 8 9 10 11， 現(xiàn)在中樞元素 5和 3(第 5個(gè)元素， 下標(biāo) 從 1 開始計(jì) ) 交換就會(huì)把元素 3 的穩(wěn)定性打亂，所以快速排序是一個(gè)不穩(wěn)定的排序算法，不穩(wěn)定 發(fā)生在中樞元素和 aj 交換的時(shí)刻。(5) 歸并排序歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有 1 個(gè)元素 (認(rèn)為直接有序 )或 者 2 個(gè)序列 (1 次比較和交換 ),然后把各個(gè)有序的段序列合并成一個(gè)有序的長序列，不斷合并直 到原序列全部排好序。可以發(fā)現(xiàn)，在1 個(gè)或 2 個(gè)元素時(shí)， 1 個(gè)元素不會(huì)交換， 2 個(gè)元素如果大小相等也沒有人故意

9、交換，這不會(huì)破壞穩(wěn)定性。那么，在短的有序序列合并的過程中，穩(wěn)定是是否受到破壞？沒有，合并過程中我們可以保證如果兩個(gè)當(dāng)前元素相等時(shí)，我們把處在前面的序 列的元素保存在結(jié)果序列的前面， 這樣就保證了穩(wěn)定性。 所以， 歸并排序也是穩(wěn)定的排序算法。(6) 基數(shù)排序基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最 高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序，最后的次 序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前。基數(shù)排序基于分別排序，分別 收集，所以其是穩(wěn)定的排序算法。(7) 希爾排序 (shell) 希爾排序是按照不同步長對(duì)元素進(jìn)

10、行插入排序，當(dāng)剛開始元素很無序的時(shí)候，步長最大， 所以插入排序的元素個(gè)數(shù)很少，速度很快；當(dāng)元素基本有序了，步長很小，插入排序?qū)τ谟行?的序列效率很高。所以，希爾排序的時(shí)間復(fù)雜度會(huì)比o(n A2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過程中，相 同的元素可能在各自的插入排序中移動(dòng)， 最后其穩(wěn)定性就會(huì)被打亂， 所以 shell 排序是不穩(wěn)定的。(8) 堆排序我們知道堆的結(jié)構(gòu)是節(jié)點(diǎn)i的孩子為2*i和2*i+1節(jié)點(diǎn)，大頂堆要求父節(jié)點(diǎn)大于等于其2個(gè)子節(jié)點(diǎn)，小頂堆要求父節(jié)點(diǎn)小于等于其 2 個(gè)子節(jié)點(diǎn)。在一個(gè)長為 n 的序列，堆排序的過程是從 第

11、n/2開始和其子節(jié)點(diǎn)共 3個(gè)值選擇最大(大頂堆)或者最小(小頂堆),這3個(gè)元素之間的選擇當(dāng)然 不會(huì)破壞穩(wěn)定性。但當(dāng)為n/2-1, n/2-2, .1 這些個(gè)父節(jié)點(diǎn)選擇元素時(shí)，就會(huì)破壞穩(wěn)定性。有可能第 n/2 個(gè)父節(jié)點(diǎn)交換把后面一個(gè)元素交換過去了， 而第 n/2-1 個(gè)父節(jié)點(diǎn)把后面一個(gè)相同的元素沒 有交換，那么這 2 個(gè)相同的元素之間的穩(wěn)定性就被破壞了。所以，堆排序不是穩(wěn)定的排序算法1 快速排序( QuickSort )快速排序是一個(gè)就地排序，分而治之，大規(guī)模遞歸的算法。從本質(zhì)上來說，它是歸并排序的就 地版本。快速排序可以由下面四步組成。1 ) 如果不多于 1 個(gè)數(shù)據(jù)，直接返回。2) 一般選擇序

12、列最左邊的值作為支點(diǎn)數(shù)據(jù)。3) 將序列分成 2 部分，一部分都大于支點(diǎn)數(shù)據(jù)，另外一部分都小于支點(diǎn)數(shù)據(jù)。4) 對(duì)兩邊利用遞歸排序數(shù)列?？焖倥判虮却蟛糠峙判蛩惴ǘ家臁１M管我們可以在某些特殊的情況下寫出比快速排序快的算 法，但是就通常情況而言，沒有比它更快的了?？焖倥判蚴沁f歸的，對(duì)于內(nèi)存非常有限的機(jī)器 來說，它不是一個(gè)好的選擇。2 歸并排序( MergeSort )歸并排序先分解要排序的序列，從 1 分成 2， 2 分成 4，依次分解，當(dāng)分解到只有 1 個(gè)一組的時(shí) 候，就可以排序這些分組，然后依次合并回原來的序列中，這樣就可以排序所有數(shù)據(jù)。合并排 序比堆排序稍微快一點(diǎn)，但是需要比堆排序多一倍的內(nèi)存

13、空間，因?yàn)樗枰粋€(gè)額外的數(shù)組。3 堆排序( HeapSort)堆排序適合于數(shù)據(jù)量非常大的場(chǎng)合(百萬數(shù)據(jù)) 堆排序不需要大量的遞歸或者多維的暫存數(shù)組。這對(duì)于數(shù)據(jù)量非常巨大的序列是合適的。比如 超過數(shù)百萬條記錄， 因?yàn)榭焖倥判颍?歸并排序都使用遞歸來設(shè)計(jì)算法， 在數(shù)據(jù)量非常大的時(shí)候， 可能會(huì)發(fā)生堆棧溢出錯(cuò)誤。堆排序會(huì)將所有的數(shù)據(jù)建成一個(gè)堆，最大的數(shù)據(jù)在堆頂，然后將堆頂數(shù)據(jù)和序列的最后一個(gè)數(shù) 據(jù)交換。接下來再次重建堆，交換數(shù)據(jù)，依次下去，就可以排序所有的數(shù)據(jù)。4 Shell 排序( ShellSort )Shell 排序通過將數(shù)據(jù)分成不同的組，先對(duì)每一組進(jìn)行排序，然后再對(duì)所有的元素進(jìn)行一次插入 排

14、序，以減少數(shù)據(jù)交換和移動(dòng)的次數(shù)。平均效率是O(nlogn) 。其中分組的合理性會(huì)對(duì)算法產(chǎn)生重要的影響。現(xiàn)在多用 D.E.Knuth 的分組方法。Shell排序比冒泡排序快 5倍，比插入排序大致快 2倍。Shell排序比起Quicksort , MergeSort,HeapSort 慢很多。 但是它相對(duì)比較簡單， 它適合于數(shù)據(jù)量在 5000 以下并且速度并不是特別重要 的場(chǎng)合。它對(duì)于數(shù)據(jù)量較小的數(shù)列重復(fù)排序是非常好的。5 插入排序( InsertSort)插入排序通過把序列中的值插入一個(gè)已經(jīng)排序好的序列中，直到該序列的結(jié)束。插入排序是對(duì) 冒泡排序的改進(jìn)。 它比冒泡排序快 2 倍。一般不用在數(shù)據(jù)大

15、于 1000 的場(chǎng)合下使用插入排序， 或 者重復(fù)排序超過 200 數(shù)據(jù)項(xiàng)的序列。6 冒泡排序( BubbleSort)冒泡排序是最慢的排序算法。在實(shí)際運(yùn)用中它是效率最低的算法。它通過一趟又一趟地比較數(shù)組中的每一個(gè)元素，使較大的數(shù)據(jù)下沉，較小的數(shù)據(jù)上升。它是0(nA2)的算法。7交換排序(ExchangeSort)和選擇排序(SelectSort)這兩種排序方法都是交換方法的排序算法，效率都是O(n2)。在實(shí)際應(yīng)用中處于和冒泡排序基本相同的地位。它們只是排序算法發(fā)展的初級(jí)階段，在實(shí)際中使用較少。8 基數(shù)排序( RadixSort )基數(shù)排序和通常的排序算法并不走同樣的路線。它是一種比較新穎的算法

16、，但是它只能用于整數(shù)的排序，如果我們要把同樣的辦法運(yùn)用到浮點(diǎn)數(shù)上，我們必須了解浮點(diǎn)數(shù)的存儲(chǔ)格式，并通 過特殊的方式將浮點(diǎn)數(shù)映射到整數(shù)上，然后再映射回去，這是非常麻煩的事情，因此，它的使 用同樣也不多。而且，最重要的是，這樣算法也需要較多的存儲(chǔ)空間。9 總結(jié)下面是一個(gè)總的表格，大致總結(jié)了我們常見的所有的排序算法的特點(diǎn)。排序法 平均時(shí)間 最差情形 穩(wěn)定度 額外空間 備注 冒泡 O(n2) O(n2) 穩(wěn)定 O(1) n 小時(shí)較好交換 O(n2) O(n2) 不穩(wěn)定 O(1) n 小時(shí)較好選擇 O(n2) O(n2) 不穩(wěn)定 O(1) n 小時(shí)較好插入 O(n2) O(n2) 穩(wěn)定 O(1) 大部分

17、已排序時(shí)較好 基數(shù) O(logRB) O(logRB) 穩(wěn)定 O(n) B 是真數(shù) (0-9)，R 是基數(shù) ( 個(gè)十百 )Shell O(nlogn) O(ns) 1<s<2 不穩(wěn)定 O(1) s 是所選分組 快速 O(nlogn) O(n2) 不穩(wěn)定 O(nlogn) n 大時(shí)較好 歸并 O(nlogn) O(nlogn) 穩(wěn)定 O(1) n 大時(shí)較好 堆 O(nlogn) O(nlogn) 不穩(wěn)定 O(1) n 大時(shí)較好 以下是一個(gè)基于模板的通用排序： 這個(gè)程序我想就沒有分析的必要了，大家看一下就可以了。不明白可以在論壇上問。 MyData.h 文件/class CMyData

18、public:CMyData(int Index,char* strData);CMyData();virtual CMyData();int m_iIndex;int GetDataSize() return m_iDataSize; ; const char* GetData() return m_strDatamember; ; /這里重載了操作符：CMyData& operator =(CMyData &SrcData);bool operator <(CMyData& data );bool operator >(CMyData& data

19、 );private:char* m_strDatamember;int m_iDataSize;/MyData.cpp 文件/CMyData:CMyData():m_iIndex(0),m_iDataSize(0),m_strDatamember(NULL)CMyData:CMyData()if(m_strDatamember != NULL) delete m_strDatamember;m_strDatamember = NULL;CMyData:CMyData(int Index,char* strData): m_iIndex(Index),m_iDataSize(0), m_str

20、Datamember(NULL)m_iDataSize = strlen(strData); m_strDatamember = new charm_iDataSize+1; strcpy(m_strDatamember,strData);CMyData& CMyData:operator =(CMyData &SrcData) m_iIndex = SrcData.m_iIndex;m_iDataSize = SrcData.GetDataSize(); m_strDatamember = new charm_iDataSize+1; strcpy(m_strDatamemb

21、er,SrcData.GetData(); return *this;bool CMyData:operator <(CMyData& data )return m_iIndex<data.m_iIndex;bool CMyData:operator >(CMyData& data )return m_iIndex>data.m_iIndex;/主程序部分#include <iostream.h>#include "MyData.h" template <class T>void run(T* pData,int left,int right)int i,j;T middle,iTemp;i = left;j = right;/下面的比較都調(diào)用我們重載的操作符函數(shù) middle = pData(left+right)/2; / 求中間值 dowhile(pDatai<middle) && (i<right)/ 從左掃描大于中值的數(shù) i+;while(pDataj>middle) && (j>left)/ 從右掃描大于中值的數(shù) j-;if(i<=j)/ 找到了一對(duì)