數(shù)據(jù)結(jié)構(gòu)中排序和查找各種時(shí)間復(fù)雜度

(1)冒泡排序

        冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。

(2)選擇排序

      選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的，比如給第一個(gè)位置選擇最小的。…… 例子說明好多了。序列5 8 5 2 9， 我們知道第一遍選擇第1個(gè)元素5會和2交換，那么原序列中2個(gè)5的相對前后順序就被破壞了， 所以選擇排序不穩(wěn)定的排序算法

(3)插入排序
     插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個(gè)元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經(jīng)有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果和插入元素相等，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變。所以插入排序是穩(wěn)定的。

(4)快速排序

    快速排序有兩個(gè)方向，左邊的i下標(biāo)一直往右走（往后），當(dāng)a[i] <= a[center_index]，其中center_index是中樞元素的數(shù)組下標(biāo)，一般取為數(shù)組第0個(gè)元素。而右邊的j下標(biāo)一直往左走（往前），當(dāng)a[j] > a[center_index]。如果i和j都走不動(dòng)了，i <= j, 交換a[i]和a[j],重復(fù)上面的過程，直到i>j。 交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時(shí)候，很有可能把前面的元素的穩(wěn)定性打亂，比如序列為 5 3 3 4 3 8 9 10 11， 現(xiàn)在中樞元素5和3(第5個(gè)元素，下標(biāo)從1開始計(jì))交換就會把元素3的穩(wěn)定性打亂，所以快速排序是一個(gè)不穩(wěn)定的排序算法。（不穩(wěn)定發(fā)生在中樞元素和a[j]交換的時(shí)刻）

(5)歸并排序
    歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個(gè)元素(認(rèn)為直接有序)或者2個(gè)序列(1次比較和交換),然后把各個(gè)有序的段序列合并成一個(gè)有序的長序列。不斷合并直到原序列全部排好序。相等時(shí)不發(fā)生交換。所以，歸并排序也是穩(wěn)定的排序算法。

(6)基數(shù)排序
   基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序，最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前。基數(shù)排序基于分別排序，分別收集，所以其是穩(wěn)定的排序算法。

(7)希爾排序(shell)
    希爾排序是按照不同步長對元素進(jìn)行插入排序，當(dāng)剛開始元素很無序的時(shí)候，步長最大，所以插入排序的元素個(gè)數(shù)很少，速度很快；當(dāng)元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序的時(shí)間復(fù)雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會被打亂，所以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的序列，堆排序的過程是從第n/2開始和其子節(jié)點(diǎn)共3個(gè)值選擇最大(大頂堆)或者最小(小頂堆),這3個(gè)元素之間的選擇當(dāng)然不會破壞穩(wěn)定性。但當(dāng)為n/2-1, n/2-2, ...1這些個(gè)父節(jié)點(diǎn)選擇元素時(shí)，就會破壞穩(wěn)定性。有可能第n/2個(gè)父節(jié)點(diǎn)交換把后面一個(gè)元素交換過去了，而第n/2-1個(gè)父節(jié)點(diǎn)把后面一個(gè)相同的元素沒有交換，那么這2個(gè)相同的元素之間的穩(wěn)定性就被破壞了。所以，堆排序是不穩(wě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)           大部分已排序時(shí)較好

Shell   O(nlogn)        O(ns) 1

快速    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í)較好

基數(shù)    O(logRB)     O(logRB)       穩(wěn)定         O(n)           B是真數(shù)(0-9)，R是基數(shù)(個(gè)十百)

二、查找

未寫……

三 樹圖

克魯斯卡爾算法的時(shí)間復(fù)雜度為O（eloge）

普里姆算法的時(shí)間復(fù)雜度為O（n2）

迪杰斯特拉算法的時(shí)間復(fù)雜度為O（n2）

拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為O（n+e）

關(guān)鍵路徑算法的時(shí)間復(fù)雜度為O（n+e）