欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java中常見的查找算法與排序算法總結(jié)

 更新時間:2023年03月11日 09:50:21   作者:瑪拉_以琳  
數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存儲的方式,算法是數(shù)據(jù)計算的方式。所以在開發(fā)中,算法和數(shù)據(jù)結(jié)構(gòu)息息相關(guān)。本文為大家整理了Java中常見的查找與排序算法的實現(xiàn),需要的可以參考一下

數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存儲的方式,算法是數(shù)據(jù)計算的方式。所以在開發(fā)中,算法和數(shù)據(jù)結(jié)構(gòu)息息相關(guān)。今天的講義中會涉及部分?jǐn)?shù)據(jù)結(jié)構(gòu)的專業(yè)名詞,如果各位鐵粉有疑惑,可以先看一下哥們后面錄制的數(shù)據(jù)結(jié)構(gòu),再回頭看算法。

1. 基本查找

也叫做順序查找

說明:順序查找適合于存儲結(jié)構(gòu)為數(shù)組或者鏈表。

基本思想:順序查找也稱為線形查找,屬于無序查找算法。從數(shù)據(jù)結(jié)構(gòu)線的一端開始,順序掃描,依次將遍歷到的結(jié)點與要查找的值相比較,若相等則表示查找成功;若遍歷結(jié)束仍沒有找到相同的,表示查找失敗。

示例代碼:

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

        //需求:定義一個方法利用基本查找,查詢某個元素是否存在
        //數(shù)據(jù)如下:{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));

    }

    //參數(shù):
    //一:數(shù)組
    //二:要查找的元素

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

2. 二分查找

也叫做折半查找

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

如果是無序的,也可以先進(jìn)行排序。但是排序之后,會改變原有數(shù)據(jù)的順序,查找出來元素位置跟原來的元素可能是不一樣的,所以排序之后再查找只能判斷當(dāng)前數(shù)據(jù)是否在容器當(dāng)中,返回的索引無實際的意義。

基本思想:也稱為是折半查找,屬于有序查找算法。用給定值先與中間結(jié)點比較。比較完之后有三種情況:

相等

說明找到了

要查找的數(shù)據(jù)比中間節(jié)點小

說明要查找的數(shù)字在中間節(jié)點左邊

要查找的數(shù)據(jù)比中間節(jié)點大

說明要查找的數(shù)字在中間節(jié)點右邊

代碼示例:

