平均復雜度最小的排序演算法

1. 各種排序演算法的總結和比較

排序演算法是《數據結構與演算法》中最基本的演算法之一。

排序演算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸並排序、快速排序、堆排序、基數排序等。用一張圖概括：

點擊以下圖片查看大圖：

平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。

線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸並排序；

O(n1+§)) 排序，§ 是介於 0 和 1 之間的常數。 希爾排序

線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。

關於穩定性

穩定的排序演算法：冒泡排序、插入排序、歸並排序和基數排序。

不是穩定的排序演算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

包含以下內容：

排序演算法包含的相關內容具體如下：

冒泡排序演算法

冒泡排序（Bubble Sort）也是一種簡單直觀的排序演算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端。

選擇排序演算法

選擇排序是一種簡單直觀的排序演算法，無論什麼數據進去都是 O(n?) 的時間復雜度。所以用到它的時候，數據規模越小越好。唯一的好處可能就是不佔用額外的內存空間。

插入排序演算法

插入排序的代碼實現雖然沒有冒泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序演算法，它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

希爾排序演算法

希爾排序，也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序演算法。

歸並排序演算法

歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

快速排序演算法

快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。

堆排序演算法

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。

計數排序演算法

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

桶排序演算法

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在於這個映射函數的確定。

基數排序演算法

基數排序是一種非比較型整數排序演算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。

2. 數組排序的最少時間復雜度O(nlog2n)怎麼計算的

for(int j=1; j<=n; j*=2)

這個循環最終執行的次數假設為x，則x次的時候j=2^x 。

當j>n時停止執行，於是2^x>n ，則可以認為該循環一共執行了log2(n)次。

所以該循環的時間復雜度為o(log2(n))，簡記為o(log n) ，忽略掉2的底數。

3. 以下排序演算法最壞情況下時間復雜度最低的是 A.冒泡排序 B.插入 C.選擇 D.快排

在冒泡排序，插入排序，選擇排序，快速排序中，在最最壞情況下，快速排序的時間復雜為O(n2) ，插入排序O(n2)，選擇排序O(n2)，冒泡排序O(n2)。所以ABCD時間復雜度是一樣的。

知識拓展：

在快速排序演算法中，最為關鍵的就是選取一個基值，將數組分為大於基值以及小於基值兩部分，並返回基值所以在位置以利用於遞歸劃分。

對數組a，設需要劃分的其中一段為a[p]~a[r]，我們期待的結果是得到一個q，其中p<=q<=r，使得a[p]~a[q-1]<=a[q]<=a[q+1]~a[r]，這個時候原先的一段數組被分成了三部分。

首先，設基值為這段數組的最後一個元素a[r]，我們希望最後得到的結果是a[r]現在對應的值在演算法結束後可以排在比他大和小的兩部分的中間愛。

然後令i=p-1; j=p，當發現有a[j]>x時，j繼續前進，不需要任何移動。當發現a[j]<=x時，我們需要將這個元素放到小於基值的一邊，於是將i自加1，並交換此時a[i]，與a[j]的元素，然後j自加1。這個時候i指向的是比基值小的那段數據的最後一個元素，j指向的是第一個還沒有判斷的剩餘元素。

上面一步不斷循環直到j指向了r，此時只剩下r沒有和基值判斷了，而a[r]本來就是基值，而除了a[r]以外，a[p]~a[i]是小於基值的部分，a[i+1]~a[r-1]是大於基值的部分，所以此時只需交換a[i+1]和a[r]即可。

由於對數組a從頭到尾掃描一次就可以得到結果，因此這一部分演算法復雜度為o(n)