数据结构和算法的学习笔记(第七部分)

简介: 自学笔记

7.6 、选择排序

7.6.1、基本介绍

选择式排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。

7.6.2、选择排序思想:

选择排序(select sorting)也是一种简单的排序方法。它的基本思想是:第一次从arr[0]~arr[n-1]中选取最小值,与 arr[0]交换,第二次从 arr[1]~arr[n-1]中选取最小值,与 arr[1]交换,第三次从 arr[2]~arr[n-1]中选取最小值,与arr[2]交换,…,第 i 次从 arr[i-1]~arr[n-1]中选取最小值,与 arr[i-1]交换,…, 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值,与 arr[n-2]交换,总共通过 n-1 次,得到一个按排序码从小到大排列的有序序列。

7.6.3、选择排序思路分析图:

image-20221122102502405

对一个数组的选择排序再进行讲解

  • 原始的数组 : 101, 34, 119, 1

  • 第一轮排序 : 1, 34, 119, 101

  • 第二轮排序 : 1, 34, 119, 101

  • 第三轮排序 : 1, 34, 101, 119

    说明:

    1. 选择排序一共有 数组大小 - 1 轮排序

    2. 每1轮排序,又是一个循环, 循环的规则(代码)

    • 2.1先假定当前这个数是最小数
    • 2.2 然后和后面的每个数进行比较,如果发现有比当前数更小的数,就重新确定最小数,并得到下标
    • 2.3 当遍历到数组的最后时,就得到本轮最小数和下标

7.6.4、选择排序应用实例

有一群牛 , 颜值分别是 101, 34, 119, 1 请使用选择排序从低到高进行排序 [101, 34, 119, 1]

  • 代码实现
/**
 * description
 * 选择排序的案例
 *
 * @author
 * @since 2022/11/22 10:56
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1};
        System.out.println("排序前" + Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序后" + Arrays.toString(arr));
    }

    //选择排序
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {   //让最小数和下标为一的数进行比较
                if (min > arr[j]) { //说明假定的最小值并部署最小的
                    min = arr[j];  //重置min
                    minIndex = j;  //重置minIndex
                }
            }
            //将最小值放在arr[0],即交换
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }
}

代码说明:算法思想:先简单--》 再复杂, 就是可以把一个复杂的算法,拆分成简单的问题-》逐步解决

  • 写代码和设计程序也是同理

7.7 、插入排序

7.7.1、插入排序法介绍

插入式排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的

7.7.2、插入排序法思想

插入排序(Insertion Sorting)的基本思想是:把 n 个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有 n-1 个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。

7.7.3、插入排序思路图

image-20221122114119807

7.7.4、插入排序法应用实例:

有一群小牛, 考试成绩分别是 101, 34, 119, 1 请从小到大排序

代码实现如下:

/**
 * description
 * 插入排序法的案例
 *
 * @author
 * @since 2022/11/22 13:00
 */
public class InsertSoft {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1};
        System.out.println("排序插入前" + Arrays.toString(arr));
        insert(arr);
    }

    /**
     * 插入排序,进行逐步推导
     *
     * @param arr 定义的一位数组,用于存放数据
     */
    public static void insert(int[] arr) {
        //使用for循环把代码简化
        for (int i = 1; i < arr.length; i++) {
            //首先定义待插入的数,第一轮排序{101, 34, 119, 1} --> {34, 101, 119, 1}
            int insertVal = arr[i];
            int insertIndex = i - 1;   //即arr[1]的前面数的下标

            /*给insertVal找到插入的位置, insertIndex >= 0保证在找插入位置时不越界
             * insertVal < arr[insertIndex]说明待插入的数还没找到适当的插入位置
             * 就需要将 arr[insertIndex] 后移 */
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex]; //将 arr[insertIndex]后移
                insertIndex--;
            }
            //当退出while循环时,说明插入的位置找到,insertIndex +1
            arr[insertIndex + 1] = insertVal;
            System.out.println("第" + i + "轮插入后" + Arrays.toString(arr));
        }
    }
}

7.8 、希尔排序

