① 歸並排序
先考慮一個簡單的問題：如何在線性的時間內將兩個有序隊列合並為一個有序隊列（並輸出）？
A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
看上面的例子，AB兩個序列都是已經有序的了。在給出數據已經有序的情況下，我們會發現很多神奇的事，比如，我們將要輸出的第一個數一定來自於這兩個序列各自最前面的那個數。兩個數都是1，那麼我們隨便取出一個（比如A隊列的那個1）並輸出：
A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1
注意，我們取出了一個數，在原數列中刪除這個數。刪除操作是通過移動隊首指針實現的，否則復雜度就高了。
現在，A隊列打頭的數變成3了，B隊列的隊首仍然是1。此時，我們再比較3和1哪個大並輸出小的那個數：
A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1 1
接下來的幾步如下：
A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9
B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ……
輸出：1 1 2 輸出：1 1 2 3 輸出：1 1 2 3 5 輸出：1 1 2 3 5 7
我希望你明白了這是怎麼做的。這個做法顯然是正確的，復雜度顯然是線性。
歸並排序(Merge Sort)將會用到上面所說的合並操作。給出一個數列，歸並排序利用合並操作在O(nlogn)的時間內將數列從小到大排序。歸並排序用的是分治(Divide and Conquer)的思想。首先我們把給出的數列平分為左右兩段，然後對兩段數列分別進行排序，最後用剛才的合並演算法把這兩段（已經排過序的）數列合並為一個數列。有人會問「對左右兩段數列分別排序時用的什麼排序」么？答案是：用歸並排序。也就是說，我們遞歸地把每一段數列又分成兩段進行上述操作。你不需要關心實際上是怎麼操作的，我們的程序代碼將遞歸調用該過程直到數列不能再分（只有一個數）為止。
初看這個演算法時有人會誤以為時間復雜度相當高。我們下面給出的一個圖將用非遞歸的眼光來看歸並排序的實際操作過程，供大家參考。我們可以藉助這個圖證明，歸並排序演算法的時間復雜度為O(nlogn)。
[3] [1] [4] [1] [5] [9] [2] [7]
\ / \ / \ / \ /
[1 3] [1 4] [5 9] [2 7]
\ / \ /
[1 1 3 4] [2 5 7 9]
\ /
[1 1 2 3 4 5 7 9]
上圖中的每一個「 \ / 」表示的是上文所述的線性時間合並操作。上圖用了4行來圖解歸並排序。如果有n個數，表示成上圖顯然需要O(logn)行。每一行的合並操作復雜度總和都是O(n)，那麼logn行的總復雜度為O(nlogn)。這相當於用遞歸樹的方法對歸並排序的復雜度進行了分析。假設，歸並排序的復雜度為T(n)，T(n)由兩個T(n/2)和一個關於n的線性時間組成，那麼T(n)=2*T(n/2)+O(n)。不斷展開這個式子我們可以同樣可以得到T(n)=O(nlogn)的結論，你可以自己試試。如果你能在線性的時間里把分別計算出的兩組不同數據的結果合並在一起，根據T(n)=2*T(n/2)+O(n)=O(nlogn)，那麼我們就可以構造O(nlogn)的分治演算法。這個結論後面經常用。我們將在計算幾何部分舉一大堆類似的例子。
如果你第一次見到這么詭異的演算法，你可能會對這個感興趣。分治是遞歸的一種應用。這是我們第一次接觸遞歸運算。下面說的快速排序也是用的遞歸的思想。遞歸程序的復雜度分析通常和上面一樣，主定理(Master Theory)可以簡化這個分析過程。主定理和本文內容離得太遠，我們以後也不會用它，因此我們不介紹它，大家可以自己去查。有個名詞在這里的話找學習資料將變得非常容易，我最怕的就是一個東西不知道叫什麼名字，半天找不到資料。
歸並排序有一個有趣的副產品。利用歸並排序能夠在O(nlogn)的時間里計算出給定序列里逆序對的個數。你可以用任何一種平衡二叉樹來完成這個操作，但用歸並排序統計逆序對更方便。我們討論逆序對一般是說的一個排列中的逆序對，因此這里我們假設所有數不相同。假如我們想要數1, 6, 3, 2, 5, 4中有多少個逆序對，我們首先把這個數列分為左右兩段。那麼一個逆序對只可能有三種情況：兩個數都在左邊，兩個數都在右邊，一個在左一個在右。在左右兩段分別處理完後，線性合並的過程中我們可以順便算出所有第三種情況的逆序對有多少個。換句話說，我們能在線性的時間里統計出A隊列的某個數比B隊列的某個數大有多少種情況。
A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6
B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ……
輸出： 輸出：1 輸出：1 2 輸出：1 2 3 輸出：1 2 3 4
每一次從B隊列取出一個數時，我們就知道了在A隊列中有多少個數比B隊列的這個數大，它等於A隊列現在還剩的數的個數。比如，當我們從B隊列中取出2時，我們同時知道了A隊列的3和6兩個數比2大。在合並操作中我們不斷更新A隊列中還剩幾個數，在每次從B隊列中取出一個數時把當前A隊列剩的數目加進最終答案里。這樣我們算出了所有「大的數在前一半，小的數在後一半」的情況，其餘情況下的逆序對在這之前已經被遞歸地算過了。
============================華麗的分割線============================
堆排序(Heap Sort)利用了堆(Heap)這種數據結構（什麼是堆？）。堆的插入操作是平均常數的，而刪除一個根節點需要花費O(log n)的時間。因此，完成堆排序需要線性時間建立堆（把所有元素依次插入一個堆），然後用總共O(nlogn)的時間不斷取出最小的那個數。只要堆會搞，堆排序就會搞。堆在那篇日誌里有詳細的說明，因此這里不重復說了。
============================華麗的分割線============================
快速排序(Quick Sort)也應用了遞歸的思想。我們想要把給定序列分成兩段，並對這兩段分別進行排序。一種不錯的想法是，選取一個數作為「關鍵字」，並把其它數分割為兩部分，把所有小於關鍵字的數都放在關鍵字的左邊，大於關鍵字的都放在右邊，然後遞歸地對左邊和右邊進行排序。把該區間內的所有數依次與關鍵字比較，我們就可以在線性的時間里完成分割的操作。完成分割操作有很多有技巧性的實現方法，比如最常用的一種是定義兩個指針，一個從前往後找找到比關鍵字大的，一個從後往前找到比關鍵字小的，然後兩個指針對應的元素交換位置並繼續移動指針重復剛才的過程。這只是大致的方法，具體的實現還有很多細節問題。快速排序是我們最常用的代碼之一，網上的快速排序代碼五花八門，各種語言，各種風格的都有。大家可以隨便找一個來看看，我說過了我們講演算法但不講如何實現。NOIp很簡單，很多人NOIp前就背了一個快速排序代碼就上戰場了。當時我把快速排序背完了，抓緊時間還順便背了一下歷史，免得晚上聽寫又不及格。
不像歸並排序，快速排序的時間復雜度很難計算。我們可以看到，歸並排序的復雜度最壞情況下也是O(nlogn)的，而快速排序的最壞情況是O(n^2)的。如果每一次選的關鍵字都是當前區間里最大（或最小）的數，那麼這樣將使得每一次的規模只減小一個數，這和插入排序、選擇排序等平方級排序沒有區別。這種情況不是不可能發生。如果你每次選擇關鍵字都是選擇的該區間的第一個數，而給你的數據恰好又是已經有序的，那你的快速排序就完蛋了。顯然，最好情況是每一次選的數正好就是中位數，這將把該區間平分為兩段，復雜度和前面討論的歸並排序一模一樣。根據這一點，快速排序有一些常用的優化。比如，我們經常從數列中隨機取一個數當作是關鍵字（而不是每次總是取固定位置上的數），從而盡可能避免某些特殊的數據所導致的低效。更好的做法是隨機取三個數並選擇這三個數的中位數作為關鍵字。而對三個數的隨機取值反而將花費更多的時間，因此我們的這三個數可以分別取數列的頭一個數、末一個數和正中間那個數。另外，當遞歸到了一定深度發現當前區間里的數只有幾個或十幾個時，繼續遞歸下去反而費時，不如返回插入排序後的結果。這種方法同時避免了當數字太少時遞歸操作出錯的可能。
下面我們證明，快速排序演算法的平均復雜度為O(nlogn)。不同的書上有不同的解釋方法，這里我選用演算法導論上的講法。它更有技巧性一些，更有趣一些，需要轉幾個彎才能想明白。
看一看快速排序的代碼。正如我們提到過的那種分割方法，程序在經過若干次與關鍵字的比較後才進行一次交換，因此比較的次數比交換次數更多。我們通過證明一次快速排序中元素之間的比較次數平均為O(nlogn)來說明快速排序演算法的平均復雜度。證明的關鍵在於，我們需要算出某兩個元素在整個演算法過程中進行過比較的概率。
我們舉一個例子。假如給出了1到10這10個數，第一次選擇關鍵字7將它們分成了{1,2,3,4,5,6}和{8,9,10}兩部分，遞歸左邊時我們選擇了3作為關鍵字，使得左部分又被分割為{1,2}和{4,5,6}。我們看到，數字7與其它所有數都比較過一次，這樣才能實現分割操作。同樣地，1到6這6個數都需要與3進行一次比較（除了它本身之外）。然而，3和9決不可能相互比較過，2和6也不可能進行過比較，因為第一次出現在3和9，2和6之間的關鍵字把它們分割開了。也就是說，兩個數A(i)和A(j)比較過，當且僅當第一個滿足A(i)<=x<=A(j)的關鍵字x恰好就是A(i)或A(j) （假設A(i)比A(j)小）。我們稱排序後第i小的數為Z(i)，假設i<j，那麼第一次出現在Z(i)和Z(j)之間的關鍵字恰好就是Z(i)或Z(j)的概率為2/(j-i+1)，這是因為當Z(i)和Z(j)之間還不曾有過關鍵字時，Z(i)和Z(j)處於同一個待分割的區間，不管這個區間有多大，不管遞歸到哪裡了，關鍵字的選擇總是隨機的。我們得到，Z(i)和Z(j)在一次快速排序中曾經比較過的概率為2/(j-i+1)。
現在有四個數，2,3,5,7。排序時，相鄰的兩個數肯定都被比較過，2和5、3和7都有2/3的概率被比較過，2和7之間被比較過有2/4的可能。也就是說，如果對這四個數做12次快速排序，那麼2和3、3和5、5和7之間一共比較了12*3=36次，2和5、3和7之間總共比較了8*2=16次，2和7之間平均比較了6次。那麼，12次排序中總的比較次數期望值為36+16+6=58。我們可以計算出單次的快速排序平均比較了多少次：58/12=29/6。其實，它就等於6項概率之和，1+1+1+2/3+2/3+2/4=29/6。這其實是與期望值相關的一個公式。
同樣地，如果有n個數，那麼快速排序平均需要的比較次數可以寫成下面的式子。令k=j-i，我們能夠最終得到比較次數的期望值為O(nlogn)。
這里用到了一個知識：1+1/2+1/3+...+1/n與log n增長速度相同，即∑(1/n)=Θ(log n)。它的證明放在本文的最後。
在三種O(nlogn)的排序演算法中，快速排序的理論復雜度最不理想，除了它以外今天說的另外兩種演算法都是以最壞情況O(nlogn)的復雜度進行排序。但實踐上看快速排序效率最高（不然為啥叫快速排序呢），原因在於快速排序的代碼比其它同復雜度的演算法更簡潔，常數時間更小。
快速排序也有一個有趣的副產品：快速選擇給出的一些數中第k小的數。一種簡單的方法是使用上述任一種O(nlogn)的演算法對這些數進行排序並返回排序後數組的第k個元素。快速選擇(Quick Select)演算法可以在平均O(n)的時間完成這一操作。它的最壞情況同快速排序一樣，也是O(n^2)。在每一次分割後，我們都可以知道比關鍵字小的數有多少個，從而確定了關鍵字在所有數中是第幾小的。我們假設關鍵字是第m小。如果k=m，那麼我們就找到了答案——第k小元素即該關鍵字。否則，我們遞歸地計算左邊或者右邊：當k<m時，我們遞歸地尋找左邊的元素中第k小的；當k>m時，我們遞歸地尋找右邊的元素中第k-m小的數。由於我們不考慮所有的數的順序，只需要遞歸其中的一邊，因此復雜度大大降低。復雜度平均線性，我們不再具體證了。
還有一種演算法可以在最壞O(n)的時間里找出第k小元素。那是我見過的所有演算法中最沒有實用價值的演算法。那個O(n)只有理論價值。
============================華麗的分割線============================
我們前面證明過，僅僅依靠交換相鄰元素的操作，復雜度只能達到O(n^2)。於是，人們嘗試交換距離更遠的元素。當人們發現O(nlogn)的排序演算法似乎已經是極限的時候，又是什麼制約了復雜度的下界呢？我們將要討論的是更底層的東西。我們仍然假設所有的數都不相等。
我們總是不斷在數與數之間進行比較。你可以試試，只用4次比較絕對不可能給4個數排出順序。每多進行一次比較我們就又多知道了一個大小關系，從4次比較中一共可以獲知4個大小關系。4個大小關系共有2^4=16種組合方式，而4個數的順序一共有4!=24種。也就是說，4次比較可能出現的結果數目不足以區分24種可能的順序。更一般地，給你n個數叫你排序，可能的答案共有n!個，k次比較只能區分2^k種可能，於是只有2^k>=n!時才有可能排出順序。等號兩邊取對數，於是，給n個數排序至少需要log2(n!)次。注意，我們並沒有說明一定能通過log2(n!)次比較排出順序。雖然2^5=32超過了4!，但這不足以說明5次比較一定足夠。如何用5次比較確定4個數的大小關系還需要進一步研究。第一次例外發生在n=12的時候，雖然2^29>12!，但現已證明給12個數排序最少需要30次比較。我們可以證明log(n!)的增長速度與nlogn相同，即log(n!)=Θ(nlogn)。這是排序所需要的最少的比較次數，它給出了排序復雜度的一個下界。log(n!)=Θ(nlogn)的證明也附在本文最後。
這篇日誌的第三題中證明log2(N)是最優時用到了幾乎相同的方法。那種「用天平稱出重量不同的那個球至少要稱幾次」一類題目也可以用這種方法來解決。事實上，這里有一整套的理論，它叫做資訊理論。資訊理論是由香農(Shannon)提出的。他用對數來表示信息量，用熵來表示可能的情況的隨機性，通過運算可以知道你目前得到的信息能夠怎樣影響最終結果的確定。如果我們的信息量是以2為底的，那資訊理論就變成信息學了。從根本上說，計算機的一切信息就是以2為底的信息量(bits=binary digits)，因此我們常說香農是數字通信之父。資訊理論和熱力學關系密切，比如熵的概念是直接從熱力學的熵定義引申過來的。和這個有關的東西已經嚴重偏題了，這里不說了，有興趣可以去看《資訊理論與編碼理論》。我對這個也很有興趣，半懂不懂的，很想了解更多的東西，有興趣的同志不妨加入討論。物理學真的很神奇，利用物理學可以解決很多純數學問題，我有時間的話可以舉一些例子。我他媽的為啥要選文科呢。
後面將介紹的三種排序是線性時間復雜度，因為，它們排序時根本不是通過互相比較來確定大小關系的。
附1：∑(1/n)=Θ(log n)的證明
首先我們證明，∑(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/2，使得兩個1/2加起來湊成一個1；再把1/5,1/6和1/7全部變成1/4，這樣四個1/4加起來又是一個1。我們把所有1/2^k的後面2^k-1項全部擴大為1/2^k，使得這2^k個分式加起來是一個1。現在，1+1/2+...+1/n裡面產生了幾個1呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的擴大後原式各項總和為log n。O(logn)是∑(1/n)的復雜度上界。
然後我們證明，∑(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/4，使得兩個1/4加起來湊成一個1/2；再把1/5,1/6和1/7全部變成1/8，這樣四個1/8加起來又是一個1/2。我們把所有1/2^k的前面2^k-1項全部縮小為1/2^k，使得這2^k個分式加起來是一個1/2。現在，1+1/2+...+1/n裡面產生了幾個1/2呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的縮小後原式各項總和為1/2*logn。Ω(logn)是∑(1/n)的復雜度下界。
附2：log(n!)=Θ(nlogn)的證明
首先我們證明，log(n!)=O(nlogn)。顯然n!<n^n，兩邊取對數我們得到log(n!)<log(n^n)，而log(n^n)就等於nlogn。因此，O(nlogn)是log(n!)的復雜度上界。
然後我們證明，log(n!)=Ω(nlogn)。n!=n(n-1)(n-2)(n-3)....1，把前面一半的因子全部縮小到n/2，後面一半因子全部捨去，顯然有n!>(n/2)^(n/2)。兩邊取對數，log(n!)>(n/2)log(n/2)，後者即Ω(nlogn)。因此，Ω(nlogn)是log(n!)的復雜度下界。
今天寫到這里了，大家幫忙校對哦
Matrix67原創
轉貼請註明出處
② 請教演算法導論中 T = 2T + nlgn 為什麼不能用主定理
T=2T+nlgn？
那T=-nlgn，負數？
③ 怎麼將C語言遞歸演算法轉化成「遞歸方程」該種演算法時間的復雜度怎麼求有固定的方法嗎
不知道你是怎麼得出"遞歸演算法可以轉化成方程"這個結論的呢? 如果真是這樣,那麼世界上恐怕很多NP問題都可以解決了. 深度優先搜索很多時候就是遞歸結構的,但是並沒有什麼辦法將其轉化成方程解決.
我猜想也許你說的是很特殊的一類遞歸問題,這類遞歸問題可以用數學函數來表達.例如計算階乘的時候,n! = (n-1)*n. 那這個是怎麼的出來的就真沒有固定的套路,但是一般的思想是考慮如何把一個問題轉化成規模更小的幾個問題.
④ 用C++交換排序
所謂交換，就是根據序列中兩個記錄值的比較結果來對換這兩個記錄在序列中的位置。交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。常見的交換排序有冒泡排序（Bubble Sort），雞尾酒排序（Cocktail Sort），奇偶排序（OddEven Sort），地精排序（Gnome Sort），快速排序（Quick Sort），臭皮匠排序（Stooge Sort），梳排序（Comb Sort），Bogo排序（Bogo sort）。下面介紹前六種：
（一）冒泡排序
最差時間復雜度：O(n^2)
最優時間復雜度：O(n)
平均時間復雜度：O(n^2)
最差空間復雜度：總共O(n)，需要輔助空間O(1)
穩定性：穩定
冒泡排序（Bubble Sort），它重復地走訪過要排序的數列，一次比較兩個元素如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。
冒泡排序演算法的運作如下：
1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
3.針對所有的元素重復以上的步驟，除了最後一個。
4.持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
實現代碼：
[cpp] view plain
void BubbleSort(int *a, int len)
{
for (int i=0; i<len; i++)
{
for (int j=len-1; j>i; j--)
{
if (a[j]<a[j-1])
swap(a[j], a[j-1]);
}
}
}
（二）雞尾酒排序
最差時間復雜度：O(n^2)
最優時間復雜度：O(n)
平均時間復雜度：O(n^2)
穩定性：穩定
雞尾酒排序（Cocktail sort），是冒泡排序的一種變形。它與冒泡排序的不同之處在於排序時是以雙向在序列中進行排序。數組中的數字本是無規律的排放，先對數組從左到右進行冒泡排序（升序），把最大值放到最右端，然後對數組從右到左進行冒泡排序（降序），把最小的數字放到最左端。然後再以此類推，以此改變冒泡的方向，並不斷縮小未排序元素的范圍。直到在一趟雙向冒泡後沒有發生交換，排序結束。
實現代碼：
[cpp] view plain
void CocktailSort(int* a, int len)
{
int bottom = 0;
int top = len-1;
bool swapped = true;
while (swapped)
{
swapped = false;
for (int i=bottom; i<top; i++)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
top = top-1;
for (int i=top; i>bottom; i--)
{
if (a[i]<a[i-1])
{
swap(a[i], a[i-1]);
swapped = true;
}
}
bottom = bottom+1;
}
}
（三）奇偶排序
最差時間復雜度：O(n^2)
穩定性：穩定
奇偶排序（OddEven Sort），是一種相對簡單的排序演算法，最初發明用於有本地互聯的並行計算。此演算法通過比較數組中相鄰的（奇-偶）位置數字對，如果該奇偶對是錯誤的順序（第一個大於第二個），則交換。下一步重復該操作，但針對所有的（偶-奇）位置數字對。如此交替下去，直到不發生交換，則排序結束。
在並行計算排序中，使用該演算法，每個處理器對應處理一個值，並僅有與左右鄰居的本地互連。所有處理器可同時與鄰居進行比較、交換操作，交替以奇-偶、偶-奇的順序。該演算法由Habermann在1972年最初發表並展現了在並行處理上的效率。但在單處理器串列運行此演算法，類似冒泡排序，較為簡單但效率並不特別高。
實現代碼：
[cpp] view plain
void OddEvenSort(int *a, int len)
{
bool swapped = true;
while (swapped)
{
swapped = false;
for (int i=0; i<len-1; i=i+2)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
for (int i=1; i<len-1; i=i+2)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
}
}
（四）地精排序
最差時間復雜度：O(n^2)
最優時間復雜度：O(n)
平均時間復雜度：O(n^2)
穩定性：穩定
地精排序（Gnome Sort），被Dick Grune稱為最簡單的排序演算法。整個演算法只有一層循環，默認情況下前進冒泡，一旦遇到冒泡的情況發生就往回冒，直到把這個數字放好，然後繼續前進，前進到數組最後一個數結束。此排序演算法雖然代碼極短，但效率不高。
實現代碼：
[cpp] view plain
void GnomeSort(int *a, int len)
{
int i=0;
while (i<len)
{
if (i==0 || a[i-1]<=a[i]){
i++;
}
else {
swap(a[i], a[i-1]);
i--;
}
}
}
（五）快速排序
最差時間復雜度：O(n^2)
最優時間復雜度：O(nlogn)
平均時間復雜度：O(nlogn)
穩定性：不穩定
快速排序（Quick Sort），使用分治法策略來把一個串列分為兩個子串列，左邊子串的值總小於右邊的子串。此演算法的三個步驟：
1．分解：將數組A[l...r]劃分成兩個（可能空）子數組A[l...p-1]和A[p+1...r]，使得A[l...p-1]中的每個元素都小於等於A(p)，而且，小於等於A[p+1...r]中的元素。下標p也在這個劃分過程中計算。
2．解決：通過遞歸調用快速排序，對數組A[l...p-1]和A[p+1...r]排序。
3．合並：因為兩個子數組時就地排序，將它們的合並並不需要操作，整個數組A[l..r]已經排序。
實現代碼（其他實現方法見「三種快速排序演算法的實現」）：
[cpp] view plain
int partition(int* a, int left, int right)
{
int x = a[right];
int i = left-1, j = right;
for (;;)
{
while(a[++i] < x) { }
while(a[--j] > x) { if(j==left) break;}
if(i < j)
swap(a[i], a[j]);
else break;
}
swap(a[i],a[right]);
return i;
}
void quickSort(int* a, int left, int right)
{
if (left<right)
{
int p = partition(a, left, right);
quickSort(a, left, p-1);
quickSort(a, p+1, right);
}
}
（六）臭皮匠排序
最差時間復雜度：O(n^2.7)
臭皮匠排序（Stooge Sort），是一種低效的排序演算法，在《演算法導論》第二版第7章的思考題中被提到，是由Howard Fine等教授提出的所謂「漂亮的」排序演算法。將數列平分為三個子串，依次遞歸排序前兩個子串、後兩個子串、前兩個子串，最後確保整個數列有序。此演算法在最壞情況下的遞歸式為T(n) = 3T(2n/3) + 1。由主定理很容易知道它的演算法復雜性為：T(n) = O(n^log(3/2, 3))。很顯然log(3/2, 3))>2，也就是說這個演算法比插入排序的O(n^2)性能還差。
實現代碼：
[cpp] view plain
void StoogeSort(int *a, int i, int j)
{
if(a[i]>a[j])
swap(a[i], a[j]);
if((i+1)>=j)
return;
int k = (j-i+1)/3;
StoogeSort(a, i, j-k);
StoogeSort(a, i+k, j);
StoogeSort(a, i, j-k);
}
⑤ 演算法導論裡面的大師解法是什麼 用大師解法計算下面遞歸表達式的時間復雜度. T(n)=2T(n/2) + Θ(n^0.1)
#a i從0循環到n，演算法復雜度為O(n)。
#b 一共要做n^2/2次加法，演算法復雜度為O(n^2)。
#c 要求一個k，滿足2^k>=n ，演算法復雜度為O(log(n))
#d 注意到這個函數做的事跟#c的函數恰好相反，演算法復雜度相同，也是O(log(n))
#e 因為已算出#g每次做3(n-3)次加法，那麼i從1到n，一共做2/3*(n^2-5n+6)次加法，所以復雜度為O(n^2)。
#f 這個函數可以寫成公式T(n)=T(n-2)+T(n-1)，這個遞歸式跟黃金分割有關系，解這個遞歸式，可以知道 T(n) = O((√5-1/2)^n)
#g 函數調用一共做3(n-3)次加法，所以復雜度為O(n)
PenitentSin 這位兄台的#c 算的不對啦，#g也不對。還有#f，這個雖然是遞歸，但不是遞歸就等於指數級的復雜度，要解遞歸方程才能斷定的。
關於演算法復雜度，《演算法導論》一書中第四章有一個主定理，記住這個定理之後，這些問題就小case了（除了復雜遞歸之外）。
⑥ 中位數演算法
樓上才是白痴，自己什麼也不懂不要說的別人也是什麼也不懂。
就是因為有了你們這種人，世界多花了巨額的代價來多做不必要的工作。
很明顯樓主不是你這樣的。
實數的排序演算法復雜度是O(nlogn)，這個中位數可以做到O(n)
下面我來說明這個演算法的過程。
演算法是基於歸並排序（merge-sort）的更改。
把中位數更改為等價的敘述。無序的n個數中的第int(n/2)大的元素。(k=int(n/2))
1.隨機化數據，這樣可以保證因為輸出時候的對稱性（可能的順序輸入）而造成的演算法退化。
for (int i=number.count;i>=0;i--)
swap(number[i],number[random(0,i-1)]);//swap，交換，random，0，k閉區間的隨機數。
2.歸並排序主過程。
mergesort(a,b,k)//尋找number數組中從下標a到下標b的元素中的第k大的元素。
{
t=number[a];
把這a,b中的元素從排，使a~p-1的元素比t小，p+1~b的元素比t大。number[p]=t;//O(n)，這步你構造吧。不是很困難，偽代碼不寫太多。
//此時比t小元素有p-1-a+1=p-a個,
//分情況，如果k=p-a+1,返回t
//如果k>p-a+1,返回mergesort(p+1,b,k-(p-a+1))
//如果k<p-a+1,返回mergesort(a,p-1,k)
}
以上演算法T(n)=T(n/2)+O(n)
根據主定理，T(n)=O(n)。
再次bs樓上的無知和狂妄的態度。
⑦ ALGORITHMS怎麼樣
遞推公式那節，主定理的證明沒有考慮葉節點的代價，而且，分解和合 並的代價應該計算到倒數第二層才對。 語言簡練清晰，倒還是不錯的。 和演算法導論相比，似乎......