老薛陪你一起過(guò)情人節(jié)诚卸，常見(jiàn)數(shù)組5大排序和4大查找算法實(shí)現(xiàn)

情人節(jié)要啥鮮花葵第，要啥女朋友？老薛陪你過(guò)??

本文內(nèi)容均屬老薛原創(chuàng)合溺，轉(zhuǎn)載請(qǐng)注明出處卒密，http://www.reibang.com/p/4674d67b125c。

今天是情人節(jié)棠赛，老薛也沒(méi)啥可以送給大家哮奇，純手敲了大概20000左右的字膛腐，總共閱讀時(shí)間大概在40分鐘左右，因?yàn)槔锩嬗行┐a可能需要你仔細(xì)思考一下屏镊，所以有點(diǎn)花時(shí)間依疼，如果你還單身，不妨可以花時(shí)間看看而芥，你說(shuō)呢律罢？

主要從復(fù)雜度問(wèn)題展開(kāi)討論我們常見(jiàn)的一些排序和查找算法，如果你對(duì)于排序比較清楚棍丐，推薦直接閱讀查找算法误辑。寫個(gè)小目錄方便大家閱讀。

大O計(jì)數(shù)法
- 什么是大O計(jì)數(shù)法
- 加法法則
- 乘法法則
- 均攤復(fù)雜度
- 常見(jiàn)復(fù)雜度分析
排序算法
- 冒泡排序以及優(yōu)化
- 選擇排序
- 插入排序
- Shell排序
- 快速排序
查找算法
- 順序查找以及優(yōu)化
- 折半查找
- 插值查找
- 斐波那契查找

image

6.1 數(shù)據(jù)結(jié)構(gòu)和算法

6.1.1 問(wèn)題

$\color{red}{ 問(wèn)題1:數(shù)據(jù)結(jié)構(gòu)的作用歌逢？ }$

通過(guò)某些特定的數(shù)據(jù)存儲(chǔ)方式巾钉，存儲(chǔ)數(shù)據(jù)。不同的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)的優(yōu)缺點(diǎn)不同秘案。以便適用于各種復(fù)雜的需求場(chǎng)景砰苍。

$\color{red}{問(wèn)題2:算法的作用}$

在有限的步驟下通過(guò)輸入獲取到一個(gè)或者多個(gè)輸出結(jié)果。(輸入阱高、輸出赚导、有窮、確定赤惊、可行)

$\color{red}{問(wèn)題3:數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系吼旧？}$

數(shù)據(jù)結(jié)構(gòu)為算法提供服務(wù)。算法圍繞數(shù)據(jù)結(jié)構(gòu)操作未舟。

不同的數(shù)據(jù)結(jié)構(gòu)底層存儲(chǔ)方式不同圈暗，不同的存儲(chǔ)方式選擇不同的算法完成程序。

單純的通過(guò)算法要解決一個(gè)問(wèn)題也是不現(xiàn)實(shí)的裕膀，算法是在數(shù)據(jù)結(jié)構(gòu)的前提下建立起來(lái)的员串。

6.1.2 如何評(píng)價(jià)一個(gè)算法是否優(yōu)秀

$\color{green}{時(shí)間復(fù)雜度（Time Complexity）}$ 我們討論的重點(diǎn)

$\color{blue}{空間復(fù)雜度（Space Complexity）}$

固定空間內(nèi)存（基本程序代碼、常數(shù)昼扛、變量）舉例：比如集合迭代時(shí)的代碼

變動(dòng)空間內(nèi)存 隨程序執(zhí)行改變使用空間昵济。比如引用類型變量

$\color{green}{隨著計(jì)算機(jī)硬件發(fā)展，純粹的從程序的效率角度而言還是由運(yùn)行時(shí)間為依據(jù)野揪。}$

6.1.3 大O計(jì)數(shù)法計(jì)算時(shí)間復(fù)雜度

1) 什么是大O計(jì)數(shù)法？(Big O Notation)

其實(shí)我們有很多方式可以可以統(tǒng)計(jì)一個(gè)算法是否夠優(yōu)瞧栗。比如事后統(tǒng)計(jì)發(fā)斯稳，起一個(gè)測(cè)試進(jìn)程，去跑一個(gè)測(cè)試用例迹恐，計(jì)算整個(gè)耗時(shí)挣惰，但是這種方式不在不同的測(cè)試環(huán)境下結(jié)果是不一樣的。所以我們通過(guò)大O計(jì)數(shù)法統(tǒng)計(jì)，比如：

i：T(n) = O(f(n))

這里T(n)表示執(zhí)行時(shí)間

n表示數(shù)據(jù)規(guī)模的大小

f(n)表示每行代碼執(zhí)行的次數(shù)總和憎茂，它是一個(gè)公式

O表示代碼的執(zhí)行時(shí)間T(n)和f(n)是成正比的

2) 大O計(jì)數(shù)法的推導(dǎo)過(guò)程

一行代碼在cpu中的執(zhí)行會(huì)經(jīng)過(guò) $\color{red}{取值->譯碼->執(zhí)行}$ 這幾步珍语，假設(shè)一行代碼的執(zhí)行時(shí)間是一個(gè)Unit_Time,雖然cpu個(gè)數(shù)不同，執(zhí)行時(shí)間不同竖幔，但是我們粗略的認(rèn)為是一致的板乙。接下來(lái)我們編寫測(cè)試用測(cè)試：

i) 測(cè)試用例1

int num1 = 10;
int num2 = 20;
int totle = num1+num2;
System.out.println(totle);

每行代碼的執(zhí)行時(shí)間1Unit_Time,那么總共的執(zhí)行時(shí)間是4Unit_Time。

ii) 測(cè)試用例2

totle = 0;
for(int i = 0;i<100;i++){
    totle += i;
}
System.out.println(totle);