7.8.1、简单插入排序存在的问题

我们看简单的插入排序可能存在的问题

数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是:

{2,3,4,5,6,6} --> {2,3,4,5,5,6} --> {2,3,4,4,5,6} --> {2,3,3,4,5,6} --> {2,2,3,4,5,6} --> {1,2,3,4,5,6}

结论: 当需要插入的数是较小的数时后移的次数明显增多,对效率有影响.

7.8.2、希尔排序法介绍

希尔排序是希尔(Donald Shell)于 1959 年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序

7.8.3、希尔排序法基本思想

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止

7.8.4、希尔排序法的示意图

image-20221123090129548

image-20221123090143544

7.8.5、希尔排序法应用实例

有一群小牛, 考试成绩分别是 {8,9,1,7,2,3,5,4,6,0} 请从小到大排序. 请分别使用

1) 希尔排序时, 对有序序列在插入时采用交换法, 并测试排序速度

2) 希尔排序时, 对有序序列在插入时采用移动法, 并测试排序速度

3) 代码实现

/**
 * description
 * 希尔排序中交换法的案例
 *
 * @author
 * @since 2022/11/23 9:34
 */
public class ShellSort {

    public static void main(String[] args) {
        //首先定义需要排序的数组
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort(arr);
    }

    /**
     * 使用逐步推导的方式编写希尔排序
     *
     * @param arr 需要排序的数组
     */
    public static void shellSort(int[] arr) {
        int temp;
        int count = 0; //计数器
        //根据逐步分析得到规律
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //遍历各组中所有的元素(共gap组,每组gap/2个元素),步长gap
                for (int j = i - gap; j >= 0; j -= gap) {
                    //如果当前元素大于加上步长后的那个元素,说明需要交换
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println("希尔排序第" + (++count) + "轮后数组的情况=" + Arrays.toString(arr));
        }
    }
}

/**
 * description
 * 希尔排序中移动法的案例
 *
 * @author
 * @since 2022/11/23 10:26
 */
public class ShellSortTwo {
    public static void main(String[] args) {
        //首先定义需要排序的数组
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort(arr);
    }

    //对交换式的希尔排序进行优化 -->移动法
    public static void shellSort(int[] arr) {
        //增量gap,并逐步地缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从第gap个元素开始,逐个对其所在的组进行直接插入
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //当退出while循环后,就给temp找到插入的位置
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

7.9 、快速排序

7.9.1、快速排序法介绍

快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

7.9.2、快速排序法示意图:

image-20221124090452656

image-20221124090439999

7.9.3、快速排序法应用实例:

要求: 对 [-9,78,0,23,-567,70] 进行从小到大的排序,要求使用快速排序法。【测试8w 和800w】说明[验证分析]:

1) 如果取消左右递归,结果是 -9 -567 0 23 78 70

2) 如果取消右递归,结果是 -567 -9 0 23 78 70

3) 如果取消左递归,结果是 -9 -567 0 23 70 78

4) 代码实现

/**
 * description
 * 快速排序的案例
 *
 * @author
 * @since 2022/11/24 10:56
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("arr=" + Arrays.toString(arr));
    }

    /**
     * 快速排序
     *
     * @param arr   需要排序的数组
     * @param left  左边的索引
     * @param right 右边的索引
     */
    public static void quickSort(int[] arr, int left, int right) {
        int l = left;   //左下标
        int r = right;  //右下标
        //中轴值
        int pivot = arr[(left + right) / 2];
        int temp = 0;  //临时变量,作为交换时使用
        while (l < r) {  //while循环的目的是让比pivot值小的放到左边,比pivot值大的放右边
            while (arr[l] < pivot) {   //在pivot左边一直找,找到大于等于pivot的值才退出
                l += 1;
            }
            while (arr[r] > pivot) {   //在pivot右边一直找,找到大于等于pivot的值才退出
                r -= 1;
            }
            //如果 l >= r 成立,说明pivot左右的值已经按照左边全是小于等于pivot值,右边大于等于pivot值
            if (l >= r) {
                break;
            }
            //若以上条件没满足,进行交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完后发现arr[l] == pivot值相等r--,前移
            if (arr[l] == pivot) {
                r -= 1;
            }
            //如果交换完后发现arr[r] == pivot值相等l++,后移
            if (arr[r] == pivot) {
                l += 1;
            }
        }
        //如果l == r ,必须l++,r--,否则会出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if (left < r) {
            quickSort(arr, left, r);
        }
        //向右递归
        if (right > l) {
            quickSort(arr, l, right);
        }
    }
}

