各種排序演算法思想

⑴ 幾種排序演算法的比較

一、八大排序演算法的總體比較

4.3、堆的插入：

每次插入都是將新數據放在數組最後。可以發現從這個新數據的父結點到根結點必然為一個有序的數列，然後將這個新數據插入到這個有序數據中

（1）用大根堆排序的基本思想

先將初始數組建成一個大根堆，此對為初始的無序區；

再將最大的元素和無序區的最後一個記錄交換，由此得到新的無序區和有序區，且滿足<=的值；

由於交換後新的根可能違反堆性質，故將當前無序區調整為堆。然後再次將其中最大的元素和該區間的最後一個記錄交換，由此得到新的無序區和有序區，且仍滿足關系的值<=的值，同樣要將其調整為堆；

..........

直到無序區只有一個元素為止；

4.4：應用

尋找M個數中的前K個最小的數並保持有序；

時間復雜度：O(K)[創建K個元素最大堆的時間復雜度] +（M-K）*log(K)[對剩餘M-K個數據進行比較並每次對最大堆進行從新最大堆化]

5.希爾排序

（1）基本思想

先將整個待排序元素序列分割成若乾子序列（由相隔某個「增量」的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序（因為直接插入排序在元素基本有序的情況下，效率很高）；

（2）適用場景

比較在希爾排序中是最主要的操作，而不是交換。用已知最好的步長序列的希爾排序比直接插入排序要快，甚至在小數組中比快速排序和堆排序還快，但在涉及大量數據時希爾排序還是不如快排；

6.歸並排序

（1）基本思想

首先將初始序列的n個記錄看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到n/2個長度為2的有序子序列，在此基礎上，再對長度為2的有序子序列進行兩兩歸並，得到若干個長度為4的有序子序列，以此類推，直到得到一個長度為n的有序序列為止；

（2）適用場景

若n較大，並且要求排序穩定，則可以選擇歸並排序；

7.簡單選擇排序

（1）基本思想

第一趟：從第一個記錄開始，將後面n-1個記錄進行比較，找到其中最小的記錄和第一個記錄進行交換；

第二趟：從第二個記錄開始，將後面n-2個記錄進行比較，找到其中最小的記錄和第2個記錄進行交換；

...........

第i趟：從第i個記錄開始，將後面n-i個記錄進行比較，找到其中最小的記錄和第i個記錄進行交換；

以此類推，經過n-1趟比較，將n-1個記錄排到位，剩下一個最大記錄直接排在最後；

⑵ 常見排序演算法以及對應的時間復雜度和空間復雜度

排序 ：將雜亂無章的數據，按照一定的方法進行排列的過程叫做排序。

排序大的分類可分為 內排序 和 外排序 ，不需要訪問外存就能進行排序的叫做內排序。

排序也可以分為 穩定排序 和 不穩定排序

穩定排序 ：假設在待排序的文件中，存在兩個或兩個以上的記錄具有相同的關鍵字，在用某種排序法排序後，若這些相同關鍵字的元素的相對次序仍然不變，則這種排序方法是穩定的。即；若 a[i]=a[j] , a[i] 在 a[j] 之前，經過排序後 a[i] 依然在 a[j] 之前。冒泡排序、直接插入排序、二分插入排序、歸並排序，基數排序都是穩定排序。
不穩定排序 ：直接選擇排序、堆排序、快速排序、希爾排序，猴子排序。

以升序為例，比較相鄰的元素，如果第一個比第二個大，則交換他們兩個。如果兩個元素一樣大，則繼續比較下一對。所以冒泡排序是一種穩定排序。

選擇一個基準元素,通常選擇第一個元素或者最後一個元素,通過一趟掃描，將待排序列分成兩部分,一部分比基準元素小,一部分大於等於基準元素,此時基準元素在其排好序後的正確位置,然後再用同樣的方法遞歸地排序劃分的兩部分。快速排序是不穩定排序。

將序列分為兩個部分{{有序序列},{無序}}，每次處理就是將無序數列的第一個元素與有序數列的元素從後往前逐個進行比較，找出插入位置，將該元素插入到有序數列的合適位置中。如果碰到相等的元素，就會把它插入到想等元素後面，順序不會改變，所以直接插入排序是穩定排序。

在直接插入排序的基礎上，對有序序列進行劃分。例如：序列為 {{a[0]......a[i-1]},a[i]} 其中 {a[0]......a[i-1]} 為有序序列，取 a[(i-1)/2] ，將其與 a[i] 比較，即可確定 a[i] 的范圍 (a[0]...a[(i-1)/2] 或者 a[(i-1)/2]...a[i-1]) ,然後繼續在已確定的范圍內進行二分。范圍依次縮小為： 1/2、1/4、1/8、1/16...... 可快速確定a[i]應該插入的位置。二分插入排序也是穩定排序。

將整個序列分割成若干個小的子序列，每個子序列內分別進行插入排序。一般情況下步長取n/2。直到最後一次步長為1，即所有元素在一個組中進行排序。由於希爾排序是先將整個序列劃分為多個子序列進行排序，相同的元素順序在這個過程中順序可能會被打亂，所以希爾排序是不穩定排序。

從待排序的數據元素中，選出最小或最大的元素與序列第一個數交換。直到所有數據排完。直接選擇排序是不穩定排序。例如： {3，3，1} ，第一次排序就將1和第一個3交換，想等元素的順序改變了。

以n=10的一個數組49, 38, 65, 97, 26, 13, 27, 49, 55, 4為例

堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。
最大堆:每個節點的值都大於等於它的孩子節點。
最小堆:每個節點的值都小於等於它的孩子節點。
最大堆第0個數據是最大數，最小堆第0個數據是最小數。
堆排序是不穩定排序

思想

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
如何將兩個有序序列合並？(升序)
{a[0]......a[i-1]},{b[0]......b[j-1]}
若 b[0]<a[0] ，取 b[0] 放入數組 c 中，然後繼續比較數組 a 和 b 中的第一個元素，直到數組 a 和 b 中最後一對元素比較完成。

思想

將數組分成二組 a , b 如果這二組組內的數據都是有序的，那麼就可以按照上述方法對這二組數據進行排序。如果這二組數據是無序的？
可以將 a , b 組各自再分成二組。遞歸操作，直到每個小組只有一個數據，每個小組只有一個元素所以我們可以認為它已經是有序序列，然後進行合並。
先分解後合並。
歸並排序是穩定排序

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。從最低位起從0-9依次掃描序列，一邊掃描一邊將掃描到的數據加到新的序列中，得到一個序列。然後比較高一位，重復上述操作，直到最高位排序完成。數列就變成一個有序序列。基數排序是穩定排序。

以全是二位數的序列舉例

無限猴子定理 :指一隻猴子隨機在打字機鍵盤上按鍵，最後必然可以打出法國國家圖書館的每本圖書。

時間復雜度最低1次，最高可執行到世界的盡頭。。。