這里第一行代碼的執(zhí)行時(shí)間是1Unit_Time,輸出語(yǔ)句是1Unit_Time拳氢，循環(huán)代碼一共2行募逞，每行執(zhí)行100次，假設(shè)循環(huán)的次數(shù)數(shù)N馋评，那么會(huì)運(yùn)行2N*Unit_Time次放接。然后總共累加(2N+2) * Unit_Time。

$\color{red}{ 所有代碼的執(zhí)行時(shí)間T(n)于每行代碼的執(zhí)行次數(shù)成正比留特。}$

iii) 測(cè)試用例3

System.out.println("執(zhí)行99乘法表打印======");//1??
for(int i = 1;i<=9;i++){
     for(int j = 1;j<=i;j++){
         System.out.print(i+"*"+j+"="+(i*j)+"\t");//2??
     }
     System.out.println();//3??
 }

這里第一行代碼的執(zhí)行時(shí)間是1Unit_Time纠脾，第二行代碼執(zhí)行n^2Unit_Time，第三行代碼執(zhí)行nUnit_Time蜕青。所以這里總共會(huì)執(zhí)行(n ^2+n+1)*Unit_Time苟蹈。所以上述的推導(dǎo)過(guò)程是沒(méi)有問(wèn)題。

$\color{red}{所有代碼的執(zhí)行時(shí)間T(n)于每行代碼的執(zhí)行次數(shù)成正比市咆。}$

6.1.4 大O計(jì)數(shù)法關(guān)注重點(diǎn)

假設(shè)大O計(jì)數(shù)法表示的Tn = 2n^2+1, Tn = n^2+1,Tn=n2汉操。

數(shù)據(jù)規(guī)模

我們發(fā)現(xiàn)當(dāng)數(shù)據(jù)規(guī)模到達(dá)一定規(guī)模的時(shí)候，可以忽略常數(shù)項(xiàng)和指數(shù)項(xiàng)蒙兰。

所以一般情況下我們分析一個(gè)算法的復(fù)雜度問(wèn)題時(shí)磷瘤，優(yōu)先關(guān)注循環(huán)次數(shù)最多的那一段代碼就可以了。

1) 加法法則

i) 測(cè)試用例

static void addFun(int n){
    int totle = 0;
    for(int i = 0;i<100;i++){
        totle+=i;
    }//代碼段1??
    System.out.println(totle);
    totle = 0;
    for(int i = 0;i<n;i++){
        totle+=i;
    }//代碼段2??
    System.out.println(totle);
    totle = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            totle+=(i*j);
        }
    }//代碼段3??
    System.out.println(totle);
}

ii) 大O計(jì)數(shù)法表示

分析

在第一個(gè)代碼段中搜变，因?yàn)檠h(huán)次數(shù)確定采缚，所以是個(gè)常量階，可以忽略挠他。

在第二個(gè)代碼段中扳抽，因?yàn)檠h(huán)次數(shù)和N掛鉤，那么循環(huán)為N

第三個(gè)代碼段中殖侵，是一個(gè)雙層循環(huán)贸呢，循環(huán)耗時(shí)是N^2

整個(gè)代碼段的執(zhí)行就是三個(gè)小代碼段的累加和。那么去掉常量階和指數(shù)階拢军，結(jié)果為N^2

表示

T(n) = O(f(n^2)) 其實(shí)也是我們說(shuō)的時(shí)間復(fù)雜度為n^2楞陷。

$\color{green}{加法法則:總時(shí)間的復(fù)雜度等于數(shù)量級(jí)最大的那段代碼的時(shí)間復(fù)雜度。}$

2) 乘法法法則

i) 測(cè)試用例

static void productFun(int n){
    int totle = 0;
    for (int i = 0;i<n;i++){
        totle += fun(n);//代碼段1??
    }
    System.out.println(totle);
}

static int fun(int n) {//代碼段2??
    int result = 0;
    for (int i = 0;i<n;i++){
        result+=i;
    }
    return result;
}

ii) 大O計(jì)數(shù)法表示

分析

在第一個(gè)代碼段中茉唉，本身的循環(huán)次數(shù)和N掛鉤固蛾，所以它的耗時(shí)是O(n),這里注意這行代碼的執(zhí)行調(diào)用了fun结执。

在第二個(gè)代碼段中，它的耗時(shí)也是O(n)艾凯。

整個(gè)代碼段的其實(shí)是一個(gè)兩層循環(huán)的嵌套献幔，所以是O(n^2)

表示

T(n) = O(f(n^2)) 其實(shí)也是我們說(shuō)的時(shí)間復(fù)雜度為n^2。

$\color{green}{乘法法則:總時(shí)間的復(fù)雜度等于嵌套內(nèi)外代碼的乘積趾诗。}$

3) 平均復(fù)雜度蜡感、均攤時(shí)間復(fù)雜度

i) 測(cè)試用例

static int findByValue(int[] arrs,int value){
    //省略判定步驟
    for(int i = 0;i<arrs.length;i++) {
        if (arrs[i] == value) {
            return i;
        }
    }
    return -1;
}

ii) 大O計(jì)數(shù)法表示

分析

上述這個(gè)代碼，最好的情況下就是第一個(gè)元素就是我們要找的值沧竟，那么此時(shí)它的時(shí)間復(fù)雜度是O(1)铸敏。這個(gè)樣的稱之為 $\color{red}{最好時(shí)間復(fù)雜度}$

上述這個(gè)代碼，最壞的情況下就是沒(méi)有我們要找的元素悟泵，那么此時(shí)它的時(shí)間復(fù)雜度是O(n)杈笔。這個(gè)樣的稱之為 $\color{red}{最壞時(shí)間復(fù)雜度}$

但是上述兩種方式都是極端情況下出現(xiàn)的問(wèn)題，所以我們通過(guò) $\color{red}{平均時(shí)間復(fù)雜度}$ 來(lái)表示上述代碼的時(shí)間復(fù)雜度糕非。

分析 $\color{red}{平均時(shí)間復(fù)雜度}$