7.10 、归并排序

7.10.1 、归并排序介绍

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

7.10.2、 归并排序思想示意图 1-基本思想:

image-20221125083510795

7.10.3、 归并排序思想示意图 2-合并相邻有序子序列:

再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤

image-20221125084505888

7.10.4、归并排序的应用实例:

给你一个数组, val arr = Array(8, 4, 5, 7, 1, 3, 6, 2 ), 请使用归并排序完成排序。

代码实现

/**
 * description
 * 归并排序的案例
 *
 * @author
 * @since 2022/11/25 8:52
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] temp = new int[arr.length];  //归并排序需要额外的空间
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 分 + 合并方法
     *
     * @param arr   待排序的数组
     * @param left  左边有序序列的初始索引
     * @param right 右边索引
     * @param temp  临时数组
     */
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;   //中间的索引
            //向左递归进行分解
            mergeSort(arr, left, mid, temp);
            //向右递归进行分解
            mergeSort(arr, mid + 1, right, temp);
            //到合并
            merge(arr, left, mid, right, temp);
        }
    }

    /**
     * 合并的方法
     *
     * @param arr   待排序的数组
     * @param left  左边有序序列的初始索引
     * @param right 右边索引
     * @param mid   中间索引
     * @param temp  临时数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;  //初始化i,左边有序序列的初始索引
        int j = mid + 1;  //初始化j,右边有序序列的初始索引
        int t = 0;   //指向temp数组的当前索引

        //1、先把左右两边的数据按照规则填充到temp数组,知道左右两边的有序序列有一方处理完毕为主
        while (i <= mid && j <= right) {//继续
            // 如果左边的有序序列的当前元素,小于等于右边有序序列的当前元素,即将左边的元素拷贝到temp,然后t后移
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else { //反之,将右边有序序列的当前元素填充到temp数组里去
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        //2、把有剩余数据的一边全部依次填充到temp
        while (i <= mid) {  //说明左边的有序序列还有剩余元素,就全部填充到temp里去
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }

        while (j <= right) {  //说明右边的有序序列还有剩余元素,就全部填充到temp里去
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
        //3、将temp数组的元素拷贝到arr,但并不是每一次都拷贝所有的元素
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }
}

7.11、 基数排序

7.11.1、 基数排序(桶排序)介绍:

1) 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用

2) 基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法

3) 基数排序(Radix Sort)是桶排序的扩展

4) 基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较。

7.11.2 、基数排序基本思想

1) 将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

2)图文解释,理解基数排序的步骤

7.11.3 、基数排序图文说明

image-20221126104705424

image-20221126104728633

7.11.4、 基数排序代码实现

要求:将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序

代码实现:

/**
 * description
 * 基数排序的代码实现,即将无需数组转成有序
 *
 * @author
 * @since 2022/11/26 16:21
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
    }

    /**
     * 基数排序的方法
     *
     * @param arr 需要进行排序的数组
     */
    public static void radixSort(int[] arr) {
        //根据推导过程,得到最终的基数排序代码,得到数组中最大的数的位数
        int max = arr[0];   //假设第一个数就是最大数
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();

        /*
        第一轮排序(针对每个元素的个位进行排序处理)
        定义一个二维数组表示10个桶,每个桶就是一个一维数组
        说明:1、二维数组包含十个一位数组
        2、为了防止在放入数时数据溢出,则每个一维数组(桶),大小为arr.length
        3、由此很明显地发现,基数排序是使用空间换时间的经典算法*/
        int[][] bucket = new int[10][arr.length];

        /* 为了记录每个桶中实际存放了多少个数据,我们定义一个一维数组来记录各个桶每次放入的数据个数
        int[] bucketElementCounts 可以理解为,记录的就是bucket[] 桶放入的数据个数*/
        int[] bucketElementCounts = new int[10];

        //这里使用循环将代码处理
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //(针对每个元素的对应的个位进行排序处理),第一次是个位,第二次是十位第三次是百位
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的个位的值
                int digitOfElement = arr[j] / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            //按照这个桶的顺序(一维数组的下标依次取出数据,放入原来数组)
            int index = 0; //下标
            //遍历每一个桶,并将桶中的数据放入到原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中有数据,我们才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    //循环第k个桶(即第k个一维数组),放入数据即可
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入到arr中
                        arr[index++] = bucket[k][l];
                    }
                }
                //第i+1轮处理后,需要将每个bucketElementCounts[k] = 0!
                bucketElementCounts[k] = 0;
            }
            System.out.println("第" + (i + 1) + "轮,对个位的排序处理arr=" + Arrays.toString(arr));
        }
    }
}

