第一篇：各種排序算法的穩(wěn)定性和時間復(fù)雜度小結(jié)
各種排序算法的穩(wěn)定性和時間復(fù)雜度小結(jié)
選擇排序、快速排序、希爾排序、堆排序不是穩(wěn)定的排序算法，冒泡排序、插入排序、歸并排序和基數(shù)排序是穩(wěn)定的排序算法。
冒泡法：
這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因為它的工作看來象是冒泡：
復(fù)雜度為O(n*n)。當數(shù)據(jù)為正序，將不會有交換。復(fù)雜度為O(0)。
直接插入排序：O(n*n)
選擇排序：O(n*n)
快速排序：平均時間復(fù)雜度log2(n)*n，所有內(nèi)部排序方法中最高好的，大多數(shù)情況下總是最好的。
歸并排序：log2(n)*n
堆排序：log2(n)*n
希爾排序：算法的復(fù)雜度為n的1.2次冪
關(guān)于快速排序分析
這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析算法：
首先我們考慮最理想的情況
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)其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那么他將變成交換法（由于使用了遞歸，情況更糟）。但是你認為這種情況發(fā)生的幾率有多大？？呵呵，你完全不必擔心這個問題。實踐證明，大多數(shù)的情況，快速排序總是最好的。
如果你擔心這個問題，你可以使用堆排序，這是一種穩(wěn)定的O(log2(n)*n)算法，但是通常情況下速度要慢 于快速排序（因為要重組堆）。
本文是針對老是記不住這個或者想真正明白到底為什么是穩(wěn)定或者不穩(wěn)定的人準備的。
首先，排序算法的穩(wěn)定性大家應(yīng)該都知道，通俗地講就是能保證排序前2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序相同。在簡單形式化一下，如果Ai = Aj, Ai原來在位置前，排序后Ai還是要在Aj位置前。
其次，說一下穩(wěn)定性的好處。排序算法如果是穩(wěn)定的，那么從一個鍵上排序，然后再從另一個鍵上排序，第一個鍵排序的結(jié)果可以為第二個鍵排序所用。基數(shù)排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。另外，如果排序算法穩(wěn)定，對基于比較的排序算法而言，元素交換的次數(shù)可能會少一些(個人感覺，沒有證實)。
回到主題，現(xiàn)在分析一下常見的排序算法的穩(wěn)定性，每個都給出簡單的理由。
(1)冒泡排序
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較，交換也發(fā)生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。
(2)選擇排序
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果當前元素比一個元素小，而該小的元素又出現(xiàn)在一個和當前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中2個5的相對前后順序就被破壞了，所以選擇排序不是一個穩(wěn)定的排序算法。
(3)插入排序
插入排序是在一個已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經(jīng)有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。
(4)快速排序
快速排序有兩個方向，左邊的i下標一直往右走，當a[i] <= a[center_index]，其中center_index是中樞元素的數(shù)組下標，一般取為數(shù)組第0個元素。而右邊的j下標一直往左走，當a[j] > a[center_index]。如果i和j都走不動了，i <= j, 交換a[i]和a[j],重復(fù)上面的過程，直到i>j。交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩(wěn)定性打亂，比如序列為 5 3 3 4 3 8 9 10 11，現(xiàn)在中樞元素5和3(第5個元素，下標從1開始計)交換就會把元素3的穩(wěn)定性打亂，所以快速排序是一個不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在中樞元素和a[j]交換的時刻。
(5)歸并排序
歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素(認為直接有序)或者2個序列(1次比較和交換),然后把各個有序的段序列合并成一個有序的長序列，不斷合并直到原序列全部排好序。可以發(fā)現(xiàn)，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也沒有人故意交換，這不會破壞穩(wěn)定性。那么，在短的有序序列合并的過程中，穩(wěn)定是是否受到破壞？沒有，合并過程中我們可以保證如果兩個當前元素相等時，我們把處在前面的序列的元素保存在結(jié)果序列的前面，這樣就保證了穩(wěn)定性。所以，歸并排序也是穩(wěn)定的排序算法。
(6)基數(shù)排序
基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序，最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前?；鶖?shù)排序基于分別排序，分別收集，所以其是穩(wěn)定的排序算法。
(7)希爾排序(shell)
希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序的時間復(fù)雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。
(8)堆排序
我們知道堆的結(jié)構(gòu)是節(jié)點i的孩子為2*i和2*i+1節(jié)點，大頂堆要求父節(jié)點大于等于其2個子節(jié)點，小頂堆要求父節(jié)點小于等于其2個子節(jié)點。在一個長為n的序列，堆排序的過程是從第n/2開始和其子節(jié)點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩(wěn)定性。但當為n/2-1, n/2-2,...1這些個父節(jié)點選擇元素時，就會破壞穩(wěn)定性。有可能第n/2個父節(jié)點交換把后面一個元素交換過去了，而第n/2-1個父節(jié)點把后面一個相同的元素沒有交換，那么這2個相同的元素之間的穩(wěn)定性就被破壞了。所以，堆排序不是穩(wěn)定的排序算法快速排序（QuickSort）
快速排序是一個就地排序，分而治之，大規(guī)模遞歸的算法。從本質(zhì)上來說，它是歸并排序的就地版本?？焖倥判蚩梢杂上旅嫠牟浇M成。
（1）如果不多于1個數(shù)據(jù)，直接返回。
（2）一般選擇序列最左邊的值作為支點數(shù)據(jù)。
（3）將序列分成2部分，一部分都大于支點數(shù)據(jù)，另外一部分都小于支點數(shù)據(jù)。（4）對兩邊利用遞歸排序數(shù)列。
快速排序比大部分排序算法都要快。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法，但是就通常情況而言，沒有比它更快的了?？焖倥判蚴沁f歸的，對于內(nèi)存非常有限的機器來說，它不是一個好的選擇。歸并排序（MergeSort）
歸并排序先分解要排序的序列，從1分成2，2分成4，依次分解，當分解到只有1個一組的時候，就可以排序這些分組，然后依次合并回原來的序列中，這樣就可以排序所有數(shù)據(jù)。合并排序比堆排序稍微快一點，但是需要比堆排序多一倍的內(nèi)存空間，因為它需要一個額外的數(shù)組。堆排序（HeapSort）
堆排序適合于數(shù)據(jù)量非常大的場合（百萬數(shù)據(jù)）。
堆排序不需要大量的遞歸或者多維的暫存數(shù)組。這對于數(shù)據(jù)量非常巨大的序列是合適的。比如超過數(shù)百萬條記錄，因為快速排序，歸并排序都使用遞歸來設(shè)計算法，在數(shù)據(jù)量非常大的時候，可能會發(fā)生堆棧溢出錯誤。
堆排序會將所有的數(shù)據(jù)建成一個堆，最大的數(shù)據(jù)在堆頂，然后將堆頂數(shù)據(jù)和序列的最后一個數(shù)據(jù)交換。接下來再次重建堆，交換數(shù)據(jù)，依次下去，就可以排序所有的數(shù)據(jù)。Shell排序（ShellSort）
Shell排序通過將數(shù)據(jù)分成不同的組，先對每一組進行排序，然后再對所有的元素進行一次插入排序，以減少數(shù)據(jù)交換和移動的次數(shù)。平均效率是O(nlogn)。其中分組的合理性會對算法產(chǎn)生重要的影響?，F(xiàn)在多用D.E.Knuth的分組方法。
Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相對比較簡單，它適合于數(shù)據(jù)量在5000以下并且速度并不是特別重要的場合。它對于數(shù)據(jù)量較小的數(shù)列重復(fù)排序是非常好的。插入排序（InsertSort）
插入排序通過把序列中的值插入一個已經(jīng)排序好的序列中，直到該序列的結(jié)束。插入排序是對冒泡排序的改進。它比冒泡排序快2倍。一般不用在數(shù)據(jù)大于1000的場合下使用插入排序，或者重復(fù)排序超過200數(shù)據(jù)項的序列。冒泡排序（BubbleSort）
冒泡排序是最慢的排序算法。在實際運用中它是效率最低的算法。它通過一趟又一趟地比較數(shù)組中的每一個元素，使較大的數(shù)據(jù)下沉，較小的數(shù)據(jù)上升。它是O(n^2)的算法。交換排序（ExchangeSort）和選擇排序（SelectSort）
這兩種排序方法都是交換方法的排序算法，效率都是 O(n2)。在實際應(yīng)用中處于和冒泡排序基本相同的地位。它們只是排序算法發(fā)展的初級階段，在實際中使用較少?；鶖?shù)排序（RadixSort）
基數(shù)排序和通常的排序算法并不走同樣的路線。它是一種比較新穎的算法，但是它只能用于整數(shù)的排序，如果我們要把同樣的辦法運用到浮點數(shù)上，我們必須了解浮點數(shù)的存儲格式，并通過特殊的方式將浮點數(shù)映射到整數(shù)上，然后再映射回去，這是非常麻煩的事情，因此，它的使用同樣也不多。而且，最重要的是，這樣算法也需要較多的存儲空間。總結(jié)
第二篇：算法的時間復(fù)雜度和空間復(fù)雜度-總結(jié)
算法的時間復(fù)雜度和空間復(fù)雜度-總結(jié)
通常，對于一個給定的算法，我們要做兩項分析。第一是從數(shù)學上證明算法的正確性，這一步主要用到形式化證明的方法及相關(guān)推理模式，如循環(huán)不變式、數(shù)學歸納法等。而在證明算法是正確的基礎(chǔ)上，第二部就是分析算法的時間復(fù)雜度。算法的時間復(fù)雜度反映了程序執(zhí)行時間隨輸入規(guī)模增長而增長的量級，在很大程度上能很好反映出算法的優(yōu)劣與否。因此，作為程序員，掌握基本的算法時間復(fù)雜度分析方法是很有必要的。
算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行時所消耗的時間來度量。而度量一個程序的執(zhí)行時間通常有兩種方法。
一、事后統(tǒng)計的方法
這種方法可行，但不是一個好的方法。該方法有兩個缺陷：一是要想對設(shè)計的算法的運行性能進行評測，必須先依據(jù)算法編制相應(yīng)的程序并實際運行；二是所得時間的統(tǒng)計量依賴于計算機的硬件、軟件等環(huán)境因素，有時容易掩蓋算法本身的優(yōu)勢。
二、事前分析估算的方法
因事后統(tǒng)計方法更多的依賴于計算機的硬件、軟件等環(huán)境因素，有時容易掩蓋算法本身的優(yōu)劣。因此人們常常采用事前分析估算的方法。
在編寫程序前，依據(jù)統(tǒng)計方法對算法進行估算。一個用高級語言編寫的程序在計算機上運行時所消耗的時間取決于下列因素：
(1).算法采用的策略、方法；(2).編譯產(chǎn)生的代碼質(zhì)量；(3).問題的輸入規(guī)模；(4).機器執(zhí)行指令的速度。
一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)3種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，則算法時間取決于兩者的綜合效果。為了便于比較同一個問題的不同算法，通常的做法是，從算法中選取一種對于所研究的問題（或算法類型）來說是基本操作的原操作，以該基本操作的重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。
1、時間復(fù)雜度
（1）時間頻度 一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)。
（2）時間復(fù)雜度 在剛才提到的時間頻度中，n稱為問題的規(guī)模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律。為此，我們引入時間復(fù)雜度概念。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n))為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。另外，上面公式中用到的 Landau符號其實是由德國數(shù)論學家保羅·巴赫曼（Paul Bachmann）在其1892年的著作《解析數(shù)論》首先引入，由另一位德國數(shù)論學家艾德蒙·朗道（Edmund Landau）推廣。Landau符號的作用在于用簡單的函數(shù)來描述復(fù)雜函數(shù)行為，給出一個上或下（確）界。在計算算法復(fù)雜度時一般只用到大O符號，Landau符號體系中的小o符號、Θ符號等等比較不常用。這里的O，最初是用大寫希臘字母，但現(xiàn)在都用大寫英語字母O；小o符號也是用小寫英語字母o，Θ符號則維持大寫希臘字母Θ。
T(n)= Ο(f(n))表示存在一個常數(shù)C，使得在當n趨于正無窮時總有 T(n)≤ C * f(n)。簡單來說，就是T(n)在n趨于正無窮時最大也就跟f(n)差不多大。也就是說當n趨于正無窮時T(n)的上界是C * f(n)。其雖然對f(n)沒有規(guī)定，但是一般都是取盡可能簡單的函數(shù)。例如，O(2n2+n +1)= O(3n2+n+3)= O(7n2 + n)= O(n2)，一般都只用O(n2)表示就可以了。注意到大O符號里隱藏著一個常數(shù)C，所以f(n)里一般不加系數(shù)。如果把T(n)當做一棵樹，那么O(f(n))所表達的就是樹干，只關(guān)心其中的主干，其他的細枝末節(jié)全都拋棄不管。在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個常數(shù)，則時間復(fù)雜度為O(1),另外，在時間頻度不相同時，時間復(fù)雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復(fù)雜度相同，都為O(n2)。按數(shù)量級遞增排列，常見的時間復(fù)雜度有：常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),...，k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。
從圖中可見，我們應(yīng)該盡可能選用多項式階O(n)的算法，而不希望用指數(shù)階的算法。常見的算法時間復(fù)雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
一般情況下，對一個問題（或一類算法）只需選擇一種基本操作來討論算法的時間復(fù)雜度即可，有時也需要同時考慮幾種基本操作，甚至可以對不同的操作賦予不同的權(quán)值，以反映執(zhí)行不同操作所需的相對時間，這種做法便于綜合比較解決同一問題的兩種完全不同的算法。
（3）求解算法的時間復(fù)雜度的具體步驟是：
k
⑴ 找出算法中的基本語句；
算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。
⑵ 計算基本語句的執(zhí)行次數(shù)的數(shù)量級；
只需計算基本語句執(zhí)行次數(shù)的數(shù)量級，這就意味著只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡化算法分析，并且使注意力集中在最重要的一點上：增長率。
⑶ 用大Ο記號表示算法的時間性能。
將基本語句執(zhí)行次數(shù)的數(shù)量級放入大Ο記號中。
如果算法中包含嵌套的循環(huán)，則基本語句通常是最內(nèi)層的循環(huán)體，如果算法中包含并列的循環(huán)，則將并列循環(huán)的時間復(fù)雜度相加。例如：
[java] view plaincopy 1.for(i=1;i<=n;i++)2.x++;3.for(i=1;i<=n;i++)4.for(j=1;j<=n;j++)5.x++;
第一個for循環(huán)的時間復(fù)雜度為Ο(n)，第二個for循環(huán)的時間復(fù)雜度為Ο(n2)，則整個算法的時間復(fù)雜度為Ο(n+n2)=Ο(n2)。
Ο(1)表示基本語句的執(zhí)行次數(shù)是一個常數(shù)，一般來說，只要算法中不存在循環(huán)語句，其時間復(fù)雜度就是Ο(1)。其中Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間，而Ο(2n)和Ο(n!)稱為指數(shù)時間。計算機科學家普遍認為前者（即多項式時間復(fù)雜度的算法）是有效算法，把這類問題稱為P（Polynomial,多項式）類問題，而把后者（即指數(shù)時間復(fù)雜度的算法）稱為NP（Non-Deterministic Polynomial, 非確定多項式）問題。
一般來說多項式級的復(fù)雜度是可以接受的，很多問題都有多項式級的解——也就是說，這樣的問題，對于一個規(guī)模是n的輸入，在n^k的時間內(nèi)得到結(jié)果，稱為P問題。有些問題要復(fù)雜些，沒有多項式時間的解，但是可以在多項式時間里驗證某個猜測是不是正確。比如問4294967297是不是質(zhì)數(shù)？如果要直接入手的話，那么要把小于4294967297的平方根的所有素數(shù)都拿出來，看看能不能整除。還好歐拉告訴我們，這個數(shù)等于641和6700417的乘積，不是素數(shù)，很好驗證的，順便麻煩轉(zhuǎn)告費馬他的猜想不成立。大數(shù)分解、Hamilton回路之類的問題，都是可以多項式時間內(nèi)驗證一個“解”是否正確，這類問題叫做NP問題。
（4）在計算算法時間復(fù)雜度時有以下幾個簡單的程序分析法則:
(1).對于一些簡單的輸入輸出語句或賦值語句,近似認為需要O(1)時間
(2).對于順序結(jié)構(gòu),需要依次執(zhí)行一系列語句所用的時間可采用大O下“求和法則” 求和法則:是指若算法的2個部分時間復(fù)雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n), g(n)))特別地,若T1(m)=O(f(m)), T2(n)=O(g(n)),則 T1(m)+T2(n)=O(f(m)+ g(n))(3).對于選擇結(jié)構(gòu),如if語句,它的主要時間耗費是在執(zhí)行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間
(4).對于循環(huán)結(jié)構(gòu),循環(huán)語句的運行時間主要體現(xiàn)在多次迭代中執(zhí)行循環(huán)體以及檢驗循環(huán)條件的時間耗費,一般可用大O下“乘法法則” 乘法法則: 是指若算法的2個部分時間復(fù)雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1*T2=O(f(n)*g(n))(5).對于復(fù)雜的算法,可以將它分成幾個容易估算的部分,然后利用求和法則和乘法法則技術(shù)整個算法的時間復(fù)雜度
另外還有以下2個運算法則:(1)若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))；(2)O(Cf(n))= O(f(n)),其中C是一個正常數(shù)
（5）下面分別對幾個常見的時間復(fù)雜度進行示例說明：(1)、O(1)
Temp=i;i=j;j=temp;以上三條單個語句的頻度均為1，該程序段的執(zhí)行時間是一個與問題規(guī)模n無關(guān)的常數(shù)。算法的時間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。注意：如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復(fù)雜度是O(1)。
(2)、O(n2)
2.1.交換i和j的內(nèi)容
[java] view plaincopy 1.sum=0；（一次）2.for(i=1;i<=n;i++)（n+1次）3.for(j=1;j<=n;j++)（n2次）4.sum++；（n2次）
解：因為Θ(2n2+n+1)=n2（Θ即：去低階項，去掉常數(shù)項，去掉高階項的常參得到），所以T(n)= =O(n2)； 2.2.[java] view plaincopy 1.for(i=1;i 該程序的時間復(fù)雜度T(n)=O(n2).一般情況下，對步進循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)，忽略該語句中步長加 1、終值判別、控制轉(zhuǎn)移等成分，當有若干個循環(huán)語句時，算法的時間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。 (3)、O(n) [java] view plaincopy 1.a=0;2.b=1;① 3.for(i=1;i<=n;i++)② 4.{ 5.s=a+b; ③ 6.b=a; ④ 7.a=s; ⑤ 8.} 解： 語句1的頻度：2, 語句2的頻度： n, 語句3的頻度： n-1, 語句4的頻度：n-1, 語句5的頻度：n-1, T(n)=2+n+3(n-1)=4n-1=O(n).(4)、O(log2n) [java] view plaincopy 1.i=1;① 2.while(i<=n)3.i=i*2;② 解： 語句1的頻度是1, 設(shè)語句2的頻度是f(n), 則：2^f(n)<=n;f(n)<=log2n 取最大值f(n)=log2n, T(n)=O(log2n)(5)、O(n3) [java] view plaincopy 1.for(i=0;i 一個經(jīng)驗規(guī)則：其中c是一個常量，如果一個算法的復(fù)雜度為c、log2n、n、n*log2n ,那么這個算法時間效率比較高，如果是2n ,3n ,n!，那么稍微大一些的n就會令這個算法不能動了，居于中間的幾個則差強人意。 算法時間復(fù)雜度分析是一個很重要的問題，任何一個程序員都應(yīng)該熟練掌握其概念和基本方法，而且要善于從數(shù)學層面上探尋其本質(zhì)，才能準確理解其內(nèi)涵。 2、算法的空間復(fù)雜度 類似于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度(Space Complexity)S(n)定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度。 空間復(fù)雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算法的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面。算法的輸入輸出數(shù)據(jù)所占用的存儲空間是由要解決的問題決定的，是通過參數(shù)表由調(diào)用函數(shù)傳遞而來的，它不隨本算法的不同而改變。存儲算法本身所占用的存儲空間與算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的算法。算法在運行過程中臨時占用的存儲空間隨算法的不同而異，有的算法只需要占用少量的臨時工作單元，而且不隨問題規(guī)模的大小而改變，我們稱這種算法是“就地"進行的，是節(jié)省存儲的算法，如這一節(jié)介紹過的幾個算法都是如此；有的算法需要占用的臨時工作單元數(shù)與解決問題的規(guī)模n有關(guān)，它隨著n的增大而增大，當n較大時，將占用較多的存儲單元，例如將在第九章介紹的快速排序和歸并排序算法就屬于這種情況。 如當一個算法的空間復(fù)雜度為一個常量，即不隨被處理數(shù)據(jù)量n的大小而改變時，可表示為O(1)；當一個算法的空間復(fù)雜度與以2為底的n的對數(shù)成正比時，可表示為0(10g2n)；當一個算法的空I司復(fù)雜度與n成線性比例關(guān)系時，可表示為0(n).若形參為數(shù)組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間，即一個機器字長空間；若形參為引用方式，則也只需要為其分配存儲一個地址的空間，用它來存儲對應(yīng)實參變量的地址，以便由系統(tǒng)自動引用實參變量。 排序算法總結(jié) 所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。當待排序記錄的關(guān)鍵字都不相同時，排序結(jié)果是惟一的，否則排序結(jié)果不惟一。 在待排序的文件中，若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生改變，則稱這種排序方法是不穩(wěn)定的。 要注意的是，排序算法的穩(wěn)定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。 一.插入排序 插入排序的基本思想是每步將一個待排序的記錄按其排序碼值的大小，插到前面已經(jīng)排好的文件中的適當位置，直到全部插入完為止。插入排序方法主要有直接插入排序和希爾排序。 ①.直接插入排序(穩(wěn)定)接插入排序的過程為：在插入第i個記錄時，R1,R2,..Ri-1已經(jīng)排好序，將第i個記錄的排序碼Ki依次和R1,R2,..,Ri-1的排序碼逐個進行比較，找到適當?shù)奈恢?。使用直接插入排序，對于具有n個記錄的文件，要進行n-1趟排序。 代碼如下: void Dir_Insert(int A[],int N)//直接插入排序 { int j,t;for(int i=1;i 希爾(Shell)排序的基本思想是：先取一個小于n的整數(shù)d1作為第一個增量把文件的全部記錄分成d1個組。所有距離為d1的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序；然后，取得第二個增量d2 一般取d1=n/2，di+1=di/2。如果結(jié)果為偶數(shù)，則加1，保證di為奇數(shù)。 希爾排序是不穩(wěn)定的，希爾排序的執(zhí)行時間依賴于增量序列，其平均時間復(fù)雜度為O(n^1.3).代碼如下: void Shell(int A[],int n)//Shell排序 { int i,j,k,t;(n/2)%2 == 0 ? k = n/2+1 : k = n/2;//保證增量為奇數(shù) while(k > 0){ for(j=k;j 二.選擇排序 選擇排序的基本思想是每步從待排序的記錄中選出排序碼最小的記錄，順序存放在已排序的記錄序列的后面，直到全部排完。選擇排序中主要使用直接選擇排序和堆排 序。 ①.直接選擇排序(不穩(wěn)定) 直接選擇排序的過程是：首先在所有記錄中選出序碼最小的記錄，把它與第1個記錄交換，然后在其余的記錄內(nèi)選出排序碼最小的記錄，與第2個記錄交換......依次類推，直到所有記錄排完為止。 無論文件初始狀態(tài)如何，在第i趟排序中選出最小關(guān)鍵字的記錄，需要做n-i次比較，因此，總的比較次數(shù)為n(n-1)/2=O(n^2)。當初始文件為正序時，移動次數(shù)為0；文件初態(tài)為反序時，每趟排序均要執(zhí)行交換操作，總的移動次數(shù)取最大值3(n-1)。直接選擇排序的平均時間復(fù)雜度為O(n^2)。直接選擇排序是不穩(wěn)定的。 代碼如下: void Dir_Choose(int A[],int n)//直接選擇排序 { int k,t;for(int i=0;i ②.堆排序(不穩(wěn)定) 堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。n個關(guān)鍵字序列 K1,K2,...,Kn稱為堆，當且僅當該序列滿足(Ki<=K2i且Ki<=K2i+1)或(Ki>=K2i且Ki>=K2i+1),(1<=i<=n/2)。根結(jié)點(堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最小者，稱為小根堆；根結(jié)點的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最大者，稱為大根堆。若將此序列所存儲的向量R[1..n]看作是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點的關(guān)鍵字。 堆排序的關(guān)鍵步驟有兩個：一是如何建立初始堆；二是當堆的根結(jié)點與堆的最后一個結(jié)點交換后，如何對少了一個結(jié)點后的結(jié)點序列做調(diào)整，使之重新成為堆。堆排序的最壞時間復(fù)雜度為O(nlog2n),堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較 次數(shù)較多，所以堆排序不適宜于記錄較少的文件。堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。 代碼略..三.交換排序 交換排序的基本思想是：兩兩比較待排序記錄的排序碼，并交換不滿足順序要求的那寫偶對，直到滿足條件為止。交換排序的主要方法有冒泡排序和快速排序.①.冒泡排序(穩(wěn)定的) 冒泡排序?qū)⒈慌判虻挠涗洈?shù)組R[1..n]垂直排列，每個記錄R[i]看作是重量為ki的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R；凡掃描到違反本原則的輕氣泡，就使其向上“漂浮”。如此反復(fù)進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 冒泡排序的具體過程如下： 第一步，先比較k1和k2，若k1>k2，則交換k1和k2所在的記錄，否則不交換。繼續(xù)對k2和k3重復(fù)上述過程，直到處理完kn-1和kn。這時最大的排序碼記錄轉(zhuǎn)到了最后位置，稱第1次起泡，共執(zhí)行n-1次比較。 與第一步類似，從k1和k2開始比較，到kn-2和kn-1為止，共執(zhí)行n-2次比較。 依次類推，共做n-1次起泡，完成整個排序過程。 若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需關(guān)鍵字比較次數(shù)為n-1次，記錄移動次數(shù)為0。因此，冒泡排序最好的時間復(fù)雜度為O(n)。 若初始文件是反序的，需要進行n-1趟排序。每趟排序要進行n-i次關(guān)鍵字的比較(1<=i<=n-1),且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較次數(shù)達到最大值n(n-1)/2=O(n^2),移動次數(shù)也達到最大值3n(n-1)/2=O(n^2)。因此，冒泡排序的最壞時間復(fù)雜度為O(n^2)。 雖然冒泡排序不一定要進行n-1趟，但由于它的記錄移動次數(shù)較多，故平均性能比直接插入排序要差得多。冒泡排序是就地排序，且它是穩(wěn)定的。 代碼如下: void QP(int A[],int n)//優(yōu)化的冒泡排序 { int count=0,t,flag;for(int i=0;i ②.快速排序：(不穩(wěn)定的) 快速排序采用了一種分治的策略，通常稱其為分治法，其基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。 快速排序的具體過程如下： 第一步，在待排序的n個記錄中任取一個記錄，以該記錄的排序碼為準，將所有記錄分成兩組，第1組各記錄的排序碼都小于等于該排序碼，第2組各記錄的排序碼都大于該排序碼，并把該記錄排在這兩組中間。 第二步，采用同樣的方法，對左邊的組和右邊的組進行排序，直到所有記錄都排到相應(yīng)的位置為止。 代碼如下: void Quick_Sort(int A[],int low,int high)//low和high是數(shù)組的下標 { if(low 四.歸并排序 歸并排序是將兩個或兩個以上的有序子表合并成一個新的有序表。初始時，把含有n個結(jié)點的待排序序列看作由n個長度都為1的有序子表組成，將它們依次兩兩歸并得到長度為2的若干有序子表，再對它們兩兩合并。直到得到長度為n的有序表，排序結(jié)束。 歸并排序是一種穩(wěn)定的排序，可用順序存儲結(jié)構(gòu)，也易于在鏈表上實現(xiàn)，對長度為n的文件，需進行l(wèi)og2n趟二路歸并，每趟歸并的時間為O(n),故其時間復(fù)雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。歸并排序需要一個輔助向量來暫存兩個有序子文件歸并的結(jié)果，故其輔助空間復(fù)雜度為O(n),顯然它不是就地排序。 代碼略...五.基數(shù)排序 設(shè)單關(guān)鍵字的每個分量的取值范圍均是C0<=Kj<=Crd-1(0<=j<=rd),可能的取值個數(shù)rd稱為基數(shù)．基數(shù)的選擇和關(guān)鍵字的分解因關(guān)鍵字的類型而異． (1).若關(guān)鍵字是十進制整數(shù)，則按個、十等位進行分解，基數(shù)rd=10,C0=0,C9=9,d為最長整數(shù)的位數(shù)． (2).若關(guān)鍵字是小寫的英文字符串，則rd=26,C0='a',C25='z',d為最長字符串的長度． 基數(shù)排序的基本思想是：從低位到高位依次對待排序的關(guān)鍵碼進行分配和收集，經(jīng)過d趟分配和收集，就可以得到一個有序序列． 按平均時間將排序分為四類： （1）平方階(O(n2))排序 一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序； （2）線性對數(shù)階(O(nlgn))排序 如快速、堆和歸并排序； （3）O(n1+￡)階排序 ￡是介于0和1之間的常數(shù)，即0<￡<1，如希爾排序； （4）線性階(O(n))排序 如基數(shù)排序。 各種排序方法比較 簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。 影響排序效果的因素 因為不同的排序方法適應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素： ①待排序的記錄數(shù)目n； ②記錄的大小(規(guī)模)； ③關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)； ④對穩(wěn)定性的要求； ⑤語言工具的條件； ⑥存儲結(jié)構(gòu)； ⑦時間和輔助空間復(fù)雜度等。 不同條件下，排序方法的選擇 (1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。 當記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序為宜。 (2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機的快速排序為宜；(3)若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或 歸并排序。 快速排序是目前基于比較的內(nèi)部排序中被認為是最好的方法，當待排序的關(guān)鍵字是隨機分布時，快速排序的平均時間最短； 堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。 若要求排序穩(wěn)定，則可選用歸并排序。但從單個記錄起進行兩兩歸并的 排序算法并不值得提倡，通?？梢詫⑺椭苯硬迦肱判蚪Y(jié)合在一起使用。先利用直接插入排序求得較長的有序子文件，然后再兩兩歸并之。因為直接插入排序是穩(wěn)定的，所以改進后的歸并排序仍是穩(wěn)定的。 事先聲明，此文檔來自某技術(shù)論壇，內(nèi)容歸原作者所有。 1.基本思想： 每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。2.排序過程： 【示例】： 初始關(guān)鍵字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序結(jié)果 13 27 38 49 49 76 76 97 3.void selectionSort(Type* arr,long len){ long i=0,j=0;/*iterator value*/ long maxPos;assertF(arr!=NULL,“In InsertSort sort,arr is NULLn”);for(i=len-1;i>=1;i--){ maxPos=i;for(j=0;j 插入排序（Insertion Sort）的基本思想是：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當位置，直到全部記錄插入完成為止。直接插入排序 直接插入排序（Straight Insertion Sort）：將一個記錄插入到排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。直接插入排序算法 哨兵（監(jiān)視哨）有兩個作用：一是作為臨變量存放R[i]（當前要進行比較的關(guān)鍵字）的副本；二是在查找循環(huán)中用來監(jiān)視下標變量j是否越界。 當文件的初始狀態(tài)不同時，直接插入排序所耗費的時間是有很大差異的。最好情況是文件初態(tài)為正序，此時算法的時間復(fù)雜度為O(n)，最壞情況是文件初態(tài)為反序，相應(yīng)的時間復(fù)雜度為O(n2)，算法的平均時間復(fù)雜度是O(n2)。算法的輔助空間復(fù)雜度是O(1)，是一個就地排序。 直接插入排序是穩(wěn)定的排序方法。三.冒泡排序 [算法思想]：將被排序的記錄數(shù)組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上“飄浮”。如此反 復(fù)進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 [算法]： void BubbleSort(SeqList R){ //R（l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序 int i，j； Boolean exchange； //交換標志 for(i=1;i exchange=FALSE； //本趟排序開始前，交換標志應(yīng)為假 for(j=n-1;j>=i；j--)//對當前無序區(qū)R[i..n]自下向上掃描 if(R[j+1].key R[0]=R[j+1]； //R[0]不是哨兵，僅做暫存單元 R[j+1]=R[j]； R[j]=R[0]； exchange=TRUE； //發(fā)生了交換，故將交換標志置為真 } if(!exchange)return；//本趟排序未發(fā)生交換，提前終止算法 } //endfor(外循環(huán))} //BubbleSort [分析]：起泡排序的結(jié)束條件為：最后一趟沒有進行“交換”。從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經(jīng)過一趟起泡，無序序列的長度只縮小1。[算法思想]：將被排序的記錄數(shù)組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上“飄浮”。如此反復(fù)進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 [算法]： void BubbleSort(SeqList R){ //R（l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序 int i，j； Boolean exchange； //交換標志 for(i=1;i exchange=FALSE； //本趟排序開始前，交換標志應(yīng)為假 for(j=n-1;j>=i；j--)//對當前無序區(qū)R[i..n]自下向上掃描 if(R[j+1].key R[0]=R[j+1]； //R[0]不是哨兵，僅做暫存單元 R[j+1]=R[j]； R[j]=R[0]； exchange=TRUE； //發(fā)生了交換，故將交換標志置為真 } if(!exchange)return；//本趟排序未發(fā)生交換，提前終止算法 } //endfor(外循環(huán))} //BubbleSort [分析]：起泡排序的結(jié)束條件為：最后一趟沒有進行“交換”。從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經(jīng)過一趟起泡，無序序列的長度只縮小1。四.希爾排序 基本思想： 先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d l的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插人排序；然后，取第二個增量d2 該方法實質(zhì)上是一種分組插入方法。給定實例的shell排序的排序過程 假設(shè)待排序文件有10個記錄，其關(guān)鍵字分別是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次為： 5，3，1 Shell排序的算法實現(xiàn) 1． 不設(shè)監(jiān)視哨的算法描述 void ShellPass(SeqList R，int d){//希爾排序中的一趟排序，d為當前增量 for(i=d+1;i<=n；i++)//將R[d+1．．n]分別插入各組當前的有序區(qū) if(R[i].key R[j+d]；=R[j]； //后移記錄 j=j-d； //查找前一記錄 }while(j>0&&R[0].key R[j+d]=R[0]； //插入R[i]到正確的位置上 } //endif } //ShellPass void ShellSort(SeqList R){ int increment=n； //增量初值，不妨設(shè)n>0 do { increment=increment/3+1； //求下一增量 ShellPass(R，increment)； //一趟增量為increment的Shell插入排序 }while(increment>1)} //ShellSort 注意： 當增量d=1時，ShellPass和InsertSort基本一致，只是由于沒有哨兵而在內(nèi)循環(huán)中增加了一個循環(huán)判定條件“j>0”，以防下標越界。2．設(shè)監(jiān)視哨的shell排序算法 算法分析 1．增量序列的選擇 Shell排序的執(zhí)行時間依賴于增量序列。 好的增量序列的共同特征： ① 最后一個增量必須為1； ② 應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。 有人通過大量的實驗，給出了目前較好的結(jié)果：當n較大時，比較和移動的次數(shù)約在nl.25到1.6n1.25之間。 2．Shell排序的時間性能優(yōu)于直接插入排序 希爾排序的時間性能優(yōu)于直接插入排序的原因： ①當文件初態(tài)基本有序時直接插入排序所需的比較和移動次數(shù)均較少。 ②當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復(fù)雜度O(n)和最壞時間復(fù)雜度0(n2)差別不大。 ③在希爾排序開始時增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量di逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過序，使文件較接近于有序狀態(tài)，所以新的一趟排序過程也較快。 因此，希爾排序在效率上較直接插人排序有較大的改進。3．穩(wěn)定性 希爾 排序是不穩(wěn)定的。參見上述實例，該例中兩個相同關(guān)鍵字49在排序前后的相對次序發(fā)生了變化。五.堆排序 1、堆排序定義 n個關(guān)鍵字序列Kl，K2，?，Kn稱為堆，當且僅當該序列滿足如下性質(zhì)(簡稱為堆性質(zhì))： (1)ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤) 若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點的關(guān)鍵字。 【例】關(guān)鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(zhì)(1)和(2)，故它們均是堆，其對應(yīng)的完全二叉樹分別如小根堆示例和大根堆示例所示。 2、大根堆和小根堆 根結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最小者的堆稱為小根堆。 根結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最大者，稱為大根堆。注意： ①堆中任一子樹亦是堆。 ②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。 3、堆排序特點 堆排序(HeapSort)是一樹形選擇排序。 堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系【參見二叉樹的順序存儲結(jié)構(gòu)】，在當前無序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄。 4、堆排序與直接插入排序的區(qū)別 直接選擇排序中，為了從R[1..n]中選出關(guān)鍵字最小的記錄，必須進行n-1次比較，然后在R[2..n]中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時未保留這些比較結(jié)果，所以后一趟排序時又重復(fù)執(zhí)行了這些比較操作。 堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。 5、堆排序 堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當前無序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡單。（1）用大根堆排序的基本思想 ① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū) ② 再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key ③ 由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有 序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。 ?? 直到無序區(qū)只有一個元素為止。（2）大根堆排序算法的基本操作： ① 初始化操作：將R[1..n]構(gòu)造為初始堆； ② 每一趟排序的基本操作：將當前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調(diào)整為堆(亦稱重建堆)。注意： ①只需做n-1趟排序，選出較大的n-1個關(guān)鍵字即可以使得文件遞增有序。 ②用小根堆排序與利用大根堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴大至整個向量為止。（3）堆排序的算法： void HeapSort(SeqIAst R){ //對R[1..n]進行堆排序，不妨用R[0]做暫存單元 int i； BuildHeap(R)； //將R[1-n]建成初始堆 for(i=n;i>1；i--){ //對當前無序區(qū)R[1..i]進行堆排序，共做n-1趟。R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //將堆頂和堆中最后一個記錄交換 Heapify(R，1，i-1)； //將R[1..i-1]重新調(diào)整為堆，僅有R[1]可能違反堆性質(zhì) } //endfor } //HeapSort（4）BuildHeap和Heapify函數(shù)的實現(xiàn) 因為構(gòu)造初始堆必須使用到調(diào)整堆的操作，先討論Heapify的實現(xiàn)。① Heapify函數(shù)思想方法 每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R[i]交換后，新的無序區(qū)R[1..i-1]中只有R[1]的值發(fā)生了變化，故除R[1]可能違反堆性質(zhì)外，其余任何結(jié)點為根的子樹均是堆。因此，當被調(diào)整區(qū)間是R[low..high]時，只須調(diào)整以R[low]為根的樹即可?！昂Y選法”調(diào)整堆 R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關(guān)鍵字最大的結(jié)點。若R[low].key不小于這兩個孩子結(jié)點的關(guān)鍵字，則R[low]未違反堆性質(zhì)，以R[low]為根的樹已是堆，無須調(diào)整；否則必須將R[low]和它的兩個孩子結(jié)點中關(guān)鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換后又可能使結(jié)點R[large]違反堆性質(zhì)，同樣由于該結(jié)點的兩棵子樹(若存在)仍然是堆，故可重復(fù)上述的調(diào)整過程，對以R[large]為根的樹進行調(diào)整。此過程直至當前被調(diào)整的結(jié)點已滿足堆性質(zhì)，或者該結(jié)點已是葉子為止。上述過程就象過篩子一樣，把較小的關(guān)鍵字逐層篩下去，而將較大的關(guān)鍵字逐層選上來。因此，有人將此方法稱為“篩選法”。 ②BuildHeap的實現(xiàn) 要將初始文件R[l..n]調(diào)整為一個大根堆，就必須將它所對應(yīng)的完全二叉樹中以每一結(jié)點為根的子樹都調(diào)整為堆。 顯然只有一個結(jié)點的 樹是堆，而在完全二叉樹中，所有序號 的結(jié)點都是葉子，因此以這些結(jié)點為根的子樹均已是堆。這樣，我們只需依次將以序號為，-1，?，1的結(jié)點作為根的子樹都調(diào)整為堆即可。 具體算法【參見教材】。 5、大根堆排序?qū)嵗?/p> 對于關(guān)鍵字序列(42，13，24，91，23，16，05，88)，在建堆過程中完全二叉樹及其存儲結(jié)構(gòu)的變化情況參見。 6、算法分析 堆排序的時間，主要由建立初始堆和反復(fù)重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用Heapify實現(xiàn)的。 堆排序的最壞時間復(fù)雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。 由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。 堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。六.快速排序 快速排序的基本思路是：首先我們選擇一個中間值middle（程序中我們可使用數(shù)組中間值），把比中間值小的放在其左邊，比中間值大的放在其右邊。由于這個排序算法較復(fù)雜，我們先給出其進行一次排序的程序框架（從各類數(shù)據(jù)結(jié)構(gòu)教材中可得）： void QuickSort(int *pData, int left, int right){ int i, j;int middle, iTemp;i = left;j = right;middle = pData[(left + right)/ 2];//求中間值 do { while((pData[i] < middle)&&(i < right))//從左掃描大于中值的數(shù) i++; while((pData[j] > middle)&&(j > left))//從右掃描小于中值的數(shù) j--; if(i <= j)//找到了一對值 { //交換 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } } while(i <= j);//如果兩邊掃描的下標交錯，就停止（完成一次） //當左邊部分有值(left if(left QuickSort(pData,left,j); //當右邊部分有值(right>i)，遞歸右半邊 if(right>i) QuickSort(pData,i,right);} 對于n個成員，快速排序法的比較次數(shù)大約為n*logn 次，交換次數(shù)大約為(n*logn)/6次。如果n為100，冒泡法需要進行4950 次比較，而快速排序法僅需要200 次，快速排序法的效率的確很高?？焖倥判蚍ǖ男阅芘c中間值的選定關(guān)系密切，如果每一次選擇的中間值都是最大值（或最小值），該算法的速度就會大大下降?？焖倥判蛩惴ㄗ顗那闆r下的時間復(fù)雜度為O(n2)，而平均時間復(fù)雜度為O(n*logn)。七.合并排序 說明 之前所介紹的排序法都是在同一個陣列中的排序，考慮今日有兩筆或兩筆以上的資料，它可能是不同陣列中的資料，或是不同檔案中的資料，如何為它們進行排序？ 解法 可以使用合併排序法，合併排序法基本是將兩筆已排序的資料合併並進行排序，如果所讀入的資料尚未排序，可以先利用其它的排序方式來處理這兩筆資料，然後再將排序好的這兩筆資料合併。 有人問道，如果兩筆資料本身就無排序順序，何不將所有的資料讀入，再一次進行排序？排序的精神是儘量利用資料已排序的部份，來加快排序的效率，小筆資料的排序較為快速，如果小筆資料排序完成之後，再合併處理時，因為兩筆資料都有排序了，所有在合併排序時會比單純讀入所有的資料再一次排序來的有效率。那麼可不可以直接使用合併排序法本身來處理整個排序的動作？而不動用到其它的排序方式？答案是肯定的，只要將所有的數(shù)字不斷的分為兩個等分，直到最後剩一個數(shù)字為止，然後再反過來不斷的合併，就如下圖所示： 不過基本上分割又會花去額外的時間，不如使用其它較好的排序法來排序小筆資料，再使用合併排序來的有效率。 下面這個程式範例，我們使用快速排序法來處理小筆資料排序，然後再使用合併排序法處理合併的動作。例子 C #include quicksort(number1, 0, MAX1-1);quicksort(number2, 0, MAX2-1);printf(“n排序後：”);printf(“nnumber1[]：”);for(i = 0;i < MAX1;i++)printf(“%d ”, number1[i]);printf(“nnumber2[]：”);for(i = 0;i < MAX2;i++)printf(“%d ”, number2[i]);// 合併排序 mergesort(number1, MAX1, number2, MAX2, number3);printf(“n合併後：”);for(i = 0;i < MAX1+MAX2;i++)printf(“%d ”, number3[i]);printf(“n”);return 0;} int partition(int number[], int left, int right){ int i, j, s;s = number[right];i = left-1;for(j = left;j < right;j++){ if(number[j] <= s){ i++;SWAP(number[i], number[j]);} } SWAP(number[i+1], number[right]);return i+1;} void quicksort(int number[], int left, int right){ int q;if(left < right){ q = partition(number, left, right);quicksort(number, left, q-1);quicksort(number, q+1, right);} } void mergesort(int number1[], int M, int number2[], int N, int number3[]){ int i = 0, j = 0, k = 0;while(i < M && j < N){ if(number1[i] <= number2[j])number3[k++] = number1[i++];else number3[k++] = number2[j++];} while(i < M)number3[k++] = number1[i++];while(j < N)number3[k++] = number2[j++];} Java public class MergeSort { public static int[] sort(int[] number1, int[] number2){ int[] number3 = new int[number1.length + number2.length];int i = 0, j = 0, k = 0;while(i < number1.length && j < number2.length){ if(number1[i] <= number2[j])number3[k++] = number1[i++];else number3[k++] = number2[j++];} while(i < number1.length)number3[k++] = number1[i++];while(j < number2.length)number3[k++] = number2[j++];return number3;} } 八?；鶖?shù)排序 基數(shù)排序是根據(jù)組成關(guān)鍵字的各位值，用“分配”和“收集”的方法進行排序。例如，把撲克牌的排序看成由花色和面值兩個數(shù)據(jù)項組成的主關(guān)鍵字排序。 花色：梅花<方塊<紅心<黑桃 面值：2<3<4<...<10 若要將一副撲克牌排成下列次序： 梅花2,...,梅花A,方塊2,...,方塊A,紅心2,...,紅心A,黑桃2,...,黑桃A。 有兩種排序方法： 一、先按花色分成四堆，把各堆收集起來；然后對每堆按面值由小到大排列，再按花色從小到大按堆收疊起來。----稱為“最高位優(yōu)先”(MSD)法。 二、先按面值由小到大排列成13堆,然后從小到大收集起來；再按花色不同分成四堆,最后順序收集起來。----稱為“最低位優(yōu)先”(LSD)法。 [例] 設(shè)記錄鍵值序列為{88,71,60,31,87,35,56,18}，用基數(shù)排序(LSD)。如圖所示：其中f[i]、e[i]為按位分配面值為i的隊列的隊頭和隊尾指針。 #define D 3 typedef struct { int key;float data;int link;} JD key data link int jspx(JD r[],int n){ /*鏈式存儲表示的基數(shù)排序*/ int i,j,k,t,p,rd,rg,f[10],e[10];/*p為r[]的下標,rd,rg為比例因子,f[j],e[j]是代碼為j的隊的首尾指針*/ for(i=1;i 將每個記錄項與其他諸項比較計算出小于該項的記錄個數(shù)，以確定該項的位置。 一、冒泡排序 已知一組無序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與 a[2]的值，若a[1]大于a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大于a[3]則交換兩者的值，否則不變。再比 較a[3]與a[4]，以此類推，最后比較a[n-1]與a[n]的值。這樣處理一輪后，a[n]的值一定是這組數(shù)據(jù)中最大的。再對a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理 n-1輪后a[1]、a[2]、……a[n]就以升序排列了。 優(yōu)點：穩(wěn)定； 缺點：慢，每次只能移動相鄰兩個數(shù)據(jù)。 二、選擇排序 每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法。 n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果： ①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。 ②第1趟排序 在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。 …… ③第i趟排序 第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(1≤i≤n-1)。該趟 排序從當前無序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。 這樣，n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。 優(yōu)點：移動數(shù)據(jù)的次數(shù)已知（n-1次）； 缺點：比較次數(shù)多。 三、插入排序 已知一組升序排列數(shù)據(jù)a[1]、a[2]、……a[n]，一組無序數(shù)據(jù)b[1]、b[2]、……b[m]，需將二者合并成一個升序數(shù)列。首先比較b[1]與a[1]的值，若b[1]大于a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大于a[2]，則繼續(xù)跳過，直到b[1]小于a數(shù)組中某一數(shù)據(jù)a[x]，則將a[x]~a[n]分別向后移動一位，將b[1]插入到原來 a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若無數(shù)組a，可將b[1]當作n=1的數(shù)組a） 優(yōu)點：穩(wěn)定，快； 缺點：比較次數(shù)不一定，比較次數(shù)越少，插入點后的數(shù)據(jù)移動越多，特別是當數(shù)據(jù)總量龐大的時候，但用鏈表可以解決這個問題。 四、縮小增量排序 由希爾在1959年提出，又稱希爾排序(shell排序)。 已知一組無序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。發(fā)現(xiàn)當n不大時，插入 排序的效果很好。首先取一增量d(d 優(yōu)點：快，數(shù)據(jù)移動少； 缺點：不穩(wěn)定，d的取值是多少，應(yīng)取多少個不同的值，都無法確切知道，只能憑經(jīng)驗來取。 五、快速排序 快速排序是冒泡排序的改進版，是目前已知的最快的排序方法。 已知一組無序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數(shù)據(jù)a[x] 作為基準。比較a[x]與其它數(shù)據(jù)并排序，使a[x]排在數(shù)據(jù)的第k位，并且使a[1]~a[k-1]中的每一個數(shù) 據(jù) 優(yōu)點：極快，數(shù)據(jù)移動少； 缺點：不穩(wěn)定。 六、箱排序 已知一組無序正整數(shù)數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。首先定義一個數(shù)組x[m],且m>=a[1]、a[2]、……a[n]，接著循環(huán)n次，每次x[a]++.優(yōu)點：快，效率達到O(1)缺點：數(shù)據(jù)范圍必須為正整數(shù)并且比較小 六、歸并排序 歸并排序是多次將兩個或兩個以上的有序表合并成一個新的有序表。最簡單的歸并是直接將兩個有序的子表合并成一個有序的表。 歸并排序是穩(wěn)定的排序.即相等的元素的順序不會改變.如輸入記錄 1(1)3(2)2(3)2(4)5(5)(括號中是記錄的關(guān)鍵字)時輸出的 1(1)2(3)2(4)3(2)5(5)中的2 和 2 是按輸入的順序.這對要排序數(shù)據(jù)包含多個信息而要按其中的某一個信息排序,要求其它信息盡量按輸入的順序排列時很重要.這也是它比快速排序優(yōu)勢的地方.歸并排序：歸并排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間。在使用它對兩個己有序的序列歸并，將有無比的優(yōu)勢。其時間復(fù)雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。對數(shù)據(jù)的有序性不敏感。若數(shù)據(jù)節(jié)點數(shù)據(jù)量大，那將不適合。但可改造成索引操作，效果將非常出色。 堆排序：由于它在直接選擇排序的基礎(chǔ)上利用了比較結(jié)果形成。效率提高很大。它完成排序的總比較次數(shù)為O(nlog2n)。它是對數(shù)據(jù)的有序性不敏感的一種算法。但堆排序?qū)⑿枰鰞蓚€步驟：－是建堆，二是排序（調(diào)整堆）。所以一般在小規(guī)模的序列中不合適，但對于較大的序列，將表現(xiàn)出優(yōu)越的性能。第三篇：排序算法總結(jié)
第四篇：51CTO下載-排序和算法總結(jié)
第五篇：各種排序算法的優(yōu)缺點
點擊咨詢 