$\color{red}{平均時(shí)間復(fù)雜度}$ ：在剛才的數(shù)組中蒙具，元素可能存在的位置是0-(length-1)中和不在數(shù)組中，總共length+1中情況朽肥。

我們將每種情況下查找需要遍歷的個(gè)數(shù)累加起來(lái)除以length+1禁筏，就可以得到需要遍歷元素的平均值。即：

$\frac{1+2+3+...+n+n}{n+1}=\frac{n(n+3)}{2(n+1)}$

我們忽略常數(shù)項(xiàng)衡招、系數(shù)篱昔、低階項(xiàng)，那么結(jié)果

是 $\color{green}{ O(n) }$

分析 $\color{red}{加權(quán)平均時(shí)間復(fù)雜度}$

$\color{red}{加權(quán)平均時(shí)間復(fù)雜度}$ ：在剛才的數(shù)組中始腾，要考慮每個(gè)元素是我們要查找元素的概率也需要加入進(jìn)去州刽。第一個(gè)位置存在的概率等于

$\frac{1}{2}*\frac{1}{(n)}=\frac{1}{2n}$

PS：二分之一代表是否可以找到第一個(gè)元素是查找的元素，N分之一說(shuō)的是每個(gè)元元素可能的概率浪箭。

我們將每種情況下每個(gè)值出現(xiàn)的概率也統(tǒng)計(jì)進(jìn)去穗椅，則結(jié)果為：

$1*\frac{1}{2n}+2*\frac{1}{2n}+3*\frac{1}{2n}+....n*\frac{1}{2n}=\frac{1+n}{4}$

我們忽略常數(shù)項(xiàng)、系數(shù)奶栖、低階項(xiàng)匹表，那么結(jié)果

是 $\color{green}{ O(n) }$

4) 常見(jiàn)復(fù)雜度問(wèn)題

i) ：常見(jiàn)復(fù)雜度

復(fù)雜度分析

ii) ：數(shù)據(jù)規(guī)模和耗時(shí)圖

圖片 1

6.2 常見(jiàn)排序算法

6.2.1 冒泡排序

冒泡排序

兩兩相鄰的元素互相比較，一直比較到最后一個(gè)數(shù)宣鄙，這樣一趟下來(lái)袍镀，最后一個(gè)數(shù)要么是最大數(shù)，要么是最小數(shù)冻晤。正好比較的是數(shù)組的元素個(gè)數(shù)-1次流椒。

持續(xù)第二次在進(jìn)行兩兩元素比較，將倒數(shù)第二大或者倒數(shù)第二小的數(shù)放到倒數(shù)第二個(gè)位置明也。

持續(xù)以上的步驟宣虾，直到整個(gè)數(shù)組排完序。

1）測(cè)試用例

/**
 * 對(duì)于數(shù)組進(jìn)行冒泡排序
 * @param arrs 需要排序的數(shù)組
 */
public static void bubbleSort(int[] arrs) {
    for(int i = 0;i<arrs.length;i++){
        System.out.println("第"+(i+1)+"趟");
        for (int j = 0;j<arrs.length-1;j++){
            System.out.println("第"+(j+1)+"次");
            //判定是否需要交換位置
            if(arrs[j]>arrs[j+1]){
                int temp = arrs[j];
                arrs[j] = arrs[j+1];
                arrs[j+1] = temp;
            }
            System.out.println(Arrays.toString(arrs));
        }
    }
}

2）測(cè)試用例

//給指定的數(shù)組進(jìn)行排序温数，默認(rèn)升序
MyArrays.bubbleSort(arrs);
System.out.println("數(shù)組排序完成之后元素："+Arrays.toString(arrs));

3）結(jié)論

初始化長(zhǎng)度為10的數(shù)組的元素是：
[37, 64, 88, 32, 81]
第1趟
第1次
[37, 64, 88, 32, 81]
第2次
[37, 64, 88, 32, 81]
第3次
[37, 64, 32, 88, 81]
第4次
[37, 64, 32, 81, 88]
绣硝。。撑刺。
第5趟
第1次
[32, 37, 64, 81, 88]
第2次
[32, 37, 64, 81, 88]
第3次
[32, 37, 64, 81, 88]
第4次
[32, 37, 64, 81, 88]

4）冒泡排序優(yōu)化

優(yōu)化從兩個(gè)方向展開(kāi)鹉胖，一個(gè)是每次循環(huán)的次數(shù)，一個(gè)是循環(huán)多少趟够傍。循環(huán)的次數(shù)降低是因?yàn)槊看味紩?huì)有一個(gè)最大數(shù)或者最小數(shù)已經(jīng)被排好序了甫菠。在某些情況下，有些數(shù)字可能經(jīng)過(guò)2-3趟可能就排好序了冕屯，此時(shí)我們就可以減少趟數(shù)即可寂诱。

i）測(cè)試用例

/**
 * 對(duì)于數(shù)組進(jìn)行冒泡排序
 * @param arrs 需要排序的數(shù)組
 */
public static void bubbleSort(int[] arrs) {
    for(int i = 0;i<arrs.length;i++){
        System.out.println("第"+(i+1)+"趟");
        //定義變量查看是否排好序
        boolean flag = false;
        for (int j = 0;j<arrs.length-1-i;j++){
            //判定是否需要交換位置
            if(arrs[j]>arrs[j+1]){
                int temp = arrs[j];
                arrs[j] = arrs[j+1];
                arrs[j+1] = temp;
                flag = true;
            }
            System.out.println(Arrays.toString(arrs));
        }

        //判定是否排好序
        if(!flag){
            return ;//確定排好序了
        }
    }
}

ii）測(cè)試用例

MyArrays.bubbleSort(arrs);
System.out.println("數(shù)組排序完成之后元素："+Arrays.toString(arrs));

iii）結(jié)論

