老薛陪你一起过情人节，常见数组5大排序和4大查找算法实现

作者: 坑王老薛 | 来源:发表于2019-02-14 17:57 被阅读88次

情人节要啥鲜花，要啥女朋友？老薛陪你过😋

本文内容均属老薛原创，转载请注明出处，https://www.jianshu.com/p/4674d67b125c。

今天是情人节，老薛也没啥可以送给大家，纯手敲了大概20000左右的字，总共阅读时间大概在40分钟左右，因为里面有些代码可能需要你仔细思考一下，所以有点花时间，如果你还单身，不妨可以花时间看看，你说呢？

主要从复杂度问题展开讨论我们常见的一些排序和查找算法，如果你对于排序比较清楚，推荐直接阅读查找算法。写个小目录方便大家阅读。

大O计数法
- 什么是大O计数法
- 加法法则
- 乘法法则
- 均摊复杂度
- 常见复杂度分析
排序算法
- 冒泡排序以及优化
- 选择排序
- 插入排序
- Shell排序
- 快速排序
查找算法
- 顺序查找以及优化
- 折半查找
- 插值查找
- 斐波那契查找

image

6.1 数据结构和算法

6.1.1 问题

$\color{red}{ 问题1:数据结构的作用？ }$

通过某些特定的数据存储方式，存储数据。不同的数据结构存储数据的优缺点不同。以便适用于各种复杂的需求场景。

$\color{red}{问题2:算法的作用}$

在有限的步骤下通过输入获取到一个或者多个输出结果。(输入、输出、有穷、确定、可行)

$\color{red}{问题3:数据结构和算法的关系？}$

数据结构为算法提供服务。算法围绕数据结构操作。

不同的数据结构底层存储方式不同，不同的存储方式选择不同的算法完成程序。

单纯的通过算法要解决一个问题也是不现实的，算法是在数据结构的前提下建立起来的。

6.1.2 如何评价一个算法是否优秀

$\color{green}{时间复杂度（Time Complexity）}$ 我们讨论的重点

$\color{blue}{空间复杂度（Space Complexity）}$

固定空间内存（基本程序代码、常数、变量）举例：比如集合迭代时的代码

变动空间内存 随程序执行改变使用空间。比如引用类型变量

$\color{green}{随着计算机硬件发展，纯粹的从程序的效率角度而言还是由运行时间为依据。}$

6.1.3 大O计数法计算时间复杂度

1) 什么是大O计数法？(Big O Notation)

其实我们有很多方式可以可以统计一个算法是否够优。比如事后统计发，起一个测试进程，去跑一个测试用例，计算整个耗时，但是这种方式不在不同的测试环境下结果是不一样的。所以我们通过大O计数法统计，比如：

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

这里T(n)表示执行时间

n表示数据规模的大小

f(n)表示每行代码执行的次数总和，它是一个公式

O表示代码的执行时间T(n)和f(n)是成正比的

2) 大O计数法的推导过程

一行代码在cpu中的执行会经过 $\color{red}{取值->译码->执行}$ 这几步，假设一行代码的执行时间是一个Unit_Time,虽然cpu个数不同，执行时间不同，但是我们粗略的认为是一致的。接下来我们编写测试用测试：

i) 测试用例1

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

每行代码的执行时间1Unit_Time,那么总共的执行时间是4Unit_Time。

ii) 测试用例2

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

这里第一行代码的执行时间是1Unit_Time,输出语句是1Unit_Time，循环代码一共2行，每行执行100次，假设循环的次数数N，那么会运行2N*Unit_Time次。然后总共累加(2N+2) * Unit_Time。

$\color{red}{ 所有代码的执行时间T(n)于每行代码的执行次数成正比。}$

iii) 测试用例3

System.out.println("执行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️⃣
 }

这里第一行代码的执行时间是1Unit_Time，第二行代码执行n^2Unit_Time，第三行代码执行nUnit_Time。所以这里总共会执行(n ^2+n+1)*Unit_Time。所以上述的推导过程是没有问题。

$\color{red}{所有代码的执行时间T(n)于每行代码的执行次数成正比。}$

6.1.4 大O计数法关注重点

假设大O计数法表示的Tn = 2n^2+1, Tn = n^2+1,Tn=n2。

数据规模

