🌲本文收錄于專欄《糊涂演算法》——從今天起，邁過資料結構和演算法這道坎

作者其它優質專欄推薦：

📚《技術專家修煉》——搞技術，進大廠，聊人生三合一專欄

📚《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個元素，排序程序中通過不斷往有序表插入元素，獲取一個區域正確解，逐漸擴大有序序列的長度，直到完成排序，

動圖講解

2021-09-25 19.20.05

代碼實作

/**
 * 插入排序
 * 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));
    }
}

輸出結果

逐步分析

構建初始堆，將待排序列構成一個大頂堆(或者小頂堆)，升序大頂堆，降序小頂堆；
將堆頂元素與堆尾元素交換，并斷開(從待排序列中移除)堆尾元素，
重新構建堆，
重復2~3，直到待排序列中只剩下一個元素(堆頂元素)，

耗時測驗

演算法優化

優化點關鍵就在于我們以什么手法找到頂部元素該有的位置，有興趣同學可以繼續研究，

歸并排序

基本思想

歸并排序（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;
        int k=0;
        // 把較小的數先移到新陣列中
        while(i<=mid && j<=right){
            if(array[i]<array[j]){
                temp[k++] = array[i++];
            }else{
                temp[k++] = array[j++];
            }
        }
        // 把左邊剩余的數移入陣列
        while(i<=mid){
            temp[k++] = array[i++];
        }
        // 把右邊邊剩余的數移入陣列
        while(j<=right){
            temp[k++] = array[j++];
        }
        // 把新陣列中的數覆寫nums陣列
        for(int x=0;x<temp.length;x++){
            array[x+left] = temp[x];
        }
    }
}

輸出結果

耗時測驗

演算法優化

計數排序

從這里開始都是非比較排序，

基本思想

假如輸入一個數x，如果我們可以找到比該數小的數有幾個，那么就可以直接將x放入到對應的輸出陣列的位置，
比如測驗序列中的x=5，，比5小的有2個，那么毫無疑問5就該排在第三位，

動圖講解

代碼實作

public class CountSort {
    public static void sort(int[] array) {
        System.out.println("計數排序開始--------");
        //計算最大值和最小值，用于確定count[]的長度
        int max = array[0], min = array[0];
        for (int i : array) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        //count[]用于存盤每個元素出現的次數
        int[] count = new int[max - min + 1];

        //統計出現的頻次
        for (int i : array) {
            count[i - min] += 1;//數的位置 上+1
        }

        //創建最侄訓傳的陣列，和原始陣列長度相等，但是排序完成的
        int[] result = new int[array.length];
        int index = 0;//記錄最終陣列的下標

        //先回圈每一個元素  在計數排序器的下標中
        for (int i = 0; i < count.length; i++) {
            //遍歷回圈出現的次數
            for (int j = 0; j < count[i]; j++) {//count[i]:這個數出現的頻率
                result[index++] = i + min;//以為原來減少了min現在加上min，值就變成了原來的值
            }
            System.out.println(Arrays.toString(result));
        }
    }
}

輸出結果

逐步分析

就是將原始陣列中的數值出現的頻率（次數）記錄在新陣列下標中，
遍歷出現的次數，依次放入新陣列，

耗時測驗

說實話，這個速度都驚到我了，計數排序的時間復雜度是O(n),缺點是限制值域為[0,k]的整數，

演算法優化

正常計數排序是從0開始的，本文實作的代碼從min開始，已優化，

總結

本文并沒有具體介紹時間復雜度，因為我放一個數字在這里你根本理解不了他們的差距，

用100000長度的陣列測驗八大排序演算法，化抽象為具體，當資料量很大的時候 nlogn的優勢將會比n^2越來越大，當n=10^5的時候，nlogn的演算法要比n^2的演算法快6000倍，什么概念呢，就是如果我們要處理一個資料集，用nlogn的演算法要處理一天的話，用n^2的演算法將要處理6020天，這就基本相當于是15年，

一個優化改進的演算法可能比一個比一個笨的演算法速度快了許多，這就是大廠考查演算法和我們學習演算法的原因，

古語云：乘眾人之智，則無不任也；用眾人之力，則無不勝也，為了攻克演算法這座大山，我制定了組隊刷題計劃，每天至少1道leetcode演算法題，

駑馬十駕，功在不舍，

如果你剛剛大一，每天堅持學習，你將會至少比別人多刷1200道題，那么畢業時你的工資就可能是別人的3-4倍，

如果你是職場人，每天提升自己，升職加薪，成為技術專家指日可待，

只要你愿意去奮斗，始終走在拼搏的路上，那你的人生，最壞的結果，也不過是大器晚成，

點擊文末卡片加入計劃

粉絲專屬福利

📚Java：1.5G學習資料——回復「資料」
📚演算法：視頻書籍——回復「演算法」

👇 點擊下方卡片關注后回復 關鍵詞 領取👇

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/303704.html

標籤：java

上一篇：樹狀陣列小結

下一篇：超詳細的Spring框架總結，學spring，看這一篇就夠了！

八大排序演算法總結——演算法入門、大廠面試必備（建議收藏）

準備

冒泡排序

基本思想

動圖講解

代碼實作

耗時測驗

演算法優化

選擇排序

基本思想

動圖講解

代碼實作

耗時測驗

演算法優化

插入排序

基本思想

動圖講解

代碼實作

耗時測驗

演算法優化

希爾排序

基本思想

動圖講解

代碼實作

耗時測驗

演算法優化

快速排序

基本思想

動圖講解

代碼實作

耗時測驗

演算法優化

堆排序

基本思想

動圖講解

代碼實作

耗時測驗

演算法優化

歸并排序

基本思想

動圖講解

代碼實作

耗時測驗

演算法優化

計數排序

基本思想

動圖講解

代碼實作

耗時測驗

演算法優化

總結

粉絲專屬福利