初始化長(zhǎng)度為10的數(shù)組的元素是：
[54, 43, 71, 79, 76]
第1趟
[43, 54, 71, 79, 76]
[43, 54, 71, 79, 76]
[43, 54, 71, 79, 76]
[43, 54, 71, 76, 79]
第2趟
[43, 54, 71, 76, 79]
[43, 54, 71, 76, 79]
[43, 54, 71, 76, 79]
數(shù)組排序完成之后元素：[43, 54, 71, 76, 79]

6.2.2 選擇排序

1) 原理分析

用第一個(gè)元素一次和所有元素進(jìn)行比較，如果存在比它小的元素安聘，則記錄位置痰洒。

整個(gè)比較完成則會(huì)記錄下最小的元素的位置，然后進(jìn)行位置互換浴韭。

總共比較length-1次丘喻，每一次都會(huì)確定一個(gè)最小的元素，以此類推

2) 圖形展示

選擇

3) 代碼實(shí)現(xiàn)

public static void selectedSort(int[] arrs){
    //省略參數(shù)判定
    for(int i = 0;i<arrs.length-1;i++){
        int index = i;//假設(shè)目前最小的數(shù)的索引是i
        for(int j = i+1;j<arrs.length;j++){
            if(arrs[i]>arrs[j]){
                index = j;
            }
        }
        if(index!=i){
            int temp = arrs[i];
            arrs[i] = arrs[index];
            arrs[index] = temp;
        }
    }
}

6.2.3 插入排序

1) 原理分析

將數(shù)組分成兩部分念颈，一部分是已經(jīng)排好序了泉粉，一部分未排序。

假設(shè)已排序的數(shù)組中包含的是數(shù)組中的第一個(gè)位置上的元素榴芳，即索引是0嗡靡。

依次獲取1-剩余索引位置的元素，獲取到到這些元素就是未排序的

判定當(dāng)前拿到的元素和已排序的數(shù)組的元素大小翠语，如果小于

將元素向后移動(dòng)一個(gè)位置

直到比較判定失敗叽躯，將當(dāng)前需要插入的元素的值，插入到指定的位置上肌括。

2) 圖形展示

插入

3) 代碼實(shí)現(xiàn)

public static void insertionSort(int[] arrs){
    //省略參數(shù)判定
    for(int i = 1;i<arrs.length;i++){
        //記錄當(dāng)前元素的值
        int current_value = arrs[i];
        //記錄要插入元素的位置
        int pre_index = i-1;
        //循環(huán)判定要插入的位置
        while(pre_index>=0&&arrs[pre_index]>current_value){
            arrs[pre_index+1] = arrs[pre_index];
            pre_index--;
        }
        arrs[pre_index+1] = current_value;
    }
}

6.2.4 Shell排序

1) 原理分析

對(duì)于插入排序而言点骑，如果數(shù)據(jù)本身越有序，那么越高效谍夭。

對(duì)于數(shù)組進(jìn)行分序列黑滴，假設(shè)分成length/2個(gè)序列，對(duì)于第0個(gè)元素紧索，那就和第length/2索引位置是上的元素是一個(gè)序列袁辈，通過(guò)插入排序比較

那么第一次排序完成之后，對(duì)于元素組進(jìn)行分序列珠漂，每次為length/2/2晚缩。直到分成一個(gè)序列為止尾膊。

內(nèi)部不斷通過(guò)插入排序比較，這樣隨著分成的序列越來(lái)越少荞彼，也就意味著數(shù)組本身原來(lái)越有序冈敛，插入排序的效率越來(lái)越高。

2) 圖形展示

shell

3) 代碼實(shí)現(xiàn)

public static void shellSort(int[] arrs){
    //省略參數(shù)判定
    //設(shè)置序列
    int group = arrs.length/2;
    for(;group>0;group/=2){
        // 通過(guò)插入排序 比較兩個(gè)值 比較序列中的前后值
        //記錄當(dāng)前元素的值
        for(int i = group;i<arrs.length;i++){
            //記錄當(dāng)前元素的值
            int current_value = arrs[i];
            //記錄要插入元素的位置
            int pre_index = i-group;
            //循環(huán)判定要插入的位置
            while(pre_index>=0&&arrs[pre_index]>current_value){
                arrs[pre_index+group] = arrs[pre_index];
                pre_index-= group;
            }
            arrs[pre_index+group] = current_value;
        }
    }
}

這里注意鸣皂，我們也可以自定義序列抓谴，只需要在外部聲明即可。

6.2.5 快速排序

1) 原理分析

對(duì)于快速排序來(lái)講寞缝，它是一個(gè)分而治之的思想癌压。

開(kāi)始存在三個(gè)值，一個(gè)是基準(zhǔn)值base荆陆，一個(gè)是最左側(cè)的游標(biāo)L和最右側(cè)的游標(biāo)R滩届。

基準(zhǔn)值可以隨意設(shè)置，然后移動(dòng)L游標(biāo)慎宾，向左移動(dòng)丐吓，保證base的左側(cè)一定是比base小的數(shù)。

反之base的右側(cè)一定是比base大的數(shù)趟据。然后找到之后就將L和R這兩個(gè)游標(biāo)位置的值進(jìn)行互換券犁，然后繼續(xù)移動(dòng)游標(biāo)，知道出現(xiàn)兩個(gè)游標(biāo)相等或者交叉的情況汹碱。

對(duì)于左右兩側(cè)分別再繼續(xù)進(jìn)行快速排序即可粘衬。

2) 圖形展示

快速

3) 代碼實(shí)現(xiàn)

static void quickSort(int[]arr, int left, int right) {
    //聲明存放左側(cè)和右側(cè)以及基準(zhǔn)的值
    int R = right;
    int L = left;
    int base = arr[(left+right) / 2];
    //循環(huán)判定
    while(L<R){
        while(arr[L]<base){ L++;}
        while(arr[R]>base){ R--;}
        if(L<=R){
            //交換位置
            int temp = arr[L];
            arr[L] = arr[R];
            arr[R] = temp;
            //繼續(xù)往下走
            L++;
            R--;
        }
    }
    //準(zhǔn)備遞歸調(diào)用
    if(left<R){
        quickSort(arr,left,R);
    }
    if(L>right){
        quickSort(arr,L,right);
    }
}

