Java中常見的查詢演演算法與排序演演算法總結

2023-03-13 06:00:45

資料結構是資料儲存的方式，演演算法是資料計算的方式。所以在開發中，演演算法和資料結構息息相關。今天的講義中會涉及部分資料結構的專業名詞，如果各位鐵粉有疑惑，可以先看一下哥們後面錄製的資料結構，再回頭看演演算法。

1. 基本查詢

也叫做順序查詢

說明：順序查詢適合於儲存結構為陣列或者連結串列。

基本思想：順序查詢也稱為線形查詢，屬於無序查詢演演算法。從資料結構線的一端開始，順序掃描，依次將遍歷到的結點與要查詢的值相比較，若相等則表示查詢成功；若遍歷結束仍沒有找到相同的，表示查詢失敗。

範例程式碼：

public class A01_BasicSearchDemo1 {
    public static void main(String[] args) {
        //基本查詢/順序查詢
        //核心：
        //從0索引開始挨個往後查詢

        //需求：定義一個方法利用基本查詢，查詢某個元素是否存在
        //資料如下：{131, 127, 147, 81, 103, 23, 7, 79}


        int[] arr = {131, 127, 147, 81, 103, 23, 7, 79};
        int number = 82;
        System.out.println(basicSearch(arr, number));

    }

    //引數：
    //一：陣列
    //二：要查詢的元素

    //返回值：
    //元素是否存在
    public static boolean basicSearch(int[] arr, int number){
        //利用基本查詢來查詢number在陣列中是否存在
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == number){
                return true;
            }
        }
        return false;
    }
}

2. 二分查詢

也叫做折半查詢

說明：元素必須是有序的，從小到大，或者從大到小都是可以的。

如果是無序的，也可以先進行排序。但是排序之後，會改變原有資料的順序，查詢出來元素位置跟原來的元素可能是不一樣的，所以排序之後再查詢只能判斷當前資料是否在容器當中，返回的索引無實際的意義。

基本思想：也稱為是折半查詢，屬於有序查詢演演算法。用給定值先與中間結點比較。比較完之後有三種情況：

相等

說明找到了

要查詢的資料比中間節點小

說明要查詢的數位在中間節點左邊

要查詢的資料比中間節點大

說明要查詢的數位在中間節點右邊

程式碼範例：

package com.itheima.search;

public class A02_BinarySearchDemo1 {
    public static void main(String[] args) {
        //二分查詢/折半查詢
        //核心：
        //每次排除一半的查詢範圍

        //需求：定義一個方法利用二分查詢，查詢某個元素在陣列中的索引
        //資料如下：{7, 23, 79, 81, 103, 127, 131, 147}

        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
        System.out.println(binarySearch(arr, 150));
    }

    public static int binarySearch(int[] arr, int number){
        //1.定義兩個變數記錄要查詢的範圍
        int min = 0;
        int max = arr.length - 1;

        //2.利用迴圈不斷的去找要查詢的資料
        while(true){
            if(min > max){
                return -1;
            }
            //3.找到min和max的中間位置
            int mid = (min + max) / 2;
            //4.拿著mid指向的元素跟要查詢的元素進行比較
            if(arr[mid] > number){
                //4.1 number在mid的左邊
                //min不變，max = mid - 1；
                max = mid - 1;
            }else if(arr[mid] < number){
                //4.2 number在mid的右邊
                //max不變，min = mid + 1;
                min = mid + 1;
            }else{
                //4.3 number跟mid指向的元素一樣
                //找到了
                return mid;
            }

        }
    }
}

3. 插值查詢

在介紹插值查詢之前，先考慮一個問題：

為什麼二分查詢演演算法一定要是折半，而不是折四分之一或者折更多呢？

其實就是因為方便，簡單，但是如果我能在二分查詢的基礎上，讓中間的mid點，儘可能靠近想要查詢的元素，那不就能提高查詢的效率了嗎？

二分查詢中查詢點計算如下：

mid=(low+high)/2, 即mid=low+1/2*(high-low);

我們可以將查詢的點改進為如下：

mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，

這樣，讓mid值的變化更靠近關鍵字key，這樣也就間接地減少了比較次數。

基本思想：基於二分查詢演演算法，將查詢點的選擇改進為自適應選擇，可以提高查詢效率。當然，差值查詢也屬於有序查詢。

細節：對於表長較大，而關鍵字分佈又比較均勻的查詢表來說，插值查詢演演算法的平均效能比折半查詢要好的多。反之，陣列中如果分佈非常不均勻，那麼插值查詢未必是很合適的選擇。

程式碼跟二分查詢類似，只要修改一下mid的計算方式即可。

4. 斐波那契查詢

在介紹斐波那契查詢演演算法之前，我們先介紹一下很它緊密相連並且大家都熟知的一個概念——黃金分割。

黃金比例又稱黃金分割，是指事物各部分間一定的數學比例關係，即將整體一分為二，較大部分與較小部分之比等於整體與較大部分之比，其比值約為1:0.618或1.618:1。

0.618被公認為最具有審美意義的比例數位，這個數值的作用不僅僅體現在諸如繪畫、雕塑、音樂、建築等藝術領域，而且在管理、工程設計等方面也有著不可忽視的作用。因此被稱為黃金分割。

在數學中有一個非常有名的數學規律：斐波那契數列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….

（從第三個數開始，後邊每一個數都是前兩個數的和）。

然後我們會發現，隨著斐波那契數列的遞增，前後兩個數的比值會越來越接近0.618，利用這個特性，我們就可以將黃金比例運用到查詢技術中。

基本思想：也是二分查詢的一種提升演演算法，通過運用黃金比例的概念在數列中選擇查詢點進行查詢，提高查詢效率。同樣地，斐波那契查詢也屬於一種有序查詢演演算法。

斐波那契查詢也是在二分查詢的基礎上進行了優化，優化中間點mid的計算方式即可

程式碼範例：