我们发现当数据规模到达一定规模的时候，可以忽略常数项和指数项。

所以一般情况下我们分析一个算法的复杂度问题时，优先关注循环次数最多的那一段代码就可以了。

1) 加法法则

i) 测试用例

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计数法表示

分析

在第一个代码段中，因为循环次数确定，所以是个常量阶，可以忽略。

在第二个代码段中，因为循环次数和N挂钩，那么循环为N

第三个代码段中，是一个双层循环，循环耗时是N^2

整个代码段的执行就是三个小代码段的累加和。那么去掉常量阶和指数阶，结果为N^2

表示

T(n) = O(f(n^2)) 其实也是我们说的时间复杂度为n^2。

$\color{green}{加法法则:总时间的复杂度等于数量级最大的那段代码的时间复杂度。}$

2) 乘法法法则

i) 测试用例

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计数法表示

分析

在第一个代码段中，本身的循环次数和N挂钩，所以它的耗时是O(n),这里注意这行代码的执行调用了fun。

在第二个代码段中，它的耗时也是O(n)。

整个代码段的其实是一个两层循环的嵌套，所以是O(n^2)

表示

T(n) = O(f(n^2)) 其实也是我们说的时间复杂度为n^2。

$\color{green}{乘法法则:总时间的复杂度等于嵌套内外代码的乘积。}$

3) 平均复杂度、均摊时间复杂度

i) 测试用例

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计数法表示

分析

上述这个代码，最好的情况下就是第一个元素就是我们要找的值，那么此时它的时间复杂度是O(1)。这个样的称之为 $\color{red}{最好时间复杂度}$

上述这个代码，最坏的情况下就是没有我们要找的元素，那么此时它的时间复杂度是O(n)。这个样的称之为 $\color{red}{最坏时间复杂度}$

但是上述两种方式都是极端情况下出现的问题，所以我们通过 $\color{red}{平均时间复杂度}$ 来表示上述代码的时间复杂度。

分析 $\color{red}{平均时间复杂度}$

$\color{red}{平均时间复杂度}$ ：在刚才的数组中，元素可能存在的位置是0-(length-1)中和不在数组中，总共length+1中情况。

我们将每种情况下查找需要遍历的个数累加起来除以length+1，就可以得到需要遍历元素的平均值。即：

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

我们忽略常数项、系数、低阶项，那么结果

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

分析 $\color{red}{加权平均时间复杂度}$

$\color{red}{加权平均时间复杂度}$ ：在刚才的数组中，要考虑每个元素是我们要查找元素的概率也需要加入进去。第一个位置存在的概率等于

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

PS：二分之一代表是否可以找到第一个元素是查找的元素，N分之一说的是每个元元素可能的概率。

我们将每种情况下每个值出现的概率也统计进去，则结果为：

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

我们忽略常数项、系数、低阶项，那么结果

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

4) 常见复杂度问题

i) ：常见复杂度

复杂度分析

ii) ：数据规模和耗时图

图片 1

6.2 常见排序算法

6.2.1 冒泡排序

冒泡排序

两两相邻的元素互相比较，一直比较到最后一个数，这样一趟下来，最后一个数要么是最大数，要么是最小数。正好比较的是数组的元素个数-1次。

持续第二次在进行两两元素比较，将倒数第二大或者倒数第二小的数放到倒数第二个位置。

持续以上的步骤，直到整个数组排完序。

1）测试用例

/**
 * 对于数组进行冒泡排序
 * @param arrs 需要排序的数组
 */
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）测试用例

//给指定的数组进行排序，默认升序
MyArrays.bubbleSort(arrs);
System.out.println("数组排序完成之后元素："+Arrays.toString(arrs));

3）结论

初始化长度为10的数组的元素是：
[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）冒泡排序优化

优化从两个方向展开，一个是每次循环的次数，一个是循环多少趟。循环的次数降低是因为每次都会有一个最大数或者最小数已经被排好序了。在某些情况下，有些数字可能经过2-3趟可能就排好序了，此时我们就可以减少趟数即可。

i）测试用例

/**
 * 对于数组进行冒泡排序
 * @param arrs 需要排序的数组
 */
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）测试用例

MyArrays.bubbleSort(arrs);
System.out.println("数组排序完成之后元素："+Arrays.toString(arrs));

iii）结论

初始化长度为10的数组的元素是：
[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]
数组排序完成之后元素：[43, 54, 71, 76, 79]

6.2.2 选择排序

1) 原理分析