6.2.6 不同排序方式的效率統(tǒng)計(jì)

效率統(tǒng)計(jì)

6.3 查找算法

查找算法是我們經(jīng)常會(huì)使用到的一種算法，比如我們知道的各個(gè)電商平臺(tái)中的站內(nèi)搜索咳促、搜索引擎中的搜索業(yè)務(wù)等等都是查找的一種體現(xiàn)稚新。顯式生活中我們也經(jīng)常能夠碰到這樣的場(chǎng)景，比如在很多書(shū)中找到一本自己想要看的跪腹，一般情況下我們都會(huì)將所有圖書(shū)按照順序排列褂删，然后從頭至尾開(kāi)始查找，直到找到位置冲茸，又或者我們會(huì)將各個(gè)類目的圖書(shū)分類然后在查找屯阀，都是在不同場(chǎng)景下我們會(huì)做的查找。

image

6.3.1 順序查找

1) 原理分析

順序查找是最基本的查找算法轴术，就是從頭至尾開(kāi)始進(jìn)行查找难衰，如果找到了就不在繼續(xù)查找，如果沒(méi)有找到則返回一個(gè)標(biāo)識(shí)逗栽，結(jié)束查找盖袭。也稱之為線性查找或者是靜態(tài)查找表。

2) 圖形展示

順序查找

3）代碼展示

/**
 * 通過(guò)順序查找數(shù)組中的指定元素
 * @param arrs 需要查找的數(shù)組
 * @param key 需要查找的元素
 * @return 返回是否找到的元素的索引 如果沒(méi)有找到返回-1
 */
public static int orderSearch01(int[] arrs,int key){
    //省略對(duì)于數(shù)組進(jìn)行判定
    int len = arrs.length;
    for(int i = 0;i<len;i++){
        if(arrs[i]==key){
            return i;
        }
    }
    return -1;
}

4) 優(yōu)缺點(diǎn)分析

如果運(yùn)氣比較好，則第一個(gè)元素就是需要查找的元素鳄虱，如果運(yùn)氣不好則最后一個(gè)才是想要查找的元素弟塞。根據(jù)我們之前學(xué)習(xí)的復(fù)雜度分析，這里的時(shí)間復(fù)雜度為 $\color{red}{O(n)}$ 拙已。如果數(shù)組很長(zhǎng)的時(shí)候宣肚，其實(shí)這樣的查找效率是很低的。

6.3.2 優(yōu)化順序查找

1) 原理分析

假設(shè)查找數(shù)組的頭或者是尾元素是需要查找的元素悠栓，然后我們從頭或者尾開(kāi)始進(jìn)行判定是否是需要查找的元素，如果頭或者尾元素是要查找的元素按价，則證明沒(méi)有找到惭适，除了頭或尾元素之外的其他元素是查找的元素，則證明找到了楼镐，但是注意為了防止查找的數(shù)組中的元素出現(xiàn)問(wèn)題癞志，我們需要在其中重新復(fù)制數(shù)組。

2) 圖形展示

順序查找優(yōu)化

3）代碼展示

/**
* 通過(guò)優(yōu)化框产，首先將數(shù)組中的最后一個(gè)元素空出來(lái)凄杯，存放哨兵，保證數(shù)組元素不變秉宿。
* @param arrs 查找的數(shù)組
* @param key 查找的元素
* @return 如果返回的是arrs長(zhǎng)度的索引戒突，則證明沒(méi)有找到，反之則找到了
*/
private static int orderSearch02(int[] arrs,int key){
    //省略對(duì)于數(shù)組進(jìn)行判定
    //首先復(fù)制一份數(shù)組描睦，第0個(gè)位置上存放的是key的值
    int[] newArrs = Arrays.copyOf(arrs,arrs.length+1);

    //設(shè)置最后一個(gè)元素的值是哨兵
    newArrs[newArrs.length-1] = key;

    //聲明變量從第0個(gè)元素開(kāi)始查找
    int index = 0;

    //開(kāi)始查找
    while(newArrs[index]!= key){
        index++;
    }
    return index;
}

4) 優(yōu)缺點(diǎn)分析

不需要和第一次順序查找一樣膊存，每次比較完成之后都有判定索引問(wèn)題，如果總數(shù)據(jù)比較多時(shí)忱叭，其實(shí)設(shè)置哨兵的方式會(huì)在效率上提高很多隔崎，大家有興趣可以測(cè)試一下在1億條數(shù)據(jù)的數(shù)組中通過(guò)兩種方式的時(shí)間進(jìn)行比較，優(yōu)化后的代碼速度大概能夠提高20%-40%左右韵丑。

6.3.3 折半查找

$\color{green}{PS：注意使用折半查找時(shí)一定要保證數(shù)組中的元素是有序的爵卒，不然無(wú)法保證查詢結(jié)果是否正確，折半查找也稱之為二分查找.}$

1) 原理分析

在數(shù)組中的元素是有序的情況下撵彻，假設(shè)數(shù)組中的元素是從小到大排序的钓株。那么首元素索引假設(shè)為low，尾元素為high千康，我們?nèi)フ麄€(gè)數(shù)組索引中的中間值假設(shè)索引為mid和需要查找的元素進(jìn)行對(duì)比享幽，如果比查找元素大，則證明在mid的索引的右側(cè)拾弃，反之是左側(cè)值桩。根據(jù)不同的位置，移動(dòng)low和high豪椿，不斷計(jì)算mid奔坟，最后能夠查找的mid就是要查找的元素的索引或者就是沒(méi)有找到

2) 圖形展示

二分查找

3）代碼展示