package com.itheima.search;

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

        //需求:定義一個方法利用二分查找,查詢某個元素在數(shù)組中的索引
        //數(shù)據(jù)如下:{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.利用循環(huán)不斷的去找要查找的數(shù)據(jù)
        while(true){
            if(min > max){
                return -1;
            }
            //3.找到min和max的中間位置
            int mid = (min + max) / 2;
            //4.拿著mid指向的元素跟要查找的元素進(jìn)行比較
            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. 插值查找

在介紹插值查找之前,先考慮一個問題:

為什么二分查找算法一定要是折半,而不是折四分之一或者折更多呢?

其實就是因為方便,簡單,但是如果我能在二分查找的基礎(chǔ)上,讓中間的mid點,盡可能靠近想要查找的元素,那不就能提高查找的效率了嗎?

二分查找中查找點計算如下:

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

我們可以將查找的點改進(jìn)為如下:

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

這樣,讓mid值的變化更靠近關(guān)鍵字key,這樣也就間接地減少了比較次數(shù)。

基本思想:基于二分查找算法,將查找點的選擇改進(jìn)為自適應(yīng)選擇,可以提高查找效率。當(dāng)然,差值查找也屬于有序查找。

細(xì)節(jié):對于表長較大,而關(guān)鍵字分布又比較均勻的查找表來說,插值查找算法的平均性能比折半查找要好的多。反之,數(shù)組中如果分布非常不均勻,那么插值查找未必是很合適的選擇。

代碼跟二分查找類似,只要修改一下mid的計算方式即可。

4. 斐波那契查找

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

黃金比例又稱黃金分割,是指事物各部分間一定的數(shù)學(xué)比例關(guān)系,即將整體一分為二,較大部分與較小部分之比等于整體與較大部分之比,其比值約為1:0.618或1.618:1。

0.618被公認(rèn)為最具有審美意義的比例數(shù)字,這個數(shù)值的作用不僅僅體現(xiàn)在諸如繪畫、雕塑、音樂、建筑等藝術(shù)領(lǐng)域,而且在管理、工程設(shè)計等方面也有著不可忽視的作用。因此被稱為黃金分割。

在數(shù)學(xué)中有一個非常有名的數(shù)學(xué)規(guī)律:斐波那契數(shù)列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….

(從第三個數(shù)開始,后邊每一個數(shù)都是前兩個數(shù)的和)。

然后我們會發(fā)現(xiàn),隨著斐波那契數(shù)列的遞增,前后兩個數(shù)的比值會越來越接近0.618,利用這個特性,我們就可以將黃金比例運用到查找技術(shù)中。

基本思想:也是二分查找的一種提升算法,通過運用黃金比例的概念在數(shù)列中選擇查找點進(jìn)行查找,提高查找效率。同樣地,斐波那契查找也屬于一種有序查找算法。

斐波那契查找也是在二分查找的基礎(chǔ)上進(jìn)行了優(yōu)化,優(yōu)化中間點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;
        //表示斐波那契數(shù)分割數(shù)的下標(biāo)值
        int index = 0;
        int mid = 0;
        //調(diào)用斐波那契數(shù)列
        int[] f = getFeiBo();
        //獲取斐波那契分割數(shù)值的下標(biāo)
        while (high > (f[index] - 1)) {
            index++;
        }
        //因為f[k]值可能大于a的長度,因此需要使用Arrays工具類,構(gòu)造一個新法數(shù)組,并指向temp[],不足的部分會使用0補齊
        int[] temp = Arrays.copyOf(arr, f[index]);
        //實際需要使用arr數(shù)組的最后一個數(shù)來填充不足的部分
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        //使用while循環(huán)處理,找到key值
        while (low <= high) {
            mid = low + f[index - 1] - 1;
            if (key < temp[mid]) {//向數(shù)組的前面部分進(jìn)行查找
                high = mid - 1;
                /*
                  對k--進(jìn)行理解
                  1.全部元素=前面的元素+后面的元素
                  2.f[k]=k[k-1]+f[k-2]
                  因為前面有k-1個元素沒所以可以繼續(xù)分為f[k-1]=f[k-2]+f[k-3]
                  即在f[k-1]的前面繼續(xù)查找k--
                  即下次循環(huán),mid=f[k-1-1]-1
                 */
                index--;
            } else if (key > temp[mid]) {//向數(shù)組的后面的部分進(jìn)行查找
                low = mid + 1;
                index -= 2;
            } else {//找到了
                //需要確定返回的是哪個下標(biāo)
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}

5. 分塊查找

當(dāng)數(shù)據(jù)表中的數(shù)據(jù)元素很多時,可以采用分塊查找。

汲取了順序查找和折半查找各自的優(yōu)點,既有動態(tài)結(jié)構(gòu),又適于快速查找

分塊查找適用于數(shù)據(jù)較多,但是數(shù)據(jù)不會發(fā)生變化的情況,如果需要一邊添加一邊查找,建議使用哈希查找

分塊查找的過程:

  • 需要把數(shù)據(jù)分成N多小塊,塊與塊之間不能有數(shù)據(jù)重復(fù)的交集。
  • 給每一塊創(chuàng)建對象單獨存儲到數(shù)組當(dāng)中
  • 查找數(shù)據(jù)的時候,先在數(shù)組查,當(dāng)前數(shù)據(jù)屬于哪一塊
  • 再到這一塊中順序查找

代碼示例:

package com.itheima.search;

public class A03_BlockSearchDemo {
    public static void main(String[] args) {
        /*
            分塊查找
            核心思想:
                塊內(nèi)無序,塊間有序
            實現(xiàn)步驟:
                1.創(chuàng)建數(shù)組blockArr存放每一個塊對象的信息
                2.先查找blockArr確定要查找的數(shù)據(jù)屬于哪一塊
                3.再單獨遍歷這一塊數(shù)據(jù)即可
        */
        int[] arr = {16, 5, 9, 12,21, 18,
                     32, 23, 37, 26, 45, 34,
                     50, 48, 61, 52, 73, 66};

        //創(chuàng)建三個塊的對象
        Block b1 = new Block(21,0,5);
        Block b2 = new Block(45,6,11);
        Block b3 = new Block(73,12,17);

        //定義數(shù)組用來管理三個塊的對象(索引表)
        Block[] blockArr = {b1,b2,b3};

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

        //調(diào)用方法,傳遞索引表,數(shù)組,要查找的元素
        int index = getIndex(blockArr,arr,number);

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



    }

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

        if(indexBlock == -1){
            //表示number不在數(shù)組當(dāng)中
            return -1;
        }

        //2.獲取這一塊的起始索引和結(jié)束索引   --- 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在哪一塊當(dāng)中
    public static int findIndexBlock(Block[] blockArr,int number){ //100


        //從0索引開始遍歷blockArr,如果number小于max,那么就表示number是在這一塊當(dāng)中的
        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;//結(jié)束索引


    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;
    }

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

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

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

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

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

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

6. 哈希查找

哈希查找是分塊查找的進(jìn)階版,適用于數(shù)據(jù)一邊添加一邊查找的情況。

一般是數(shù)組 + 鏈表的結(jié)合體或者是數(shù)組+鏈表 + 紅黑樹的結(jié)合體

在課程中,為了讓大家方便理解,所以規(guī)定:

  • 數(shù)組的0索引處存儲1~100
  • 數(shù)組的1索引處存儲101~200
  • 數(shù)組的2索引處存儲201~300
  • 以此類推

但是實際上,我們一般不會采取這種方式,因為這種方式容易導(dǎo)致一塊區(qū)域添加的元素過多,導(dǎo)致效率偏低。

更多的是先計算出當(dāng)前數(shù)據(jù)的哈希值,用哈希值跟數(shù)組的長度進(jìn)行計算,計算出應(yīng)存入的位置,再掛在數(shù)組的后面形成鏈表,如果掛的元素太多而且數(shù)組長度過長,我們也會把鏈表轉(zhuǎn)化為紅黑樹,進(jìn)一步提高效率。

具體的過程,大家可以參見B站阿瑋講解課程:從入門到起飛。在集合章節(jié)詳細(xì)講解了哈希表的數(shù)據(jù)結(jié)構(gòu)。全程采取動畫形式講解,讓大家一目了然。

在此不多做闡述。

7. 樹表查找

本知識點涉及到數(shù)據(jù)結(jié)構(gòu):樹。

建議先看一下后面阿瑋講解的數(shù)據(jù)結(jié)構(gòu),再回頭理解。

基本思想:二叉查找樹是先對待查找的數(shù)據(jù)進(jìn)行生成樹,確保樹的左分支的值小于右分支的值,然后在就行和每個節(jié)點的父節(jié)點比較大小,查找最適合的范圍。 這個算法的查找效率很高,但是如果使用這種查找方法要首先創(chuàng)建樹。

二叉查找樹(BinarySearch Tree,也叫二叉搜索樹,或稱二叉排序樹Binary Sort Tree),具有下列性質(zhì)的二叉樹:

1)若任意節(jié)點左子樹上所有的數(shù)據(jù),均小于本身;

2)若任意節(jié)點右子樹上所有的數(shù)據(jù),均大于本身;

二叉查找樹性質(zhì):對二叉查找樹進(jìn)行中序遍歷,即可得到有序的數(shù)列。

不同形態(tài)的二叉查找樹如下圖所示:

基于二叉查找樹進(jìn)行優(yōu)化,進(jìn)而可以得到其他的樹表查找算法,如平衡樹、紅黑樹等高效算法。

具體細(xì)節(jié)大家可以參見B站阿瑋講解課程:從入門到起飛。在集合章節(jié)詳細(xì)講解了樹數(shù)據(jù)結(jié)構(gòu)。全程采取動畫形式講解,讓大家一目了然。

在此不多做闡述。

不管是二叉查找樹,還是平衡二叉樹,還是紅黑樹,查找的性能都比較高

十大排序算法

1. 冒泡排序

冒泡排序(Bubble Sort)也是一種簡單直觀的排序算法。

它重復(fù)的遍歷過要排序的數(shù)列,一次比較相鄰的兩個元素,如果他們的順序錯誤就把他們交換過來。

這個算法的名字由來是因為越大的元素會經(jīng)由交換慢慢"浮"到最后面。

當(dāng)然,大家可以按照從大到小的方式進(jìn)行排列。

1.1 算法步驟

  • 相鄰的元素兩兩比較,大的放右邊,小的放左邊
  • 第一輪比較完畢之后,最大值就已經(jīng)確定,第二輪可以少循環(huán)一次,后面以此類推
  • 如果數(shù)組中有n個數(shù)據(jù),總共我們只要執(zhí)行n-1輪的代碼就可以

1.2 動圖演示

1.3 代碼示例

public class A01_BubbleDemo {
    public static void main(String[] args) {
        /*
            冒泡排序:
            核心思想:
            1,相鄰的元素兩兩比較,大的放右邊,小的放左邊。
            2,第一輪比較完畢之后,最大值就已經(jīng)確定,第二輪可以少循環(huán)一次,后面以此類推。
            3,如果數(shù)組中有n個數(shù)據(jù),總共我們只要執(zhí)行n-1輪的代碼就可以。
        */


        //1.定義數(shù)組
        int[] arr = {2, 4, 5, 3, 1};

        //2.利用冒泡排序?qū)?shù)組中的數(shù)據(jù)變成 1 2 3 4 5

        //外循環(huán):表示我要執(zhí)行多少輪。 如果有n個數(shù)據(jù),那么執(zhí)行n - 1 輪
        for (int i = 0; i < arr.length - 1; i++) {
            //內(nèi)循環(huán):每一輪中我如何比較數(shù)據(jù)并找到當(dāng)前的最大值
            //-1:為了防止索引越界
            //-i:提高效率,每一輪執(zhí)行的次數(shù)應(yīng)該比上一輪少一次。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //i 依次表示數(shù)組中的每一個索引: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.遍歷數(shù)組
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

2. 選擇排序

2.1 算法步驟

  • 從0索引開始,跟后面的元素一一比較
  • 小的放前面,大的放后面
  • 第一次循環(huán)結(jié)束后,最小的數(shù)據(jù)已經(jīng)確定
  • 第二次循環(huán)從1索引開始以此類推
  • 第三輪循環(huán)從2索引開始以此類推
  • 第四輪循環(huán)從3索引開始以此類推。

2.2 動圖演示

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

        /*
            選擇排序:
                1,從0索引開始,跟后面的元素一一比較。
                2,小的放前面,大的放后面。
                3,第一次循環(huán)結(jié)束后,最小的數(shù)據(jù)已經(jīng)確定。
                4,第二次循環(huán)從1索引開始以此類推。

         */


        //1.定義數(shù)組
        int[] arr = {2, 4, 5, 3, 1};


        //2.利用選擇排序讓數(shù)組變成 1 2 3 4 5
       /* //第一輪:
        //從0索引開始,跟后面的元素一一比較。
        for (int i = 0 + 1; i < arr.length; i++) {
            //拿著0索引跟后面的數(shù)據(jù)進(jìn)行比較
            if(arr[0] > arr[i]){
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
            }
        }*/

        //最終代碼:
        //外循環(huán):幾輪
        //i:表示這一輪中,我拿著哪個索引上的數(shù)據(jù)跟后面的數(shù)據(jù)進(jìn)行比較并交換
        for (int i = 0; i < arr.length -1; i++) {
            //內(nèi)循環(huán):每一輪我要干什么事情?
            //拿著i跟i后面的數(shù)據(jù)進(jìn)行比較交換
            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.遍歷數(shù)組
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

3. 插入排序

插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴,但它的原理應(yīng)該是最容易理解的了,因為只要打過撲克牌的人都應(yīng)該能夠秒懂。插入排序是一種最簡單直觀的排序算法,它的工作原理是通過創(chuàng)建有序序列和無序序列,然后再遍歷無序序列得到里面每一個數(shù)字,把每一個數(shù)字插入到有序序列中正確的位置。

插入排序在插入的時候,有優(yōu)化算法,在遍歷有序序列找正確位置時,可以采取二分查找

3.1 算法步驟

將0索引的元素到N索引的元素看做是有序的,把N+1索引的元素到最后一個當(dāng)成是無序的。

遍歷無序的數(shù)據(jù),將遍歷到的元素插入有序序列中適當(dāng)?shù)奈恢?,如遇到相同?shù)據(jù),插在后面。

N的范圍:0~最大索引

3.2 動圖演示

package com.itheima.mysort;


public class A03_InsertDemo {
    public static void main(String[] args) {
        /*
            插入排序:
                將0索引的元素到N索引的元素看做是有序的,把N+1索引的元素到最后一個當(dāng)成是無序的。
                遍歷無序的數(shù)據(jù),將遍歷到的元素插入有序序列中適當(dāng)?shù)奈恢茫缬龅较嗤瑪?shù)據(jù),插在后面。
                N的范圍:0~最大索引

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

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

        //2.遍歷從startIndex開始到最后一個元素,依次得到無序的哪一組數(shù)據(jù)中的每一個元素
        for (int i = startIndex; i < arr.length; i++) {
            //問題:如何把遍歷到的數(shù)據(jù),插入到前面有序的這一組當(dāng)中

            //記錄當(dāng)前要插入數(shù)據(jù)的索引
            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.遍歷數(shù)組
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

4. 快速排序

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

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

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

它是處理大數(shù)據(jù)最快的排序算法之一了。

4.1 算法步驟

  • 從數(shù)列中挑出一個元素,一般都是左邊第一個數(shù)字,稱為 "基準(zhǔn)數(shù)";
  • 創(chuàng)建兩個指針,一個從前往后走,一個從后往前走。
  • 先執(zhí)行后面的指針,找出第一個比基準(zhǔn)數(shù)小的數(shù)字
  • 再執(zhí)行前面的指針,找出第一個比基準(zhǔn)數(shù)大的數(shù)字
  • 交換兩個指針指向的數(shù)字
  • 直到兩個指針相遇
  • 將基準(zhǔn)數(shù)跟指針指向位置的數(shù)字交換位置,稱之為:基準(zhǔn)數(shù)歸位。
  • 第一輪結(jié)束之后,基準(zhǔn)數(shù)左邊的數(shù)字都是比基準(zhǔn)數(shù)小的,基準(zhǔn)數(shù)右邊的數(shù)字都是比基準(zhǔn)數(shù)大的。
  • 把基準(zhǔn)數(shù)左邊看做一個序列,把基準(zhǔn)數(shù)右邊看做一個序列,按照剛剛的規(guī)則遞歸排序

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索引的數(shù)字為基準(zhǔn)數(shù),確定基準(zhǔn)數(shù)在數(shù)組中正確的位置。
           比基準(zhǔn)數(shù)小的全部在左邊,比基準(zhǔn)數(shù)大的全部在右邊。
           后面以此類推。
     */

       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中常見的查找算法與排序算法總結(jié)的詳細(xì)內(nèi)容,更多關(guān)于Java查找 排序算法的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • JAVA內(nèi)存模型(JMM)詳解

    JAVA內(nèi)存模型(JMM)詳解

    這篇文章主要介紹了JAVA內(nèi)存模型(JMM)詳解的相關(guān)資料,需要的朋友可以參考下
    2022-12-12
  • java線程之用Thread類創(chuàng)建線程的方法

    java線程之用Thread類創(chuàng)建線程的方法

    本篇文章介紹了,Thread類創(chuàng)建線程的方法。需要的朋友參考下
    2013-05-05
  • java 進(jìn)制轉(zhuǎn)換實例詳解

    java 進(jìn)制轉(zhuǎn)換實例詳解

    這篇文章主要介紹了java 進(jìn)制轉(zhuǎn)換實例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-04-04
  • 詳解如何解析pom文件方法示例

    詳解如何解析pom文件方法示例

    這篇文章主要為大家介紹了詳解如何解析pom文件方法示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-08-08
  • Eclipse配置Tomcat和JDK步驟圖解

    Eclipse配置Tomcat和JDK步驟圖解

    這篇文章主要內(nèi)容是Eclipse配置Tomcat和JDK步驟圖解,需要的朋友可以參考下
    2015-08-08
  • Spring注解解析之@ImportResource

    Spring注解解析之@ImportResource

    之前我們使用spring,最多的還是通過xml配置文件的方式來配置spring bean等內(nèi)容,隨著注解的廣泛應(yīng)用和spring4中Java config的引入,xml配置文件方式逐步被替換,但是如果是想要使用xml配置文件方式的話,也可以通過@ImportResource注解來實現(xiàn),下面我們來一起看下如何使用.
    2021-05-05
  • SpringCloud Gateway HttpWebHandlerAdapter鏈路調(diào)用請求流程介紹

    SpringCloud Gateway HttpWebHandlerAdapter鏈路調(diào)用請求流程介

    Spring Cloud Gateway旨在為微服務(wù)架構(gòu)提供一種簡單有效的、統(tǒng)一的 API 路由管理方式。Spring Cloud Gateway 作為 Spring Cloud 生態(tài)系中的網(wǎng)關(guān),它不僅提供統(tǒng)一的路由方式,并且基于 Filter 鏈的方式提供了網(wǎng)關(guān)基本的功能,例如:安全、監(jiān)控/埋點和限流等
    2022-10-10
  • java 中Executor, ExecutorService 和 Executors 間的不同

    java 中Executor, ExecutorService 和 Executors 間的不同

    這篇文章主要介紹了java 中Executor, ExecutorService 和 Executors 間的不同的相關(guān)資料,需要的朋友可以參考下
    2017-06-06
  • Java實現(xiàn)在不同線程中運行的代碼實例

    Java實現(xiàn)在不同線程中運行的代碼實例

    這篇文章主要介紹了Java實現(xiàn)在不同線程中運行的代碼,結(jié)合具體實例形式分析了java多線程操作的相關(guān)實現(xiàn)技巧,需要的朋友可以參考下
    2017-04-04
  • 淺析JVM逃逸的原理及分析

    淺析JVM逃逸的原理及分析

    在本篇文章里我們給大家分享了JVM逃逸的原理及分析的相關(guān)知識點內(nèi)容,需要的讀者們可以學(xué)習(xí)下。
    2018-10-10

最新評論