用第一个元素一次和所有元素进行比较，如果存在比它小的元素，则记录位置。

整个比较完成则会记录下最小的元素的位置，然后进行位置互换。

总共比较length-1次，每一次都会确定一个最小的元素，以此类推

2) 图形展示

选择

3) 代码实现

public static void selectedSort(int[] arrs){
    //省略参数判定
    for(int i = 0;i<arrs.length-1;i++){
        int index = i;//假设目前最小的数的索引是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) 原理分析

将数组分成两部分，一部分是已经排好序了，一部分未排序。

假设已排序的数组中包含的是数组中的第一个位置上的元素，即索引是0。

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

判定当前拿到的元素和已排序的数组的元素大小，如果小于

将元素向后移动一个位置

直到比较判定失败，将当前需要插入的元素的值，插入到指定的位置上。

2) 图形展示

插入

3) 代码实现

public static void insertionSort(int[] arrs){
    //省略参数判定
    for(int i = 1;i<arrs.length;i++){
        //记录当前元素的值
        int current_value = arrs[i];
        //记录要插入元素的位置
        int pre_index = i-1;
        //循环判定要插入的位置
        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) 原理分析

对于插入排序而言，如果数据本身越有序，那么越高效。

对于数组进行分序列，假设分成length/2个序列，对于第0个元素，那就和第length/2索引位置是上的元素是一个序列，通过插入排序比较

那么第一次排序完成之后，对于元素组进行分序列，每次为length/2/2。直到分成一个序列为止。

内部不断通过插入排序比较，这样随着分成的序列越来越少，也就意味着数组本身原来越有序，插入排序的效率越来越高。

2) 图形展示

shell

3) 代码实现

public static void shellSort(int[] arrs){
    //省略参数判定
    //设置序列
    int group = arrs.length/2;
    for(;group>0;group/=2){
        // 通过插入排序 比较两个值 比较序列中的前后值
        //记录当前元素的值
        for(int i = group;i<arrs.length;i++){
            //记录当前元素的值
            int current_value = arrs[i];
            //记录要插入元素的位置
            int pre_index = i-group;
            //循环判定要插入的位置
            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) 原理分析

对于快速排序来讲，它是一个分而治之的思想。

开始存在三个值，一个是基准值base，一个是最左侧的游标L和最右侧的游标R。

基准值可以随意设置，然后移动L游标，向左移动，保证base的左侧一定是比base小的数。

反之base的右侧一定是比base大的数。然后找到之后就将L和R这两个游标位置的值进行互换，然后继续移动游标，知道出现两个游标相等或者交叉的情况。

对于左右两侧分别再继续进行快速排序即可。

2) 图形展示

快速

3) 代码实现

static void quickSort(int[]arr, int left, int right) {
    //声明存放左侧和右侧以及基准的值
    int R = right;
    int L = left;
    int base = arr[(left+right) / 2];
    //循环判定
    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;
            //继续往下走
            L++;
            R--;
        }
    }
    //准备递归调用
    if(left<R){
        quickSort(arr,left,R);
    }
    if(L>right){
        quickSort(arr,L,right);
    }
}

6.2.6 不同排序方式的效率统计

效率统计

6.3 查找算法

查找算法是我们经常会使用到的一种算法，比如我们知道的各个电商平台中的站内搜索、搜索引擎中的搜索业务等等都是查找的一种体现。显式生活中我们也经常能够碰到这样的场景，比如在很多书中找到一本自己想要看的，一般情况下我们都会将所有图书按照顺序排列，然后从头至尾开始查找，直到找到位置，又或者我们会将各个类目的图书分类然后在查找，都是在不同场景下我们会做的查找。

image

6.3.1 顺序查找

1) 原理分析

顺序查找是最基本的查找算法，就是从头至尾开始进行查找，如果找到了就不在继续查找，如果没有找到则返回一个标识，结束查找。也称之为线性查找或者是静态查找表。

2) 图形展示

顺序查找

3）代码展示

/**
 * 通过顺序查找数组中的指定元素
 * @param arrs 需要查找的数组
 * @param key 需要查找的元素
 * @return 返回是否找到的元素的索引 如果没有找到返回-1
 */