/**
* 聽(tīng)過(guò)二分查找法查找數(shù)組的元素
* @param arrs 查找的數(shù)組
* @param key 查找的元素
* @return 返回元素的索引
*/
public static int binerySearch(int[] arrs,int key){
    //省略對(duì)于數(shù)組的判定
    int low = 0;//最小索引
    int high = arrs.length-1;//最大索引
    int mid ;//中間索引
    while(low<=high) {//最小索引小于最大索引則繼續(xù)查找
        //計(jì)算中間索引
        mid = (low + high) / 2;
        //判定元素在中間索引的那一側(cè)
        if (arrs[mid] > key) {//中間值大于查找的元素 在左側(cè)
            //改變最大索引
            high = mid - 1;
        } else if (arrs[mid] < key) {//中間值小于查找的元素 在左側(cè)
            //改變最小索引
            low = mid + 1;
        } else {//中間值等于查找的元素 返回
            return mid;
        }
    }
    return -1;//證明沒(méi)有找到
}

4) 優(yōu)缺點(diǎn)分析

該算法比較容易理解携栋，并且效率較高。因?yàn)槊看味际侨サ粢话霐?shù)據(jù)進(jìn)行查找咳秉，它的時(shí)間復(fù)雜度為0(logn).但是前提必須要保證數(shù)組中數(shù)據(jù)已經(jīng)是有序的婉支。如果該集合中頻繁的插入或者是刪除數(shù)據(jù)，那么維護(hù)有序的集合是一件很麻煩的事情澜建，就不建議使用了向挖。

PS:附兩張圖更好的理解折半查找和順序查找的對(duì)比。

image

6.3.4 插值查找

1) 原理分析

我們?cè)谕ㄟ^(guò)二分查找法進(jìn)行元素查找時(shí)炕舵，發(fā)現(xiàn)問(wèn)題何之，為什么每次要折一半呢？比如在一個(gè)分部均勻的數(shù)組中咽筋，<span style="color:green">arrs={1,16,22,34,45,57,68,73,86,97}</span>中查找元素<span style="color:red">16</span>,通過(guò)二分查找法要找4次才能找到溶推，有沒(méi)有好一點(diǎn)的方法，可以讓我們通過(guò)更少的次數(shù)找到元素呢奸攻？

這里我們只需要將mid的取值改為以下方式即可蒜危。

原來(lái)計(jì)算mid的方式
$mid=\frac{low+high}{2}=low+\frac{1}{2}(high-low)$
通過(guò)算法科學(xué)家將1/2進(jìn)行改進(jìn)得到以下的公式
$mid=low+\frac{key-arrs[low]}{arrs[high]-arrs[low]}(high-low)$

只需要在原來(lái)計(jì)算mid的時(shí)，替換該公式即可增加當(dāng)集合中的數(shù)據(jù)均勻分布時(shí)提高效率睹耐。

2）代碼展示

/**
 * 通過(guò)插值查找法查找數(shù)組的元素
 * @param arrs 查找的數(shù)組
 * @param key 查找的元素
 * @return 返回元素的索引
 */
public static int nterpolationQuery(int[] arrs,int key){
    //省略對(duì)于數(shù)組的判定
    int low = 0;//最小索引
    int high = arrs.length-1;//最大索引
    int mid ;//中間索引
    while(low<=high) {//最小索引小于最大索引則繼續(xù)查找
        //計(jì)算中間索引
        mid = low+(high-low)*(key-arrs[low])/(arrs[high]-arrs[low]);
        //判定元素在中間索引的那一側(cè)
        if (arrs[mid] > key) {//中間值大于查找的元素 在左側(cè)
            //改變最大索引
            high = mid - 1;
        } else if (arrs[mid] < key) {//中間值小于查找的元素 在左側(cè)
            //改變最小索引
            low = mid + 1;
        } else {//中間值等于查找的元素 返回
            return mid;
        }
    }
    return -1;//證明沒(méi)有找到
}

3) 優(yōu)缺點(diǎn)分析

該算法的時(shí)間復(fù)雜度也是O(logn),但是如果查找的集合很大辐赞，而且關(guān)鍵詞的分部很平均的話那么插值查找的算法要優(yōu)于折半算法，但是如果集合中分部的數(shù)據(jù)不是很均勻疏橄，或者很極端占拍，那么未必就適合使用插值算法。

6.3.5 斐波那契查找

推薦大家可以先看看百度百科對(duì)于斐波那契查找的說(shuō)明捎迫。

在介紹斐波那契查找算法之前晃酒，先介紹一下很它緊密相連的一個(gè)概念——黃金分割。黃金比例又稱黃金分割窄绒，是指事物各部分間一定的數(shù)學(xué)比例關(guān)系贝次，即將整體一分為二，較大部分與較小部分之比等于整體與較大部分之比彰导，其比值約為1:0.618或1.618:1蛔翅。0.618被公認(rèn)為最具有審美意義的比例數(shù)字，這個(gè)數(shù)值的作用不僅僅體現(xiàn)在諸如繪畫(huà)位谋、雕塑山析、音樂(lè)、建筑等藝術(shù)領(lǐng)域掏父，而且在管理笋轨、工程設(shè)計(jì)等方面也有著不可忽視的作用。因此被稱為黃金分割。斐波那契數(shù)列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（從第三個(gè)數(shù)開(kāi)始爵政，后邊每一個(gè)數(shù)都是前兩個(gè)數(shù)的和）仅讽。然后我們會(huì)發(fā)現(xiàn)，隨著斐波那契數(shù)列的遞增钾挟，前后兩個(gè)數(shù)的比值會(huì)越來(lái)越接近0.618洁灵，利用這個(gè)特性，我們就可以將黃金比例運(yùn)用到查找技術(shù)中掺出。

1) 原理分析

斐波那契查找其實(shí)和二分查找和插值查找是類似的徽千，只不過(guò)對(duì)于mid的取值不同。

