數據結構中排序和查找各種時間復雜度

(1)冒泡排序

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

(2)選擇排序

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

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

(4)快速排序

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

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

(6)基數排序
   基數排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序，最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前?；鶖蹬判蚧诜謩e排序，分別收集，所以其是穩定的排序算法。

(7)希爾排序(shell)
    希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以shell排序是不穩定的。

(8)堆排序
   我們知道堆的結構是節點i的孩子為2*i和2*i+1節點，大頂堆要求父節點大于等于其2個子節點，小頂堆要求父節點小于等于其2個子節點。在一個長為n的序列，堆排序的過程是從第n/2開始和其子節點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩定性。但當為n/2-1, n/2-2, ...1這些個父節點選擇元素時，就會破壞穩定性。有可能第n/2個父節點交換把后面一個元素交換過去了，而第n/2-1個父節點把后面一個相同的元素沒有交換，那么這2個相同的元素之間的穩定性就被破壞了。所以，堆排序是不穩定的排序算法

一、排序

排序法 平均時間   最差情形      穩定度     額外空間     備注

冒泡    O(n2)            O(n2)             穩定         O(1)          n小時較好

交換    O(n2)            O(n2)             不穩定     O(1)            n小時較好

選擇    O(n2)            O(n2)             不穩定     O(1)           n小時較好

插入    O(n2)             O(n2)              穩定       O(1)           大部分已排序時較好

Shell   O(nlogn)        O(ns) 1

快速    O(nlogn)        O(n2)             不穩定      O(nlogn)      n大時較好

歸并    O(nlogn)      O(nlogn)       穩定         O(1)           n大時較好

堆      O(nlogn)     O(nlogn)       不穩定   O(1)           n大時較好

基數    O(logRB)     O(logRB)       穩定         O(n)           B是真數(0-9)，R是基數(個十百)

二、查找

未寫……

三 樹圖

克魯斯卡爾算法的時間復雜度為O（eloge）

普里姆算法的時間復雜度為O（n2）

迪杰斯特拉算法的時間復雜度為O（n2）

拓撲排序算法的時間復雜度為O（n+e）

關鍵路徑算法的時間復雜度為O（n+e）