public static int orderSearch01(int[] arrs,int key){
    //省略对于数组进行判定
    int len = arrs.length;
    for(int i = 0;i<len;i++){
        if(arrs[i]==key){
            return i;
        }
    }
    return -1;
}

4) 优缺点分析

如果运气比较好，则第一个元素就是需要查找的元素，如果运气不好则最后一个才是想要查找的元素。根据我们之前学习的复杂度分析，这里的时间复杂度为 $\color{red}{O(n)}$ 。如果数组很长的时候，其实这样的查找效率是很低的。

6.3.2 优化顺序查找

1) 原理分析

假设查找数组的头或者是尾元素是需要查找的元素，然后我们从头或者尾开始进行判定是否是需要查找的元素，如果头或者尾元素是要查找的元素，则证明没有找到，除了头或尾元素之外的其他元素是查找的元素，则证明找到了，但是注意为了防止查找的数组中的元素出现问题，我们需要在其中重新复制数组。

2) 图形展示

顺序查找优化

3）代码展示

/**
* 通过优化，首先将数组中的最后一个元素空出来，存放哨兵，保证数组元素不变。
* @param arrs 查找的数组
* @param key 查找的元素
* @return 如果返回的是arrs长度的索引，则证明没有找到，反之则找到了
*/
private static int orderSearch02(int[] arrs,int key){
    //省略对于数组进行判定
    //首先复制一份数组，第0个位置上存放的是key的值
    int[] newArrs = Arrays.copyOf(arrs,arrs.length+1);

    //设置最后一个元素的值是哨兵
    newArrs[newArrs.length-1] = key;

    //声明变量从第0个元素开始查找
    int index = 0;

    //开始查找
    while(newArrs[index]!= key){
        index++;
    }
    return index;
}

4) 优缺点分析

不需要和第一次顺序查找一样，每次比较完成之后都有判定索引问题，如果总数据比较多时，其实设置哨兵的方式会在效率上提高很多，大家有兴趣可以测试一下在1亿条数据的数组中通过两种方式的时间进行比较，优化后的代码速度大概能够提高20%-40%左右。

6.3.3 折半查找

$\color{green}{PS：注意使用折半查找时一定要保证数组中的元素是有序的，不然无法保证查询结果是否正确，折半查找也称之为二分查找.}$

1) 原理分析

在数组中的元素是有序的情况下，假设数组中的元素是从小到大排序的。那么首元素索引假设为low，尾元素为high，我们去整个数组索引中的中间值假设索引为mid和需要查找的元素进行对比，如果比查找元素大，则证明在mid的索引的右侧，反之是左侧。根据不同的位置，移动low和high，不断计算mid，最后能够查找的mid就是要查找的元素的索引或者就是没有找到

2) 图形展示

二分查找

3）代码展示

/**
* 听过二分查找法查找数组的元素
* @param arrs 查找的数组
* @param key 查找的元素
* @return 返回元素的索引
*/
public static int binerySearch(int[] arrs,int key){
    //省略对于数组的判定
    int low = 0;//最小索引
    int high = arrs.length-1;//最大索引
    int mid ;//中间索引
    while(low<=high) {//最小索引小于最大索引则继续查找
        //计算中间索引
        mid = (low + high) / 2;
        //判定元素在中间索引的那一侧
        if (arrs[mid] > key) {//中间值大于查找的元素 在左侧
            //改变最大索引
            high = mid - 1;
        } else if (arrs[mid] < key) {//中间值小于查找的元素 在左侧
            //改变最小索引
            low = mid + 1;
        } else {//中间值等于查找的元素 返回
            return mid;
        }
    }
    return -1;//证明没有找到
}

4) 优缺点分析

该算法比较容易理解，并且效率较高。因为每次都是去掉一半数据进行查找，它的时间复杂度为0(logn).但是前提必须要保证数组中数据已经是有序的。如果该集合中频繁的插入或者是删除数据，那么维护有序的集合是一件很麻烦的事情，就不建议使用了。

PS:附两张图更好的理解折半查找和顺序查找的对比。

image

6.3.4 插值查找

1) 原理分析

