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、选择排序思路分析图:
对一个数组的选择排序再进行讲解
原始的数组 ： 101, 34, 119, 1
第一轮排序 : 1, 34, 119, 101
第二轮排序 : 1, 34, 119, 101
第三轮排序 : 1, 34, 101, 119
说明：
选择排序一共有 数组大小 - 1 轮排序
每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、插入排序思路图
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、希尔排序法的示意图
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、快速排序法示意图:
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-基本思想:
7.10.3、 归并排序思想示意图 2-合并相邻有序子序列:
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤
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 、基数排序图文说明
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 、一张排序算法的比较图
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、二分查找算法的思路
说明：如果需要二分查找的数组是倒序，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
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 的数组
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 代表斐波那契数列），如下图所示
对 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;
}
}