7.11.5 、基数排序的说明:

1) 基数排序是对传统桶排序的扩展,速度很快.

2) 基数排序是经典的空间换时间的方式,占用内存很大, 当对海量数据排序时,容易造成OutOfMemoryError 。

3) 基数排序时稳定的。[注:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且 r[i]在 r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的]

4) 有负数的数组,我们不用基数排序来进行排序, 如果要支持负数,参考: https://code.i-harness.com/zh-CN/q/e98fa9

7.12 、常用排序算法总结和对比

7.12.1 、一张排序算法的比较图

image-20221126211218351

7.12.2 、相关术语解释

1) 稳定:如果 a 原本在 b 前面,而 a=b,排序之后 a 仍然在 b 的前面;

2) 不稳定:如果 a 原本在 b 的前面,而 a=b,排序之后 a 可能会出现在 b 的后面;

3) 内排序:所有排序操作都在内存中完成;

4) 外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

5) 时间复杂度: 一个算法执行所耗费的时间。

6) 空间复杂度:运行完一个程序所需内存的大小。

7) n: 数据规模

8) k: “桶”的个数

9) In-place: 不占用额外内存

10) Out-place: 占用额外内存

八、查找算法

8.1 、查找算法介绍 在 java 中,我们常用的查找有四种:

1) 顺序(线性)查找

2) 二分查找/折半查找

3) 插值查找

4) 斐波那契查找

8.2 、线性查找算法

有一个数列: {1,8, 10, 89, 1000, 1234} ,判断数列中是否包含此名称【顺序查找】要求: 如果找到了,就提示找到,并给出下标值。

代码实现如下:

 /**
 * description
 * 线性查找算法的代码实现
 *
 * @author
 * @since 2022/11/27 16:25
 */
public class SeqSearch {
    public static void main(String[] args) {
        int[] arr = {1, 9, 11, -1, 34, 89};  //没有顺序的数列
        int index = search(arr,-11);
        if (index == -1 ){
            System.out.println("没有查找到你要找的这个值");
        }else {
            System.out.println("找到,下标为=" + index);
        }
    }

    /**
     * 这里实现的线性查找的方法是找到满足一个条件的值就返回
     *
     * @param arr   需要查找的数组
     * @param value 需要查找的值
     * @return 查找数的下标
     */
    public static int search(int[] arr, int value) {
        //线性查找是逐一比对,发现有相同值,就返回下标
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == value){
                return i;
            }
        }
        return -1;
    }
}

8.3、 二分查找算法

8.3.1、二分查找:

请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数"。

8.3.2、二分查找算法的思路

image-20221127163509876

说明:如果需要二分查找的数组是倒序,2.1和2.2的递归条件则相反

8.3.3、二分查找的代码实现

代码实现

/**
 * description
 * 二分查找的案例
 *
 * @author
 * @since 2022/11/27 16:51
 */
public class BinarySearch {