斐波那契查找
low和high為最大和最小索引汤锨。
我們通過(guò)斐波那契 $\color{green}{F[k]=F[k-1]+F[k-2]}$ 罐栈。可以推導(dǎo)出 $\color{green}{(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1}$ 泥畅。
我們只要要查找的順序表的長(zhǎng)度為 $\color{green}{F[k]-1}$ ,就可以將整個(gè)表分為F[k-1]-1和F[k-2]-1著兩段，那么mid的位置就是low+F[k-1]-1琅翻。
然后只需要比較mid的值和key值的大形蝗省：
- 如果相等證明找到了
- 如果大于 mid>key 那么在F[k-1]-1這個(gè)位置，改變high的值方椎，然后mid取值還是low+F[k-1]-1聂抢，所以接下來(lái)要查找的順序表為F[k-1]-1,將整個(gè)順序表F[k-1]-1看成一個(gè)順序表，改變k的值棠众，讓F[k-1]-1等于F[k]-1,及k=k-1琳疏；
- 如果小于 mid<key 那么在F[k-2]-1這個(gè)順序表中，改變low的值闸拿，然后mid取值還是low+F[k-1]-1空盼，所以接下來(lái)要查找的順序表為F[k-2]-1,所以將整個(gè)順序表F[k-2]-1看成一個(gè)要查找的順序表，改變k的值新荤，及k=k-2揽趾。
$\color{red}{注意：這里有兩個(gè)問(wèn)題需要解決：}$

①：為什么整個(gè)表要看成是F[k]-1,而不是F[k]，由于剛剛我們的推導(dǎo)過(guò)程是可以推導(dǎo)出來(lái)一個(gè) $\color{red}{(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1}$ 這個(gè)公式的苛骨，在這個(gè)公式里我們發(fā)現(xiàn)篱瞎，拋開(kāi)兩個(gè)順序表之外，還需要一個(gè)mid的值痒芝，如果直接使用F[k],那么后續(xù)要不斷求得mid值而移動(dòng)數(shù)組的元素俐筋。所以一般情況下我們說(shuō) $\color{blue}{要求開(kāi)始表中記錄的個(gè)數(shù)為某個(gè)斐波那契數(shù)小1，及n=F(k)-1}$ 严衬。

②：不是所有情況下順序表中的數(shù)據(jù)都是比某個(gè)斐波那契數(shù)小1的澄者，此時(shí)我們需要對(duì)于原數(shù)組進(jìn)行擴(kuò)容，擴(kuò)展為等于或者是大于即可。

③：對(duì)于原數(shù)組中的數(shù)據(jù)闷哆，如果長(zhǎng)度小于斐波那契數(shù)腰奋，擴(kuò)容之后將超過(guò)的索引上的元素，填充最后一個(gè)元素抱怔。

之所以可以這樣進(jìn)行查找就是由于我們發(fā)現(xiàn)對(duì)于斐波那契數(shù)列而言劣坊，相鄰兩個(gè)數(shù)的比值不斷趨向于黃金分割比例，那么我們讓mid的取值位置靠近通過(guò)mid分割的兩段的比值為黃金分割比例屈留。而確定的方式就是兩段的數(shù)據(jù)個(gè)數(shù)和斐波那契中相鄰的兩個(gè)數(shù)相等局冰，求比值。

3）代碼展示

 //計(jì)算斐波那契數(shù)列
public static int fib(int n){
    if(n==1||n==2){
        return 1;
    }
    return fib(n-1)+fib(n-2);
}
/**
     * 通過(guò)斐波那契查找法查找需要計(jì)算的值
     * @param arrs
     * @param key
     * @return
     */
public static int fibSearch(int[] arrs,int key){
    //省略數(shù)組判定
    int low = 0;//最小索引
    int high = arrs.length-1;//最大索引
    int mid ;//中間索引

    //獲取k的值 使得查找的數(shù)組的長(zhǎng)度正好小于或者等于F(k)-1
    int k = 1;
    while(arrs.length>fib(k)-1){
        k++;
    }

    //重新聲明一個(gè)新的數(shù)組灌危，然后超過(guò)的長(zhǎng)度通過(guò)最大值填充
    int[] temp = new int[fib(k)];
    //復(fù)制原來(lái)數(shù)據(jù)
    System.arraycopy(arrs,0,temp,0,arrs.length);
    //對(duì)于超過(guò)的數(shù)據(jù)填充最大值
    for(int i = arrs.length;i<=temp.length-1;i++){
        temp[i] = temp[arrs.length-1];
    }

    //判定在中間值
    while(low<=high){
        mid = low+fib(k-1)-1;
        if(temp[mid]>key){
            high = mid - 1; //high向右移動(dòng)
            k = k-1;//對(duì)應(yīng)上圖中的左端 長(zhǎng)度為F[k-1]-1
        }else if(temp[mid]<key) {
            low=mid+1;//low向左移動(dòng)
            k=k-2;  //對(duì)應(yīng)上圖中的右端康二，長(zhǎng)度F[k-2]-1
        }else {
            if(mid<=arrs.length)
                return mid;
            else
              //當(dāng)mid位于新增的數(shù)組中時(shí)，證明要查找的數(shù)是最后一個(gè)位置上的
                return arrs.length;     
        }
    }
    return -1;
}

4) 優(yōu)缺點(diǎn)分析

該算法的時(shí)間復(fù)雜度也是O(logn),但是就平均性能來(lái)說(shuō)勇蝙，斐波那契查找要優(yōu)于折半查找沫勿，但是如果要查找的元素的一直處于整個(gè)順序表的最左側(cè)，也就意味著每次都要在長(zhǎng)半?yún)^(qū)進(jìn)行查找味混，此時(shí)效率就低于折半产雹。

折半、插值翁锡、斐波那契其實(shí)都是將原本很大的有序順序表拆分成2部分蔓挖，進(jìn)行遞歸查找，不過(guò)選擇的中間點(diǎn)mid不同馆衔。各有優(yōu)劣瘟判。

參考網(wǎng)站：
https://www.cnblogs.com/onepixel/articles/7674659.html
參考書(shū)籍：
大話數(shù)據(jù)結(jié)構(gòu)，Java算法手冊(cè)

