基礎排序演算法(附加java實現)

七種最基本的排序演算法：（面試必會！）

冒泡排序： 

　　最基礎的排序演算法，從數列最前端開始，兩兩比較，如果前一個數比後一個數大，那麼兩個數就交換位置，經過一輪遍歷之後，最大的數就到了數列的最後一個位置上，再進行下一次迴圈，第二大的數就浮到了倒數第二個位置，這樣一步步較大的數往上浮的過程就是冒泡排序。

java實現：

 1 public void bubbleSort(int[] arr) {
 2     for (int i = 0;  i < arr.length;  i++) {
 3     　　for (int j = 0; j < arr.length - 1; j++) {
 4         　　if(arr[j] > arr[j+1]) {
 5             　　arr[j] = arr[j]^arr[j+1];     //通過一個數異或同一個數兩次，結果不變
 6             　　arr[j+1] = arr[j]^arr[j+1];　　//的方法將兩個數的值進行交換
 7             　　arr[j] = arr[j]^arr[j+1];
 8                }
 9     　　}
10     }
11 }

時間複雜度 O(n^2)，空間複雜度O(1)，穩定性(a=b，排序前a在b的前面，排序後仍在前即為穩定)：穩定 

選擇排序：

　　將一個數列看成有序區和無序區，剛開始，有序區沒有元素，無序區就是整個列表。將無序區的最大（或者最小）的元素找到，並與無序區的第一個元素交換位置，那麼這時，無序區的第一個元素就是最大（或者最小的），此時無序區就變為第一個元素之後的剩餘元素，再對剩餘元素進行找最大（或者最小）元素的操作，並再把該元素與此時無序區第一個元素位置互換，依次類推，那麼整個數列中最大（或者最小）的元素就依次排在了數列中

Java實現：（註意：選擇排序在實現時，是記錄最大值的索引，如果出現更大的值，就更新索引，最後通過索引互換元素）

 1     public void selectSort(int[] arr) {
 2         int subMin;
 3         for (int i = 0; i < arr.length - 1; i++) {
 4             subMin = i;
 5             for (int j = i + 1 ; j < arr.length; j++) {
 6                 if(arr[j] < arr[subMin]) {
 7                     subMin = j;
 8                 }
 9             }        
10             if (i != subMin) {     //一定要加這個判斷，不然當i=subMin的時候，兩個相同的數異或為零
11                 arr[i] = arr[i]^arr[subMin];
12                 arr[subMin] = arr[i]^arr[subMin];
13                 arr[i] = arr[i]^arr[subMin];
14             }
15         }    
16     }

時間複雜度 O(n^2)，空間複雜度O(1)，穩定性：不穩定 

插入排序：

　　插入排序也比較直觀，通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

 1     public void insertSort(int[] arr) {
 2         
 3         //從下標為1的元素開始選擇合適的位置插入，因為下標為0只有一個元素，預設是有序的
 4         for (int i = 1; i < arr.length; i++) {
 5             
 6             //tmp為要插入的元素
 7             int tmp = arr[i];
 8             
 9             //j表示已排序部分的索引，它將逐漸自減
10             int j = i;
11             
12             //挪位置
13             while (j>0 && tmp<arr[j-1]) {
14                 arr[j] = arr[j-1];
15                 j--;    
16             }
17             
18             //插入
19             if(j!=i) {
20                 arr[j] = tmp;        
21             }
22         }
23     }

插入排序在實現上，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。

時間複雜度 O(n^2)，空間複雜度O(1)，穩定性：穩定 

希爾排序：

　　插入排序的改進版，確定一個間隔，然後根據這個間隔進行分組，這個間隔通常為總長度的一半，奇偶數均可。先進行組內排序，組內排序用插入排序的方法。當每組排完序以後，間隔數減半，重新進行分組併進行插入排序，知道間隔數為1，那麼此時對整個數組進行插入排序。

　　那麼為什麼使用希爾排序呢？那是因為，當數列元素數目多大的時候， 插入排序的比較次數會遠遠大於希爾排序。

Java實現

 1     public void shellSort(int[] arr) {
 2         
 3         int gap = 1;
 4         
 5         while (gap<arr.length) {
 6             gap = gap * 3 + 1;
 7         }
 8         
 9         while(gap>0) {
10             for (int i = gap; i < arr.length; i++) {
11                 int tmp = arr[i];
12                 int j = i-gap;
13                 while (j>=0 && arr[j]>tmp) {
14                     arr[j+gap] = arr[j];
15                     j = j-gap;
16                 }
17                 arr[j+gap] = tmp;
18             }
19             gap = (int) Math.floor(gap/3);
20         }
21     }

時間複雜度 O(n^1.3)，空間複雜度O(1)，穩定性：不穩定 

推薦B站視頻：https://www.bilibili.com/video/BV1rE411g7rW [演算法]六分鐘徹底弄懂希爾排序，簡單易懂  by新原家龍之介

歸併排序：

　　核心思想為分治法，並通過遞歸實現。將長度為n的序列分成兩個長度為n/2的子序列，對這兩個子序列分別採用歸併排序，最後將兩個排序好的子序列合併成一個最終的排序序列。

Java代碼待更新

...

時間複雜度 O(nlog以2為底n的對數)，空間複雜度O(n)，穩定性：穩定 

快速排序：

　　快速排序也是分治法加遞歸的思想，首先從數列中挑出一個元素作為基準（pivot）；重新排列數列，所有比基準小的元素放在基準前面，所有比基準大的擺在後面，（相同的數可以到仍一邊）。在這個分區退出以後，該基準就處在數列的中間位置。遞歸地把小於基準值元素的子數列和大於基準值元素的子數列排列。

Java代碼待更新

....

時間複雜度 O(nlog以2為底n的對數)，空間複雜度O(nlog以2為底n的對數)，穩定性：不穩定 

堆排序：

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

1. 大頂堆：每個節點的值都大於或等於其子節點的值，在堆排序演算法中用於升序排列；
2. 小頂堆：每個節點的值都小於或等於其子節點的值，在堆排序演算法中用於降序排列；

Java代碼實現待更新：
...

時間複雜度 O(nlog以2為底n的對數)，空間複雜度O(1)，穩定性：不穩定 

可參考B站視頻：https://www.bilibili.com/video/BV1Gb411a7o3?from=search&seid=13649039337940123139