七種最基本的排序演算法：（面試必會！）
冒泡排序：
最基礎的排序演算法，從數列最前端開始，兩兩比較，如果前一個數比后一個數大，那么兩個數就交換位置，經過一輪遍歷之后，最大的數就到了數列的最后一個位置上，再進行下一次回圈，第二大的數就浮到了倒數第二個位置，這樣一步步較大的數往上浮的程序就是冒泡排序，
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）是指利用堆這種資料結構所設計的一種排序演算法，堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點，堆排序可以說是一種利用堆的概念來排序的選擇排序，分為兩種方法：
- 大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序演算法中用于升序排列；
- 小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序演算法中用于降序排列；
Java代碼實作待更新：
...
時間復雜度 O(nlog以2為底n的對數)，空間復雜度O(1)，穩定性：不穩定
可參考B站視頻：https://www.bilibili.com/video/BV1Gb411a7o3?from=search&seid=13649039337940123139
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/174376.html
標籤：Java