最后編輯于：2019.02.14 18:02:33

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末角溃，一起剝皮案震驚了整個(gè)濱河市拷获，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌减细，老刑警劉巖刀诬，帶你破解...
沈念sama閱讀 218,941評(píng)論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異邪财，居然都是意外死亡陕壹，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,397評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門树埠，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)糠馆，“玉大人，你說(shuō)我怎么就攤上這事怎憋∮致担” “怎么了九昧？”我有些...
開(kāi)封第一講書(shū)人閱讀 165,345評(píng)論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)毕匀。經(jīng)常有香客問(wèn)我铸鹰，道長(zhǎng)，這世上最難降的妖魔是什么皂岔？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,851評(píng)論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任蹋笼，我火速辦了婚禮，結(jié)果婚禮上躁垛，老公的妹妹穿的比我還像新娘剖毯。我一直安慰自己，他們只是感情好教馆，可當(dāng)我...
茶點(diǎn)故事閱讀 67,868評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布逊谋。她就那樣靜靜地躺著，像睡著了一般土铺。火紅的嫁衣襯著肌膚如雪胶滋。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書(shū)人閱讀 51,688評(píng)論 1贊 305
城市分裂傳說(shuō)
那天悲敷，我揣著相機(jī)與錄音镀钓，去河邊找鬼。笑死镀迂，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的唤蔗。我是一名探鬼主播探遵，決...
沈念sama閱讀 40,414評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼妓柜！你這毒婦竟也來(lái)了箱季？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書(shū)人閱讀 39,319評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤棍掐，失蹤者是張志新（化名）和其女友劉穎藏雏，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體作煌，經(jīng)...
沈念sama閱讀 45,775評(píng)論 1贊 315
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡掘殴，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,945評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了粟誓。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片奏寨。...
茶點(diǎn)故事閱讀 40,096評(píng)論 1贊 350
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖鹰服，靈堂內(nèi)的尸體忽然破棺而出病瞳，到底是詐尸還是另有隱情揽咕，我是刑警寧澤，帶...
沈念sama閱讀 35,789評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布套菜，位于F島的核電站亲善，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏逗柴。R本人自食惡果不足惜蛹头，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,437評(píng)論 3贊 331
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望嚎于。院中可真熱鬧掘而，春花似錦、人聲如沸于购。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,993評(píng)論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)肋僧。三九已至斑胜，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間嫌吠，已是汗流浹背止潘。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 33,107評(píng)論 1贊 271
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留辫诅，地道東北人凭戴。一個(gè)月前我還...
沈念sama閱讀 48,308評(píng)論 3贊 372
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像炕矮，于是被迫代替她去往敵國(guó)和親么夫。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,037評(píng)論 2贊 355

老薛陪你一起過(guò)情人節(jié)诚卸，常見(jiàn)數(shù)組5大排序和4大查找算法實(shí)現(xiàn)

情人節(jié)要啥鮮花葵第，要啥女朋友？老薛陪你過(guò)??

6.1 數(shù)據(jù)結(jié)構(gòu)和算法

6.1.1 問(wèn)題

6.1.2 如何評(píng)價(jià)一個(gè)算法是否優(yōu)秀

6.1.3 大O計(jì)數(shù)法計(jì)算時(shí)間復(fù)雜度

1) 什么是大O計(jì)數(shù)法？(Big O Notation)

2) 大O計(jì)數(shù)法的推導(dǎo)過(guò)程

i) 測(cè)試用例1

ii) 測(cè)試用例2

iii) 測(cè)試用例3

6.1.4 大O計(jì)數(shù)法關(guān)注重點(diǎn)

1) 加法法則

i) 測(cè)試用例

ii) 大O計(jì)數(shù)法表示

2) 乘法法法則

i) 測(cè)試用例

ii) 大O計(jì)數(shù)法表示

3) 平均復(fù)雜度蜡感、均攤時(shí)間復(fù)雜度

i) 測(cè)試用例

ii) 大O計(jì)數(shù)法表示

4) 常見(jiàn)復(fù)雜度問(wèn)題

i) ：常見(jiàn)復(fù)雜度

ii) ：數(shù)據(jù)規(guī)模和耗時(shí)圖

6.2 常見(jiàn)排序算法

6.2.1 冒泡排序

1） 測(cè)試用例

2） 測(cè)試用例

3） 結(jié)論

4） 冒泡排序優(yōu)化

i） 測(cè)試用例

ii） 測(cè)試用例

iii） 結(jié)論

6.2.2 選擇排序

1) 原理分析

2) 圖形展示

3) 代碼實(shí)現(xiàn)

6.2.3 插入排序

1) 原理分析

2) 圖形展示

3) 代碼實(shí)現(xiàn)

6.2.4 Shell排序

1) 原理分析

2) 圖形展示

3) 代碼實(shí)現(xiàn)

6.2.5 快速排序

1) 原理分析

2) 圖形展示

3) 代碼實(shí)現(xiàn)

6.2.6 不同排序方式的效率統(tǒng)計(jì)

6.3 查找算法

6.3.1 順序查找

1) 原理分析

2) 圖形展示

3）代碼展示

4) 優(yōu)缺點(diǎn)分析

6.3.2 優(yōu)化順序查找

1) 原理分析

2) 圖形展示

3）代碼展示

4) 優(yōu)缺點(diǎn)分析

6.3.3 折半查找

1) 原理分析

2) 圖形展示

3）代碼展示

4) 優(yōu)缺點(diǎn)分析

6.3.4 插值查找

1) 原理分析

2）代碼展示

3) 優(yōu)缺點(diǎn)分析

6.3.5 斐波那契查找

1) 原理分析

3）代碼展示

4) 優(yōu)缺點(diǎn)分析

1）測(cè)試用例

2）測(cè)試用例

3）結(jié)論

4）冒泡排序優(yōu)化

i）測(cè)試用例

ii）測(cè)試用例

iii）結(jié)論