資訊專欄INFORMATION COLUMN
摘要：今天，一條就帶大家徹底跨過排序算法這道坎，保姆級教程建議收藏。利用遞歸算法，對分治后的子數組進行排序。基本思想堆排序是利用堆這種數據結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為，它也是不穩定排序。
?本文收錄于專欄《糊涂算法》——從今天起，邁過數據結構和算法這道坎
作者其它優質專欄推薦：
?《技術專家修煉》——搞技術，進大廠，聊人生三合一專欄
?《leetcode 300題》——每天一道算法題，進大廠必備
?《源碼中的設計模式》——理論與實戰的完美結合
?《從實戰學python》——Python的爬蟲，自動化，AI等實戰應用（代碼開源）
點擊跳轉到文末領取粉絲福利
哈嘍，大家好，我是一條~
今天給大家帶來《糊涂算法》專欄的第二期內容——排序算法的講解。相信無論是初學者學習還是大廠面試，都少不了排序算法這關，即使沒學過算法，對冒泡排序也不會陌生。
今天，一條就帶大家徹底跨過「排序算法」這道坎，保姆級教程建議收藏。??
本文配套源碼地址：《八大排序》源碼，提取碼：5ehp
古語云：“兵馬未動，糧草先行”。想跟著一條一塊把「排序算法」弄明白的,建議先準備好以下代碼模板。
? 觀看本教程需知道基本循環語法、兩數交換、雙指針等前置知識。
? 建議先看完代碼和逐步分析后再嘗試自己寫。
Java工程,本文全篇也基于Java語言實現代碼。MainTest測試類中編寫測試模板。/** * 測試類 * Author：一條 * Date：2021/09/23 */public class MainTest { public static void main(String[] args) { //待排序序列 int[] array={6,10,4,5,2,8}; //調用不同排序算法 // BubbleSort.sort(array); // 創建有100000個隨機數據的數組 int[] costArray=new int[100000]; for (int i = 0; i < 100000; i++) { // 生成一個[0,100000) 的一個數 costArray[i] = (int) (Math.random() * 100000); } Date start = new Date(); //過長，先注釋掉逐步打印 //BubbleSort.sort(costArray); Date end = new Date(); System.out.println("耗時："+(end.getTime()-start.getTime())/1000+"s"); }}該段代碼內容主要有兩個功能：
10w個數排好序需要的時間。更加具象的理解時間復雜度的不同通過對亂序序列從前向后遍歷,依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從前移向后部。
像水底下的氣泡一樣逐漸向上冒一樣。
不理解的小伙伴可以用
debug模式逐步分析。
/** * 冒泡排序 * Author：一條 * Date：2021/09/23 */public class BubbleSort{ public static int[] sort(int[] array){ for (int i = 0; i < array.length; i++) { for (int j = 0; j < array.length-1; j++) { //依次比較，將最大的元素交換到最后 if (array[j]>array[j+1]){ // 用臨時變量temp交換兩個值 int temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; } } //輸出每一步的排序結果 System.out.println(Arrays.toString(array)); } return array; }}輸出結果
逐步分析
[6,10,4,5,2,8]6拿出來和后一個10比較，6<10，不用交換。- > j++;10拿出來和后一個4比較,10>4,交換。- > [6,4,10,5,2,8]j++與后一個比較交換。i循環完，打印第一行- > [6, 4, 5, 2, 8, 10]，此時最后一位10在正確位置上。 - > i++4開始，繼續比較交換，倒數第二位8回到正確位置。[2, 4, 5, 6, 8, 10]這時再回去看動圖理解。
記得先注釋掉排序類逐步打印代碼。
時間復雜度：O(n^2)
優化點一
外層第一次遍歷完，最后一位已經是正確的，j就不需要再比較，所以結束條件應改為j-i-1;。
優化點二
因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，因此要在排序過程中設置一個標志flag判斷元素是否進行過交換。從而減少不必要的比較。
優化代碼
public static int[] sortPlus(int[] array){ System.out.println("優化冒泡排序開始----------"); for (int i = 0; i < array.length; i++) { boolean flag=false; for (int j = 0; j < array.length-i-1; j++) { if (array[j]>array[j+1]){ flag=true; int temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; } } if (flag==false){ break; }// System.out.println(Arrays.toString(array)); } return array; }優化測試
通過基礎測試看到當序列已經排好序，即不發生交換后終止循環。
耗時測試由27s優化到17s。
選擇排序和冒泡排序很像，是從亂序序列的數據中，按指定的規則選出某一元素，再依規定交換位置后達到排序的目的。
public class SelectSort { public static int[] sort(int[] array) { System.out.println("選擇排序開始----------"); for (int i = 0; i < array.length; i++) { //每個值只需與他后面的值進行比較，所以從開始 for (int j = i; j < array.length; j++) { //注意此處是哪兩個值比較 if (array[i]>array[j]){ int temp=array[i]; array[i]=array[j]; array[j]=temp; } } System.out.println(Arrays.toString(array)); } return array; }}輸出結果
逐步分析
[6,10,4,5,2,8]6與10比較，不交換 - > j++6與2比較，交換 - > j++2繼續比較，都不交換，確定第一位（最小的數）為2 - > i++[2, 4, 5, 6, 8, 10]這時再回去看動圖理解。
時間復雜度：O(n^2)
上訴代碼中使用交換的方式找到較小值，還可以通過移動的方式，即全部比較完只交換一次。
這種對空間的占有率會有些增益，但對時間的增益幾乎沒有，可忽略，亦不再演示。
把n個亂序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中通過不斷往有序表插入元素，獲取一個局部正確解，逐漸擴大有序序列的長度，直到完成排序。
/** * 插入排序 * Author：一條 * Date：2021/09/23 */public class InsertSort { public static void sort(int[] array) { for (int i = 1; i < array.length; i++) { //插入有序序列，且將有序序列擴大 for (int j = i; j > 0; j--) { if (array[j]>array[j-1]){ int temp=array[j]; array[j]=array[j-1]; array[j-1]=temp; } }// System.out.println(Arrays.toString(array)); } }}輸出結果
見下方希爾排序，就是希爾對插入排序的優化。
希爾排序是插入排序的一個優化，思考往
[2,3,4,5,6]中插入1，需要將所有元素的位置都移動一遍，也就是說在某些極端情況下效率不高，也稱該算法不穩定。希爾排序是插入排序經過改進之后的一個更高效的版本，也稱為縮小增量排序。
希爾排序是把記錄按下標的一定增量分組，對每組使用插入排序；
隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個序列恰被分成一組，算法便終止。
和插入排序一樣，從局部到全部，希爾排序是局部再局部。
/** * 希爾排序 * Author：一條 * Date：2021/09/23 */public class ShellSort { public static void sort(int[] array) { System.out.println("希爾排序開始--------"); //gap初始增量=length/2 逐漸縮小：gap/2 for (int gap = array.length/2; gap > 0 ; gap/=2) { //插入排序 交換法 for (int i = gap; i < array.length ; i++) { int j = i; while(j-gap>=0 && array[j]<array[j-gap]){ //插入排序采用交換法 int temp = array[j]; array[j]=array[j-gap]; array[j-gap]=temp; j-=gap; } } System.out.println(Arrays.toString(array)); } }}輸出結果
無
快速排序（Quicksort）是對冒泡排序的一種改進，相比冒泡排序，每次的交換都是跳躍式的。
將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
體現出分治的思想。
思路如下：
- 首先在這個序列中找一個數作為基準數，為了方便可以取第一個數。
- 遍歷數組，將小于基準數的放置于基準數左邊，大于基準數的放置于基準數右邊。此處可用雙指針實現。
- 此時基準值把數組分為了兩半，基準值算是已歸位（找到排序后的位置）。
- 利用遞歸算法，對分治后的子數組進行排序。
public class QuickSort { public static void sort(int[] array) { System.out.println("快速排序開始---------"); mainSort(array, 0, array.length - 1); } private static void mainSort(int[] array, int left, int right) { if(left > right) { return; } //雙指針 int i=left; int j=right; //base就是基準數 int base = array[left]; //左邊小于基準，右邊大于基準 while (i<j) { //先看右邊，依次往左遞減 while (base<=array[j]&&i<j) { j--; } //再看左邊，依次往右遞增 while (base>=array[i]&&i<j) { i++; } //交換 int temp = array[j]; array[j] = array[i]; array[i] = temp; } //最后將基準為與i和j相等位置的數字交換 array[left] = array[i]; array[i] = base; System.out.println(Arrays.toString(array)); //遞歸調用左半數組 mainSort(array, left, j-1); //遞歸調用右半數組 mainSort(array, j+1, right); }}輸出結果
逐步分析
6作為基準數，利用左右指針使左邊的數<6，右邊的數>6。5作為基準數繼續比較。left > right結束遞歸。快速排序為什么這么快？
優化一
三數取中（median-of-three）：我們目前是拿第一個數作為基準數，對于部分有序序列，會浪費循環，可以用三數取中法優化，感性的小伙伴可自行了解。
優化二
快速排序對于長序列非常快，但對于短序列不如插入排序。可以綜合使用。
此章節對基礎知識要求較高，初學者可跳過。
堆排序是利用堆這種數據結構而設計的一種排序算法，堆排序是一種**選擇排序，**它的最壞，最好，平均時間復雜度均為O(nlogn)，它也是不穩定排序。首先簡單了解下堆結構。
堆
堆是具有以下性質的完全二叉樹：
主要利用堆頂元素最大或最小的特性，通過不斷構建大頂堆，交換堆頂和堆尾，斷尾重構的方式實現排序。
public class HeapSort { public static void sort(int[] array) { //創建堆 for (int i = (array.length - 1) / 2; i >= 0; i--) { //從第一個非葉子結點從下至上，從右至左調整結構 adjustHeap(array, i, array.length); } //調整堆結構+交換堆頂元素與末尾元素 for (int i = array.length - 1; i > 0; i--) { //將堆頂元素與末尾元素進行交換 int temp = array[i]; array[i] = array[0]; array[0] = temp; //重新對堆進行調整 adjustHeap(array, 0, i); } } /** * 調整堆 * @param array 待排序列 * @param parent 父節點 * @param length 待排序列尾元素索引 */ private static void adjustHeap(int[] array, int parent, int length) { //將temp作為父節點 int temp = array[parent]; //左孩子 int lChild = 2 * parent + 1; while (lChild < length) { //右孩子 int rChild = lChild + 1; // 如果有右孩子結點，并且右孩子結點的值大于左孩子結點，則選取右孩子結點 if (rChild < length && array[lChild] < array[rChild]) { lChild++; } // 如果父結點的值已經大于孩子結點的值，則直接結束 if (temp >= array[lChild]) { break; } // 把孩子結點的值賦給父結點 array[parent] = array[lChild]; //選取孩子結點的左孩子結點,繼續向下篩選 parent = lChild; lChild = 2 * lChild + 1; } array[parent] = temp; System.out.println(Arrays.toString(array)); }}輸出結果
逐步分析
優化點關鍵就在于我們以什么手法找到頂部元素該有的位置，有興趣同學可以繼續研究。
歸并排序（MERGE-SORT）是利用歸并的思想實現的排序方法，采用經典的分治（divide-and-conquer）策略。
將亂序序列不斷的分成一半，排好序再拼回去，用遞歸實現。
難點在于如何歸并兩個排好序的數組？
我們可以開辟一個臨時數組，使用快慢指針來輔助我們的歸并。
雖然需要額外空間的來完成這個排序。但是現在計算機的內存都比較大，時間的效率要比空間的效率重要的多。
所以空間換時間也是優化算法時的一個方向。
public class MergeSort { public static void sort(int[] array){ divide(array,0,array.length-1); } private static int[] divide(int[] array, int left, int right) { int mid = (left+right)/2; if(left<right){ divide(array,left,mid); divide(array,mid+1,right); //左右歸并 merge(array,left,mid,right); } System.out.println(Arrays.toString(array)); return array; } public static void merge(int[] array, int left, int mid, int right) { int[] temp = new int[right-left+1]; int i= left; int j = mid+1
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/121429.html
?? 一條獨家專欄 ?? 搞技術，進大廠，聊人生 ?《大廠面試突擊》——面試10多家中大廠的萬字總結 ?《技術專家修煉》——高薪必備，企業真實場景 ?《leetcode 300題》——每天一道算法題，進大廠必備 ?《糊涂算法》——數據結構+算法全面講解 ?《從實戰學python》——python的各種應用 ?《程序人生》——聽一條聊職場，聊人生 ?更多資料點這里 天下難事，必作于易；天下大事，...
摘要：本篇博客我要來和大家一起聊一聊數據結構初階中的最后一篇博客八大經典排序算法的總結，其中會介紹他們的原來，還有復雜度的分析以及各種優化。快速排序遞歸版本快速排序是于年提出的一種二叉樹結構的交換排序方法。 ...
摘要：當到達時等同于直接插入排序，此時序列已基本有序，所有記錄在統一組內排好成有序序列。當面對大量數據時，希爾排序將比直接插入排序更具優勢圖示講解第一趟取增量，所有間隔為的元素分在一組，在各個組中分別進行直接插入排序。 ...
閱讀 719·2023-04-25 20:32
閱讀 2264·2021-11-24 10:27
閱讀 4518·2021-09-29 09:47
閱讀 2241·2021-09-28 09:36
閱讀 3632·2021-09-22 15:27
閱讀 2755·2019-08-30 15:54
閱讀 369·2019-08-30 11:06
閱讀 1271·2019-08-30 10:58