    //注意:使用二分查找的前提是:该数组是有序的
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        int resultIndex = binarySearch(arr, 0, arr.length - 1, 1);   //结果索引
        System.out.println("resultIndex=" + resultIndex);
    }

    /**
     * 二分查找的算法
     *
     * @param arr     需要查找的数组
     * @param left    左边的索引
     * @param right   右边的索引
     * @param findVal 需要查找的值
     * @return 如果找到就返回值的下标,没有找到就返回-1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {

        //当left > right 时,说明递归整个数组,但是也没有找到
        if (left < right) {
            return -1;
        }
        int mid = (left + right) / 2; //中间数的下标
        int midVal = arr[mid];  //中间数的值

        //如果查找的值大于中间的值
        if (findVal > midVal) { //向右递归
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {  //向左递归
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }
}

8.3.4、二分查找的优化

说明:增加了找到所有的满足条件的元素下标:

课后思考题: {1,8, 10, 89, 1000, 1000,1234} 当一个有序数组中,有多个相同的数值时,如何将所有的数值都查找到,比如这里的 1000

代码实现:

/**
     * 二分查找中有多个相同的值,如何将所有数值都找到
     * 思路分析
     * 1、在找到mid索引值,不要马上返回
     * 2、向mid索引值的左边扫描,将所有满足查找值的元素下标加入到一个集合中
     * 3、向mid索引值的右边扫描,将所有满足查找值的元素下标加入到一个集合中
     * 4、将集合返回即可
     *
     * @param arr     需要查找的数组
     * @param left    左边的索引
     * @param right   右边的索引
     * @param findVal 需要查找的值
     * @return 如果找到就返回值的下标,没有找到就返回-1,找到相同的数时将他们存入一个集合中
     */
    public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {

        //当left > right 时,说明递归整个数组,但是也没有找到
        if (left > right) {
            return new ArrayList<Integer>();
        }
        int mid = (left + right) / 2; //中间数的下标
        int midVal = arr[mid];  //中间数的值

        //如果查找的值大于中间的值
        if (findVal > midVal) { //向右递归
            return binarySearch2(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {  //向左递归
            return binarySearch2(arr, left, mid - 1, findVal);
        } else {
            //创建一个集合,用于存放备查找的数值
            ArrayList<Integer> resultIndexList = new ArrayList<Integer>();
            //向mid索引值的左边扫描,将所有满足查找值的元素下标加入到一个集合中
            int temp = mid - 1;
            while (temp >= 0 && arr[temp] == findVal) {
                //否则就把temp放到集合中
                resultIndexList.add(temp);
                temp -= 1; //temp左移
            }
            resultIndexList.add(mid);

            //向mid索引值的右边扫描,将所有满足查找值的元素下标加入到一个集合中
            temp = mid + 1;
            while (temp <= arr.length - 1 && arr[temp] == findVal) {
                //否则就把temp放到集合中
                resultIndexList.add(temp);
                temp += 1; //temp右移
            }
            return resultIndexList;
        }
    }

8.3.5、二分查找的力扣练习题

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

思路分析

  • 首先确定该数组的中间的下标
  • mid = (right - left) / 2 + left
  • 然后让需要查找的数 findVal 和 arr[mid] 比较
    • target > arr[mid] , 说明你要查找的数在mid 的右边, 因此需要递归的向右查找
    • target < arr[mid], 说明你要查找的数在mid 的左边, 因此需要递归的向左查找
    • target == arr[mid] 说明找到,就返回
      • 什么时候我们需要结束递归.
        • 找到就结束递归
        • 递归完整个数组,仍然没有找到target ,也需要结束递归 当 left <= right 就需要退出

代码实现

class Solution {
    public int search(int[] nums, int target) {
        int left = 0; //左边索引
        int right = nums.length - 1;  //右边索引
        while (left <= right) {  //若左边索引大于等于右边,就是死递归
            int mid = (right - left) / 2 + left; //中间数的下标
            int midVal = nums[mid];  //中间数的值
            //如果寻找值等于中间值,直接返回
            if (midVal == target) {
                return mid;
            } else if (midVal > target) {   //大于中间值,向左递归
                right = mid - 1;
            } else {  //小于中间值,向右递归
                left = mid + 1;
            }
        }
        return -1;
    }
}

8.4 、插值查找算法

1) 插值查找原理介绍: 插值查找算法类似于二分查找,不同的是插值查找每次从自适应 mid 处开始查找。

2) 将折半查找中的求 mid 索引的公式 , low 表示左边索引 left, high 表示右边索引 right. key 就是前面我们讲的 findVal