我们在通过二分查找法进行元素查找时，发现问题，为什么每次要折一半呢？比如在一个分部均匀的数组中，<span style="color:green">arrs={1,16,22,34,45,57,68,73,86,97}</span>中查找元素<span style="color:red">16</span>,通过二分查找法要找4次才能找到，有没有好一点的方法，可以让我们通过更少的次数找到元素呢？

这里我们只需要将mid的取值改为以下方式即可。

原来计算mid的方式
$mid=\frac{low+high}{2}=low+\frac{1}{2}(high-low)$
通过算法科学家将1/2进行改进得到以下的公式
$mid=low+\frac{key-arrs[low]}{arrs[high]-arrs[low]}(high-low)$

只需要在原来计算mid的时，替换该公式即可增加当集合中的数据均匀分布时提高效率。

2）代码展示

/**
 * 通过插值查找法查找数组的元素
 * @param arrs 查找的数组
 * @param key 查找的元素
 * @return 返回元素的索引
 */
public static int nterpolationQuery(int[] arrs,int key){
    //省略对于数组的判定
    int low = 0;//最小索引
    int high = arrs.length-1;//最大索引
    int mid ;//中间索引
    while(low<=high) {//最小索引小于最大索引则继续查找
        //计算中间索引
        mid = low+(high-low)*(key-arrs[low])/(arrs[high]-arrs[low]);
        //判定元素在中间索引的那一侧
        if (arrs[mid] > key) {//中间值大于查找的元素 在左侧
            //改变最大索引
            high = mid - 1;
        } else if (arrs[mid] < key) {//中间值小于查找的元素 在左侧
            //改变最小索引
            low = mid + 1;
        } else {//中间值等于查找的元素 返回
            return mid;
        }
    }
    return -1;//证明没有找到
}

3) 优缺点分析

该算法的时间复杂度也是O(logn),但是如果查找的集合很大，而且关键词的分部很平均的话那么插值查找的算法要优于折半算法，但是如果集合中分部的数据不是很均匀，或者很极端，那么未必就适合使用插值算法。

6.3.5 斐波那契查找

推荐大家可以先看看百度百科对于斐波那契查找的说明。

在介绍斐波那契查找算法之前，先介绍一下很它紧密相连的一个概念——黄金分割。黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。

1) 原理分析

斐波那契查找其实和二分查找和插值查找是类似的，只不过对于mid的取值不同。
斐波那契查找
low和high为最大和最小索引。
我们通过斐波那契 $\color{green}{F[k]=F[k-1]+F[k-2]}$ 。可以推导出 $\color{green}{(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1}$ 。
我们只要要查找的顺序表的长度为 $\color{green}{F[k]-1}$ ,就可以将整个表分为F[k-1]-1和F[k-2]-1着两段，那么mid的位置就是low+F[k-1]-1。
然后只需要比较mid的值和key值的大小：
- 如果相等证明找到了
- 如果大于 mid>key 那么在F[k-1]-1这个位置，改变high的值，然后mid取值还是low+F[k-1]-1，所以接下来要查找的顺序表为F[k-1]-1,将整个顺序表F[k-1]-1看成一个顺序表，改变k的值，让F[k-1]-1等于F[k]-1,及k=k-1；
- 如果小于 mid<key 那么在F[k-2]-1这个顺序表中，改变low的值，然后mid取值还是low+F[k-1]-1，所以接下来要查找的顺序表为F[k-2]-1,所以将整个顺序表F[k-2]-1看成一个要查找的顺序表，改变k的值，及k=k-2。
$\color{red}{注意：这里有两个问题需要解决：}$

①：为什么整个表要看成是F[k]-1,而不是F[k]，由于刚刚我们的推导过程是可以推导出来一个 $\color{red}{(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1}$ 这个公式的，在这个公式里我们发现，抛开两个顺序表之外，还需要一个mid的值，如果直接使用F[k],那么后续要不断求得mid值而移动数组的元素。所以一般情况下我们说 $\color{blue}{要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1}$ 。

②：不是所有情况下顺序表中的数据都是比某个斐波那契数小1的，此时我们需要对于原数组进行扩容，扩展为等于或者是大于即可。

③：对于原数组中的数据，如果长度小于斐波那契数，扩容之后将超过的索引上的元素，填充最后一个元素。

之所以可以这样进行查找就是由于我们发现对于斐波那契数列而言，相邻两个数的比值不断趋向于黄金分割比例，那么我们让mid的取值位置靠近通过mid分割的两段的比值为黄金分割比例。而确定的方式就是两段的数据个数和斐波那契中相邻的两个数相等，求比值。

3）代码展示

 //计算斐波那契数列
public static int fib(int n){
    if(n==1||n==2){
        return 1;
    }
    return fib(n-1)+fib(n-2);
}
/**
     * 通过斐波那契查找法查找需要计算的值
     * @param arrs
     * @param key
     * @return
     */
public static int fibSearch(int[] arrs,int key){
    //省略数组判定
    int low = 0;//最小索引
    int high = arrs.length-1;//最大索引
    int mid ;//中间索引

    //获取k的值 使得查找的数组的长度正好小于或者等于F(k)-1
    int k = 1;
    while(arrs.length>fib(k)-1){
        k++;
    }

    //重新声明一个新的数组，然后超过的长度通过最大值填充
    int[] temp = new int[fib(k)];
    //复制原来数据
    System.arraycopy(arrs,0,temp,0,arrs.length);
    //对于超过的数据填充最大值
    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向右移动
            k = k-1;//对应上图中的左端 长度为F[k-1]-1
        }else if(temp[mid]<key) {
            low=mid+1;//low向左移动
            k=k-2;  //对应上图中的右端，长度F[k-2]-1
        }else {
            if(mid<=arrs.length)
                return mid;
            else
              //当mid位于新增的数组中时，证明要查找的数是最后一个位置上的
                return arrs.length;     
        }
    }
    return -1;
}

