常見排序算法總結
冒泡排序：
基本思路：每次冒泡總會將當前數組最大數據通過相鄰數據比較交換，排到數組尾，因此一次冒泡至少排好一個數 據的順序，經過n次冒泡就會將當前數組排好順序。
空間複雜度：O(1),因為只涉及相鄰數據互換，所以只需要常量級的臨時空間，是原地排序算法。
穩定性：在冒泡排序中只有交換才改變數據順序，而為了保證數據穩定性，當兩個數據相等時不進行數據互換。
時間複雜度：最好情況下，數據已經是有序的了，只需要進行一次冒泡，因此時間複雜度為O(n),最壞情況下數據 完全是倒敘的，因此需要N次冒泡，時間複雜度為O(n2)。平均時間複雜度為O(n2)
插入排序：
基本思路：將數據中的數組分為兩個區間分別為已排序區間和未排序區間，每次將未排序區間中的一個元素挑出插 入已排序區間中的合適位置，直到未排序區間中的元素為空，排序結束。
空間複雜度：因為不需要額外的空間，所以空間複雜度為O(1),是原地排序算法。
穩定性：當未排序區間元素插入已排序區間時，碰到相同的元素，後排的元素插入已經排好元素的後方，就不會打 亂相同元素的原相對順序，因此屬於穩定排序。
時間複雜度：最好情況下，數組為有序的，因此不需要進行插入操作，只需從頭到尾進行一次遍歷比較即可，因此 時間複雜度為O(n),最壞情況下，數組為倒序，每次插入相當於在數組第一個位置插入新的數據，因 此時間複雜度為O(n2)。平均時間複雜度為O(n2)。
選擇排序：
基本思路：選擇排序與插入排序類似，也是分為已排序區間和未排序區間，不同的是選擇排序選擇未排序區間最小 值放在已排序區間末尾之後的一個元素也就是未排序區間開頭，而未排序區間開頭的元素放在原未排 序區間最小值的位置，簡而言之選擇未排序區間最小值與未排序區間首值進行互換。直到未排序區間 元素個數為零。
空間複雜度：因為不需要額外的空間，所以空間複雜度為O(1),是原地排序算法。
穩定性：不穩定，因為其中涉及到元素互換，所以會導致大小相同元素的相對位置被打亂。（為什麼互換而不能插 入，因為空間複雜度為一，若像插入排序那樣將最小值插入已排序區間末尾，會導致未排序首位值被覆 蓋，造成數據丟失）
時間複雜度：最好，最壞，平均都為O(n2)。
歸併排序：
基本思路：將整個數組分開成小部分，分別排序後再合併到一起。關鍵在於合併步驟，假設要合併的數組分別為A 和B，那麼我們利用一個臨時數組C，兩個指針a,b初始位置分別位於A,B數組首位，然後將a,b所指內容 進行比較，將較小數據放入C中，然後將該指針後移一位，繼續比較a,b直到某一數組為零，然後將另 一數組剩餘數據拷貝進C中。C中的數據即為合併完成的數據，然後拷貝回原數組中。其實排序是在合 並步驟中完成的。
空間複雜度：不是原地排序算法，因為合併過程中需要臨時數組C，所以需要額外空間，空間複雜度為O(n).
穩定性：穩定，是否穩定主要看合併過程，當我們對A,B 數組進行比較時，如果碰到相同數據，只需要將A數組數 據放入C中就會使相同數據原相對位置不變，也就達到了穩定排序。
時間複雜度：遞歸代碼時間複雜度，假設求解A的時間為T(a),A分解為子問題B,C 求解時間分別為T(b)，T(c)，那麼 T(a)=T(b)+T(c)+K,K為b與c合併的時間。假設A的長度為n，那麼將A分為兩等份的話時間為 2*T(n/2)，且合併兩個有序數組的時間複雜度為O(n),所以分析長度為n的數組時間複雜度為：
T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
……
= 2^k * T(n/2^k) + k * n
所以當n/2^k=1時，k=log2n,所以時間複雜度為O(nlogn).
快速排序：
基本思路：在數組A中選擇一個隨機數據a，令quick_sort()函數可以將數組A中大於a的數放在a的前方，小於a的數放在a的後方，那麼遞推公式為quick_sort(p…..r)=quick_sort(p…..q-1)+quick_sort(q-1…..r).截止條件為p>=r。
1，關於放置方法，若不考慮空間複雜度，則可以類似於選擇排序，設置兩個臨時數組B C ，將A數組的數據與a進行比較，將較大的數放在B，較小的數放在C，再將數組B與C的數據複製回A，將a放在中間。但是這種方法並不是原地排序方法。並不常用。
2，若要原地排序，則類似於插入排序，將數組A分為已排序區間與未排序區間，將未排序區間的數與a進行比較，若小於a，則將該數放在已排序區間末尾，這裡可以選擇將需要放置的數與被放置位置的數進行交換，從而避免插入過程中的數據搬移使得時間損耗上升，而由於交換操作會導致相同數據原位置被打亂，所以這種方法是不穩定的。
所以快排一般為原地，但並不穩定的排序方法。
空間複雜度：O(1)。
時間複雜度：由於這裡也是用的遞歸思想，那麼對於歸併排序的思想這裡同樣適用，時間複雜度為O(nlogn)。但是在極端情況下會退化為O(n2).
優化：之所以會造成極端情況，是因為分區點選擇不合理，合理的分區點選擇是要數組數據在分區點兩邊數據數量差不多。分區點選擇方法，一個是三數取中法，即在數據區間首，中，尾各取一數，選擇中間數作為分區點，而如果數組數據較大，則可以「五數取中」「十數取中」。還有一個是隨機法。
桶排序：
不基於比較，但是對數據又較為嚴格的要求：
1.要求數據可以很容易的分成m個桶，並且桶與桶之間有天然的大小關係，從而可以不用對桶進行排序，
2.要求數據在桶中分佈式比較均勻的
3.桶排序比較適合外部排序，也就是數據存儲在外部磁盤中，數據量很大無法全部加載到內存中進行排序。
基本思路：將全部數據均勻的分到桶中，然後對每個桶進行快排，之後按照桶的大小將其中數據依次取出。
時間複雜度：假設有n個數據，分在m個桶中，那麼每個桶中的數據就為k=n/m個，對m個桶種
數據進行快排，時間複雜度為O(m*k log(n/m))也就是O(n log(n/m)),當m接近n時，時間複雜度也就較接近O(n)。
堆排序：
不穩定，原地，時間複雜度：O(nlogn)
基本思路：
1.建堆，就是將數組原地組建成堆的數據結構，這其中利用到了堆化操作，堆化就是將堆中子節點與其葉子節點盡行比較，將其中最大的（或最小）的數據放到子結點處，完成後比較下一個子節點，直到所有子節點全部完成該操作。
代碼如下：
void heapify(int a[], int n,int i)//堆化 { while (true) { int maxpos = i; if (i*2<=n && a[i] < a[2 * i]) maxpos = 2 * i; if (i*2 +1<= n && a[maxpos] < a[2 * i + 1]) maxpos = 2 * i + 1; if (maxpos == i) break; swap(a, i, maxpos); i=maxpos;//為了將使下降的原主節點進行下一輪堆化，直到最底層的葉節點 } } void buildheap(int a[], int n)//建立堆 { for (int i = n / 2; i >= 1; --i) { heapify(a,n,i); } }
2.排序，這個過程有點類似於刪除堆頂操作，將堆頂元素與堆底元素進行交換，這樣該數組最大的數放在了位於n的位置，然後將剩下的n-1數據進行堆化，重複這個操作直到堆中剩下下標為1的一個元素，排序完成。
代碼如下：
void heapsort(int a[], int n) { for (int i = n; i > 1; --i) { swap(a, 1, i); buildheap(a, i-1); } return; }
時間複雜度：每個節點堆化的過程都會與葉子節點進行比較與交換，所以每個節點的時間複雜度與該節點所在的高度成正比，堆化時間複雜度為O(n),排序時間複雜度為O(n/logn),所以整個堆排序的時間複雜度為O(n/logn)。
穩定度：不穩定，因為在排序過程中回進行數據交換。
為什麼快排性能比堆排序好，主要有兩個方面原因：
1.快速排序的數據訪問順序時順序訪問，但是堆排序的數據訪問是跳着訪問的，這樣對CPU緩存不友好。
2.對於數據相同的數組，堆排序的數據交換次數多於快排。