image-20221128100421295

3) int mid = low + (high - low) (key - arr[low]) / (arr[high] - arr[low]) ;插值索引 对应前面的代码公式: int mid = left + (right – left) (findVal – arr[left]) / (arr[right] – arr[left])

4) 举例说明插值查找算法 1-100 的数组

image-20221128095827516

8.4.1、插值查找应用案例:

请对一个有序数组进行插值查找 {1,2,3,4,...,100} ,输入一个数看看该数组是否存在此数,并且求出下标

代码实现:

/**
 * description
 * 插值查找的算法案例实现——对一个有序数组进行插值查找 {1,2,3,4,...,100}
 *
 * @author
 * @since 2022/11/28 10:21
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {  //生成1-100的数组
            arr[i] = i + 1;
        }
        int resultIndexValue = insertValueSearch(arr, 0, arr.length - 1, 100);
        System.out.println("resultIndexValue=" + resultIndexValue);
    }

    /**
     * 编写插值插值查找算法,思路大致跟二分查找一致,要求数组是有序的
     *
     * @param arr       传入的数组
     * @param left      左边的索引
     * @param right     右边的索引
     * @param findValue 查找的值
     * @return 如果找到就返回查找数值的下标,如果没有找到返回-1
     */
    public static int insertValueSearch(int[] arr, int left, int right, int findValue) {
        System.out.println("查找次数");
        //这些条件必须需要,否则数组可能会越界
        if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) {
            return -1;
        }
        //找出中间索引
        int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);
        //找到中间值
        int midValue = arr[mid];
        if (findValue == midValue) {
            return mid;
        } else if (findValue > midValue) { //向左递归
            return insertValueSearch(arr, mid + 1, right, findValue);
        } else { //向右递归
            return insertValueSearch(arr, left, mid - 1, findValue);
        }
    }
}

8.4.2、插值查找注意事项

1) 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找, 速度较快.

2) 关键字分布不均匀的情况下,该方法不一定比折半查找要好

8.5 、斐波那契(黄金分割法)查找算法

8.5.1、斐波那契(黄金分割法)查找基本介绍:

1) 黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是 0.618。由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比。这是一个神奇的数字,会带来意向不大的效果。

2) 斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数 的比例,无限接近黄金分割值0.618

8.5.2、斐波那契(黄金分割法)原理:

斐波那契查找原理与前两种相似,仅仅改变了中间结点(mid)的位置,mid 不再是中间或插值得到,而是位于黄金分割点附近,即 mid=low+F(k-1)-1(F 代表斐波那契数列),如下图所示

image-20221129093949016

对 F(k-1)-1 的理解:

1) 由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质,可以得到 (F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1 。该式说明:只要顺序表的长度为 F[k]-1,则可以将该表分成长度为 F[k-1]-1 和 F[k-2]-1 的两段,即如上图所示。从而中间位置为 mid=low+F(k-1)-1

2) 类似的,每一子段也可以用相同的方式分割

3) 但顺序表长度 n 不一定刚好等于 F[k]-1,所以需要将原来的顺序表长度 n 增加至F[k]-1。这里的k 值只要能使得 F[k]-1 恰好大于或等于 n 即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1 到F[k]-1 位置),都赋为 n 位置的值即可。 while(n>fib(k)-1) k++;

8.5.3、斐波那契查找应用案例