4) 优缺点分析

该算法的时间复杂度也是O(logn),但是就平均性能来说，斐波那契查找要优于折半查找，但是如果要查找的元素的一直处于整个顺序表的最左侧，也就意味着每次都要在长半区进行查找，此时效率就低于折半。

折半、插值、斐波那契其实都是将原本很大的有序顺序表拆分成2部分，进行递归查找，不过选择的中间点mid不同。各有优劣。

参考网站：
https://www.cnblogs.com/onepixel/articles/7674659.html
参考书籍：
大话数据结构，Java算法手册

老薛陪你一起过情人节，常见数组5大排序和4大查找算法实现

情人节要啥鲜花，要啥女朋友？老薛陪你过😋

6.1 数据结构和算法

6.1.1 问题

6.1.2 如何评价一个算法是否优秀

6.1.3 大O计数法计算时间复杂度

1) 什么是大O计数法？(Big O Notation)

2) 大O计数法的推导过程

i) 测试用例1

ii) 测试用例2

iii) 测试用例3

6.1.4 大O计数法关注重点

1) 加法法则

i) 测试用例

ii) 大O计数法表示

2) 乘法法法则

i) 测试用例

ii) 大O计数法表示

3) 平均复杂度、均摊时间复杂度

i) 测试用例

ii) 大O计数法表示

4) 常见复杂度问题

i) ：常见复杂度

ii) ：数据规模和耗时图

6.2 常见排序算法

6.2.1 冒泡排序

1） 测试用例

2） 测试用例

3） 结论

4） 冒泡排序优化

i） 测试用例

ii） 测试用例

iii） 结论

6.2.2 选择排序

1) 原理分析

2) 图形展示

3) 代码实现

6.2.3 插入排序

1) 原理分析

2) 图形展示

3) 代码实现

6.2.4 Shell排序

1) 原理分析

2) 图形展示

3) 代码实现

6.2.5 快速排序

1) 原理分析

2) 图形展示

3) 代码实现

6.2.6 不同排序方式的效率统计

6.3 查找算法

6.3.1 顺序查找

1) 原理分析

2) 图形展示

3）代码展示

4) 优缺点分析

6.3.2 优化顺序查找

1) 原理分析

2) 图形展示

3）代码展示

4) 优缺点分析

6.3.3 折半查找

1) 原理分析

2) 图形展示

3）代码展示

4) 优缺点分析

6.3.4 插值查找

1) 原理分析

2）代码展示

3) 优缺点分析

6.3.5 斐波那契查找

1) 原理分析

3）代码展示

4) 优缺点分析

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

1）测试用例

2）测试用例

3）结论

4）冒泡排序优化

i）测试用例

ii）测试用例

iii）结论