public class FeiBoSearchDemo {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println(search(arr, 1234));
    }

    public static int[] getFeiBo() {
        int[] arr = new int[maxSize];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr;
    }

    public static int search(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        //表示斐波那契數分割數的下標值
        int index = 0;
        int mid = 0;
        //呼叫斐波那契數列
        int[] f = getFeiBo();
        //獲取斐波那契分割數值的下標
        while (high > (f[index] - 1)) {
            index++;
        }
        //因為f[k]值可能大於a的長度，因此需要使用Arrays工具類，構造一個新法陣列，並指向temp[],不足的部分會使用0補齊
        int[] temp = Arrays.copyOf(arr, f[index]);
        //實際需要使用arr陣列的最後一個數來填充不足的部分
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        //使用while迴圈處理，找到key值
        while (low <= high) {
            mid = low + f[index - 1] - 1;
            if (key < temp[mid]) {//向陣列的前面部分進行查詢
                high = mid - 1;
                /*
                  對k--進行理解
                  1.全部元素=前面的元素+後面的元素
                  2.f[k]=k[k-1]+f[k-2]
                  因為前面有k-1個元素沒所以可以繼續分為f[k-1]=f[k-2]+f[k-3]
                  即在f[k-1]的前面繼續查詢k--
                  即下次迴圈,mid=f[k-1-1]-1
                 */
                index--;
            } else if (key > temp[mid]) {//向陣列的後面的部分進行查詢
                low = mid + 1;
                index -= 2;
            } else {//找到了
                //需要確定返回的是哪個下標
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}

5. 分塊查詢

當資料表中的資料元素很多時，可以採用分塊查詢。

汲取了順序查詢和折半查詢各自的優點，既有動態結構，又適於快速查詢

分塊查詢適用於資料較多，但是資料不會發生變化的情況，如果需要一邊新增一邊查詢，建議使用雜湊查詢

分塊查詢的過程：

需要把資料分成N多小塊，塊與塊之間不能有資料重複的交集。
給每一塊建立物件單獨儲存到陣列當中
查詢資料的時候，先在陣列查，當前資料屬於哪一塊
再到這一塊中順序查詢

程式碼範例：

package com.itheima.search;

public class A03_BlockSearchDemo {
    public static void main(String[] args) {
        /*
            分塊查詢
            核心思想：
                塊內無序，塊間有序
            實現步驟：
                1.建立陣列blockArr存放每一個塊物件的資訊
                2.先查詢blockArr確定要查詢的資料屬於哪一塊
                3.再單獨遍歷這一塊資料即可
        */
        int[] arr = {16, 5, 9, 12,21, 18,
                     32, 23, 37, 26, 45, 34,
                     50, 48, 61, 52, 73, 66};

        //建立三個塊的物件
        Block b1 = new Block(21,0,5);
        Block b2 = new Block(45,6,11);
        Block b3 = new Block(73,12,17);

        //定義陣列用來管理三個塊的物件（索引表）
        Block[] blockArr = {b1,b2,b3};

        //定義一個變數用來記錄要查詢的元素
        int number = 37;

        //呼叫方法，傳遞索引表，陣列，要查詢的元素
        int index = getIndex(blockArr,arr,number);

        //列印一下
        System.out.println(index);



    }

    //利用分塊查詢的原理，查詢number的索引
    private static int getIndex(Block[] blockArr, int[] arr, int number) {
        //1.確定number是在那一塊當中
        int indexBlock = findIndexBlock(blockArr, number);

        if(indexBlock == -1){
            //表示number不在陣列當中
            return -1;
        }

        //2.獲取這一塊的起始索引和結束索引   --- 30
        // Block b1 = new Block(21,0,5);   ----  0
        // Block b2 = new Block(45,6,11);  ----  1
        // Block b3 = new Block(73,12,17); ----  2
        int startIndex = blockArr[indexBlock].getStartIndex();
        int endIndex = blockArr[indexBlock].getEndIndex();

        //3.遍歷
        for (int i = startIndex; i <= endIndex; i++) {
            if(arr[i] == number){
                return i;
            }
        }
        return -1;
    }


    //定義一個方法，用來確定number在哪一塊當中
    public static int findIndexBlock(Block[] blockArr,int number){ //100


        //從0索引開始遍歷blockArr，如果number小於max，那麼就表示number是在這一塊當中的
        for (int i = 0; i < blockArr.length; i++) {
            if(number <= blockArr[i].getMax()){
                return i;
            }
        }
        return -1;
    }



}

class Block{
    private int max;//最大值
    private int startIndex;//起始索引
    private int endIndex;//結束索引


    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    /**
     * 獲取
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 設定
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 獲取
     * @return startIndex
     */
    public int getStartIndex() {
        return startIndex;
    }

    /**
     * 設定
     * @param startIndex
     */
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    /**
     * 獲取
     * @return endIndex
     */
    public int getEndIndex() {
        return endIndex;
    }

    /**
     * 設定
     * @param endIndex
     */
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public String toString() {
        return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}

6. 雜湊查詢

雜湊查詢是分塊查詢的進階版，適用於資料一邊新增一邊查詢的情況。

一般是陣列 + 連結串列的結合體或者是陣列+連結串列 + 紅黑樹的結合體

在課程中，為了讓大家方便理解，所以規定：

陣列的0索引處儲存1~100
陣列的1索引處儲存101~200
陣列的2索引處儲存201~300
以此類推

但是實際上，我們一般不會採取這種方式，因為這種方式容易導致一塊區域新增的元素過多，導致效率偏低。

更多的是先計算出當前資料的雜湊值，用雜湊值跟陣列的長度進行計算，計算出應存入的位置，再掛在陣列的後面形成連結串列，如果掛的元素太多而且陣列長度過長，我們也會把連結串列轉化為紅黑樹，進一步提高效率。

具體的過程，大家可以參見B站阿瑋講解課程：從入門到起飛。在集合章節詳細講解了雜湊表的資料結構。全程採取動畫形式講解，讓大家一目瞭然。

在此不多做闡述。

7. 樹表查詢

本知識點涉及到資料結構：樹。

建議先看一下後面阿瑋講解的資料結構，再回頭理解。

基本思想：二叉查詢樹是先對待查詢的資料進行生成樹，確保樹的左分支的值小於右分支的值，然後在就行和每個節點的父節點比較大小，查詢最適合的範圍。這個演演算法的查詢效率很高，但是如果使用這種查詢方法要首先建立樹。

二叉查詢樹（BinarySearch Tree，也叫二元搜尋樹，或稱二叉排序樹Binary Sort Tree），具有下列性質的二元樹：

1）若任意節點左子樹上所有的資料，均小於本身；

2）若任意節點右子樹上所有的資料，均大於本身；

二叉查詢樹性質：對二叉查詢樹進行中序遍歷，即可得到有序的數列。

不同形態的二叉查詢樹如下圖所示：

基於二叉查詢樹進行優化，進而可以得到其他的樹表查詢演演算法，如平衡樹、紅黑樹等高效演演算法。

具體細節大家可以參見B站阿瑋講解課程：從入門到起飛。在集合章節詳細講解了樹資料結構。全程採取動畫形式講解，讓大家一目瞭然。

在此不多做闡述。

不管是二叉查詢樹，還是平衡二元樹，還是紅黑樹，查詢的效能都比較高

十大排序演演算法

1. 氣泡排序

氣泡排序（Bubble Sort）也是一種簡單直觀的排序演演算法。

它重複的遍歷過要排序的數列，一次比較相鄰的兩個元素，如果他們的順序錯誤就把他們交換過來。

這個演演算法的名字由來是因為越大的元素會經由交換慢慢"浮"到最後面。

當然，大家可以按照從大到小的方式進行排列。

1.1 演演算法步驟

相鄰的元素兩兩比較，大的放右邊，小的放左邊
第一輪比較完畢之後，最大值就已經確定，第二輪可以少迴圈一次，後面以此類推
如果陣列中有n個資料，總共我們只要執行n-1輪的程式碼就可以

1.2 動圖演示

1.3 程式碼範例

public class A01_BubbleDemo {
    public static void main(String[] args) {
        /*
            氣泡排序：
            核心思想：
            1，相鄰的元素兩兩比較，大的放右邊，小的放左邊。
            2，第一輪比較完畢之後，最大值就已經確定，第二輪可以少迴圈一次，後面以此類推。
            3，如果陣列中有n個資料，總共我們只要執行n-1輪的程式碼就可以。
        */


        //1.定義陣列
        int[] arr = {2, 4, 5, 3, 1};

        //2.利用氣泡排序將陣列中的資料變成 1 2 3 4 5

        //外迴圈：表示我要執行多少輪。 如果有n個資料，那麼執行n - 1 輪
        for (int i = 0; i < arr.length - 1; i++) {
            //內迴圈：每一輪中我如何比較資料並找到當前的最大值
            //-1：為了防止索引越界
            //-i：提高效率，每一輪執行的次數應該比上一輪少一次。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //i 依次表示陣列中的每一個索引：0 1 2 3 4
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        printArr(arr);




    }

    private static void printArr(int[] arr) {
        //3.遍歷陣列
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

2. 選擇排序

2.1 演演算法步驟

從0索引開始，跟後面的元素一一比較
小的放前面，大的放後面
第一次迴圈結束後，最小的資料已經確定
第二次迴圈從1索引開始以此類推
第三輪迴圈從2索引開始以此類推
第四輪迴圈從3索引開始以此類推。

2.2 動圖演示

public class A02_SelectionDemo {
    public static void main(String[] args) {

        /*
            選擇排序：
                1，從0索引開始，跟後面的元素一一比較。
                2，小的放前面，大的放後面。
                3，第一次迴圈結束後，最小的資料已經確定。
                4，第二次迴圈從1索引開始以此類推。

         */


        //1.定義陣列
        int[] arr = {2, 4, 5, 3, 1};


        //2.利用選擇排序讓陣列變成 1 2 3 4 5
       /* //第一輪：
        //從0索引開始，跟後面的元素一一比較。
        for (int i = 0 + 1; i < arr.length; i++) {
            //拿著0索引跟後面的資料進行比較
            if(arr[0] > arr[i]){
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
            }
        }*/

        //最終程式碼：
        //外迴圈：幾輪
        //i:表示這一輪中，我拿著哪個索引上的資料跟後面的資料進行比較並交換
        for (int i = 0; i < arr.length -1; i++) {
            //內迴圈：每一輪我要幹什麼事情？
            //拿著i跟i後面的資料進行比較交換
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }


        printArr(arr);


    }
    private static void printArr(int[] arr) {
        //3.遍歷陣列
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

3. 插入排序

插入排序的程式碼實現雖然沒有氣泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序演演算法，它的工作原理是通過建立有序序列和無序序列，然後再遍歷無序序列得到裡面每一個數位，把每一個數位插入到有序序列中正確的位置。

插入排序在插入的時候，有優化演演算法，在遍歷有序序列找正確位置時，可以採取二分查詢

3.1 演演算法步驟

將0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最後一個當成是無序的。

遍歷無序的資料，將遍歷到的元素插入有序序列中適當的位置，如遇到相同資料，插在後面。

N的範圍：0~最大索引

3.2 動圖演示

package com.itheima.mysort;


public class A03_InsertDemo {
    public static void main(String[] args) {
        /*
            插入排序：
                將0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最後一個當成是無序的。
                遍歷無序的資料，將遍歷到的元素插入有序序列中適當的位置，如遇到相同資料，插在後面。
                N的範圍：0~最大索引

        */
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        //1.找到無序的哪一組陣列是從哪個索引開始的。  2
        int startIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > arr[i + 1]){
                startIndex = i + 1;
                break;
            }
        }

        //2.遍歷從startIndex開始到最後一個元素，依次得到無序的哪一組資料中的每一個元素
        for (int i = startIndex; i < arr.length; i++) {
            //問題：如何把遍歷到的資料，插入到前面有序的這一組當中

            //記錄當前要插入資料的索引
            int j = i;

            while(j > 0 && arr[j] < arr[j - 1]){
                //交換位置
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j--;
            }

        }
        printArr(arr);
    }

    private static void printArr(int[] arr) {
        //3.遍歷陣列
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

4. 快速排序

快速排序是由東尼·霍爾所發展的一種排序演演算法。

快速排序又是一種分而治之思想在排序演演算法上的典型應用。

快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！

它是處理巨量資料最快的排序演演算法之一了。

4.1 演演算法步驟

從數列中挑出一個元素，一般都是左邊第一個數位，稱為 "基準數";
建立兩個指標，一個從前往後走，一個從後往前走。
先執行後面的指標，找出第一個比基準數小的數位
再執行前面的指標，找出第一個比基準數大的數位
交換兩個指標指向的數位
直到兩個指標相遇
將基準數跟指標指向位置的數位交換位置，稱之為：基準數歸位。
第一輪結束之後，基準數左邊的數位都是比基準數小的，基準數右邊的數位都是比基準數大的。
把基準數左邊看做一個序列，把基準數右邊看做一個序列，按照剛剛的規則遞迴排序

4.2 動圖演示

package com.itheima.mysort;

import java.util.Arrays;

public class A05_QuickSortDemo {
   public static void main(String[] args) {
       System.out.println(Integer.MAX_VALUE);
       System.out.println(Integer.MIN_VALUE);
     /*
       快速排序：
           第一輪：以0索引的數位為基準數，確定基準數在陣列中正確的位置。
           比基準數小的全部在左邊，比基準數大的全部在右邊。
           後面以此類推。
     */

       int[] arr = {1,1, 6, 2, 7, 9, 3, 4, 5, 1,10, 8};


       //int[] arr = new int[1000000];

      /* Random r = new Random();
       for (int i = 0; i < arr.length; i++) {
           arr[i] = r.nextInt();
       }*/

以上就是Java中常見的查詢演演算法與排序演演算法總結的詳細內容，更多關於Java查詢排序演演算法的資料請關注it145.com其它相關文章！