请对一个有序数组进行斐波那契查找 {1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数"。

代码实现如下:

/**
 * description
 * 斐波那契查找的案例
 *
 * @author
 * @since 2022/11/29 9:54
 */
public class FibonacciSearch {

    public static int maxSize = 20;  //初始化变量

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

    /**
     * 因为我们要使用斐波那契算法,因此需要先获取斐波那契数列
     * 使用非递归的方式得到一个斐波那契数列
     * 公式为 F[k]=F[k-1]+F[k-2]--> (F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1
     */
    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    /**
     * 编写斐波那契数列查找算法
     * 使用非递归的方式编写
     *
     * @param arr 数组
     * @param key 需要查找的关键值
     * @return 返回对于下标,如果没有就返回-1
     */
    public static int fibSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int k = 0; //表示斐波那契分割数值的下标
        int mid = 0;  //存放mid值
        int[] f = fib();  //获取到斐波那契数列
        //获取到斐波那契数值的下标,也就是k
        while (high > f[k] - 1) {
            k++;    
        }
        //因为f[k] 值可能大于数组的arr的长度,因此我们需要使用一个Arrays构造一个新的数组并指向arr
        int[] temp = Arrays.copyOf(arr, f[k]);
        //实际上需要使用数组最后一个元素填充temp
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        //使用while来循环处理,找到需要的找到的值(k)
        while (low <= high) {  //只要这个条件满足就可以一直找
            mid = low + f[k - 1] - 1;
            if (key < temp[mid]) {  //说明我们应该继续向数组的前部分查找(左边)
                high = mid - 1;

                /* 为什么是k--,说明:
                1、全部元素= 前面的元素 + 后面的元素
                2、f[k] = f[k-1] + f[k-2]
                3、因为前面有f[k-1]个元素,所以可以继续拆分f[k-1] = f[k-2] + f[k-3]
                4、即在f[k-1]的前面继续查找k--,即下次循环mid = f[k-1-1]-1*/
                k--;
            } else if (key > temp[mid]) {  //说明我们应该继续向数组的前部分查找(右边)
                low = mid + 1;

                /* 为什么是k-=2 ,说明:
                1、全部元素= 前面的元素 + 后面的元素
                2、f[k] = f[k-1] + f[k-2]
                3、因为后面我们有f[k-2],所以可以继续拆分f[k-1] = f[k-3] +f[k-4]
                4、即在f[k-2]的前面进行查找 k-=2
                5、即下次循环 mid = f[k-1-2]-1*/
                k -= 2;
            } else { //找到了
                //需要确定返回的是哪个下标
                if (mid <= high){
                    return mid;
                }else {
                    return high;
                }
            }
        }
        return -1;
    }
}
相关文章
|
22天前
|
存储 算法 Java
【数据结构与算法】1.数据结构绪论
【数据结构与算法】1.数据结构绪论
|
24天前
|
算法
【数据结构入门精讲 | 第十七篇】一文讲清图及各类图算法
【数据结构入门精讲 | 第十七篇】一文讲清图及各类图算法
26 0
|
24天前
|
搜索推荐 算法 大数据
【数据结构入门精讲 | 第十篇】考研408排序算法专项练习(二)
【数据结构入门精讲 | 第十篇】考研408排序算法专项练习(二)
20 0
|
24天前
|
存储 搜索推荐 算法
【数据结构入门精讲 | 第九篇】考研408排序算法专项练习(一)
【数据结构入门精讲 | 第九篇】考研408排序算法专项练习(一)
16 0
|
24天前
|
存储 搜索推荐 算法
【数据结构入门精讲 | 第八篇】一文讲清全部排序算法(2)
【数据结构入门精讲 | 第八篇】一文讲清全部排序算法(2)
18 0
|
24天前
|
搜索推荐 算法 Shell
【数据结构入门精讲 | 第七篇】一文讲清全部排序算法(1)
【数据结构入门精讲 | 第七篇】一文讲清全部排序算法(1)
15 0
|
1天前
|
存储
栈和队列OJ题
栈和队列OJ题
6 0
|
1天前
|
编译器 C++
队列实现栈VS栈实现队列
队列实现栈VS栈实现队列
6 0
|
1天前
【数组栈】实现
【数组栈】实现
5 0

相关产品