共计 11055 个字符，预计需要花费 28 分钟才能阅读完成。
常见的七种查找算法：
数据结构是数据存储的形式，算法是数据计算的形式。所以在开发中，算法和数据结构非亲非故。明天的讲义中会波及局部数据结构的专业名词，如果各位铁粉有纳闷，能够先看一下哥们前面录制的数据结构，再回头看算法。
1. 根本查找
也叫做程序查找
阐明：程序查找适宜于存储构造为数组或者链表。
根本思维 ：程序查找也称为线形查找，属于无序查找算法。从数据结构线的一端开始，程序扫描，顺次将遍历到的结点与要查找的值相比拟，若相等则示意查找胜利；若遍历完结仍没有找到雷同的，示意查找失败。
示例代码：
public class A01_BasicSearchDemo1 {public static void main(String[] args) {
// 根本查找 / 程序查找
// 外围：// 从 0 索引开始挨个往后查找
// 需要：定义一个办法利用根本查找，查问某个元素是否存在
// 数据如下：{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));
}
// 参数：// 一：数组
// 二：要查找的元素
// 返回值：// 元素是否存在
public static boolean basicSearch(int[] arr, int number){
// 利用根本查找来查找 number 在数组中是否存在
for (int i = 0; i < arr.length; i++) {if(arr[i] == number){return true;}
}
return false;
}
}2. 二分查找
也叫做折半查找
阐明：元素必须是有序的，从小到大，或者从大到小都是能够的。
如果是无序的，也能够先进行排序。然而排序之后，会扭转原有数据的程序，查找进去元素地位跟原来的元素可能是不一样的，所以排序之后再查找只能判断以后数据是否在容器当中，返回的索引无理论的意义。
根本思维 ：也称为是折半查找，属于有序查找算法。用给定值先与两头结点比拟。比拟完之后有三种状况：
-
相等
阐明找到了
-
要查找的数据比两头节点小
阐明要查找的数字在两头节点右边
-
要查找的数据比两头节点大
阐明要查找的数字在两头节点左边
代码示例：
package com.itheima.search;
public class A02_BinarySearchDemo1 {public static void main(String[] args) {
// 二分查找 / 折半查找
// 外围：// 每次排除一半的查找范畴
// 需要：定义一个办法利用二分查找，查问某个元素在数组中的索引
// 数据如下：{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. 利用循环不断的去找要查找的数据
while(true){if(min > max){return -1;}
//3. 找到 min 和 max 的两头地位
int mid = (min + max) / 2;
//4. 拿着 mid 指向的元素跟要查找的元素进行比拟
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. 插值查找
在介绍插值查找之前，先思考一个问题：
为什么二分查找算法肯定要是折半，而不是折四分之一或者折更多呢？
其实就是因为不便，简略，然而如果我能在二分查找的根底上，让两头的 mid 点，尽可能凑近想要查找的元素，那不就能进步查找的效率了吗？
二分查找中查找点计算如下：
mid=(low+high)/2, 即 mid=low+1/2*(high-low);
咱们能够将查找的点改良为如下：
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，
这样，让 mid 值的变动更凑近关键字 key，这样也就间接地缩小了比拟次数。
根本思维：基于二分查找算法，将查找点的抉择改良为自适应抉择，能够进步查找效率。当然，差值查找也属于有序查找。
细节： 对于表长较大，而关键字散布又比拟平均的查找表来说，插值查找算法的均匀性能比折半查找要好的多。反之，数组中如果散布十分不平均，那么插值查找未必是很适合的抉择。
代码跟二分查找相似，只有批改一下 mid 的计算形式即可。
4. 斐波那契查找
在介绍斐波那契查找算法之前，咱们先介绍一下很它严密相连并且大家都熟知的一个概念——黄金分割。
黄金比例又称黄金分割，是指事物各局部间肯定的数学比例关系，行将整体一分为二，较大局部与较小局部之比等于整体与较大局部之比，其比值约为 1:0.618 或 1.618:1。
0.618 被公认为最具备审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、修建等艺术畛域，而且在治理、工程设计等方面也有着不可漠视的作用。因而被称为黄金分割。
在数学中有一个十分有名的数学法则：斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….
（从第三个数开始，后边每一个数都是前两个数的和）。
而后咱们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越靠近 0.618，利用这个个性，咱们就能够将黄金比例使用到查找技术中。
根本思维：也是二分查找的一种晋升算法，通过使用黄金比例的概念在数列中抉择查找点进行查找，进步查找效率。同样地，斐波那契查找也属于一种有序查找算法。
斐波那契查找也是在二分查找的根底上进行了优化，优化两头点 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;
// 示意斐波那契数宰割数的下标值
int index = 0;
int mid = 0;
// 调用斐波那契数列
int[] f = getFeiBo();
// 获取斐波那契宰割数值的下标
while (high > (f[index] - 1)) {index++;}
// 因为 f[k] 值可能大于 a 的长度，因而须要应用 Arrays 工具类，结构一个新法数组，并指向 temp[], 有余的局部会应用 0 补齐
int[] temp = Arrays.copyOf(arr, f[index]);
// 理论须要应用 arr 数组的最初一个数来填充有余的局部
for (int i = high + 1; i < temp.length; i++) {temp[i] = arr[high];
}
// 应用 while 循环解决，找到 key 值
while (low <= high) {mid = low + f[index - 1] - 1;
if (key < temp[mid]) {// 向数组的后面局部进行查找
high = mid - 1;
/*
对 k -- 进行了解
1. 全副元素 = 后面的元素 + 前面的元素
2.f[k]=k[k-1]+f[k-2]
因为后面有 k - 1 个元素没所以能够持续分为 f[k-1]=f[k-2]+f[k-3]
即在 f[k-1] 的后面持续查找 k --
即下次循环,mid=f[k-1-1]-1
*/
index--;
} else if (key > temp[mid]) {// 向数组的前面的局部进行查找
low = mid + 1;
index -= 2;
} else {// 找到了
// 须要确定返回的是哪个下标
if (mid <= high) {return mid;} else {return high;}
}
}
return -1;
}
}
5. 分块查找
当数据表中的数据元素很多时，能够采纳分块查找。
吸取了程序查找和折半查找各自的长处，既有动静构造，又适于疾速查找
分块查找实用于数据较多，然而数据不会发生变化的状况，如果须要一边增加一边查找，倡议应用哈希查找
分块查找的过程：
- 须要把数据分成 N 多小块，块与块之间不能有数据反复的交加。
- 给每一块创建对象独自存储到数组当中
- 查找数据的时候，先在数组查，以后数据属于哪一块
- 再到这一块中程序查找
代码示例：
package com.itheima.search;
public class A03_BlockSearchDemo {public static void main(String[] args) {
/*
分块查找
核心思想：块内无序，块间有序
实现步骤：1. 创立数组 blockArr 寄存每一个块对象的信息
2. 先查找 blockArr 确定要查找的数据属于哪一块
3. 再独自遍历这一块数据即可
*/
int[] arr = {16, 5, 9, 12,21, 18,
32, 23, 37, 26, 45, 34,
50, 48, 61, 52, 73, 66};
// 创立三个块的对象
Block b1 = new Block(21,0,5);
Block b2 = new Block(45,6,11);
Block b3 = new Block(73,12,17);
// 定义数组用来治理三个块的对象（索引表）Block[] blockArr = {b1,b2,b3};
// 定义一个变量用来记录要查找的元素
int number = 37;
// 调用办法，传递索引表，数组，要查找的元素
int index = getIndex(blockArr,arr,number);
// 打印一下
System.out.println(index);
}
// 利用分块查找的原理，查问 number 的索引
private static int getIndex(Block[] blockArr, int[] arr, int number) {
//1. 确定 number 是在那一块当中
int indexBlock = findIndexBlock(blockArr, number);
if(indexBlock == -1){
// 示意 number 不在数组当中
return -1;
}
//2. 获取这一块的起始索引和完结索引 --- 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 在哪一块当中
public static int findIndexBlock(Block[] blockArr,int number){ //100
// 从 0 索引开始遍历 blockArr，如果 number 小于 max，那么就示意 number 是在这一块当中的
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;// 完结索引
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;}
/**
* 设置
* @param max
*/
public void setMax(int max) {this.max = max;}
/**
* 获取
* @return startIndex
*/
public int getStartIndex() {return startIndex;}
/**
* 设置
* @param startIndex
*/
public void setStartIndex(int startIndex) {this.startIndex = startIndex;}
/**
* 获取
* @return endIndex
*/
public int getEndIndex() {return endIndex;}
/**
* 设置
* @param endIndex
*/
public void setEndIndex(int endIndex) {this.endIndex = endIndex;}
public String toString() {return "Block{max =" + max + ", startIndex =" + startIndex + ", endIndex =" + endIndex + "}";
}
}6. 哈希查找
哈希查找是分块查找的进阶版，实用于数据一边增加一边查找的状况。
个别是数组 + 链表的结合体或者是数组 + 链表 + 红黑树的结合体
在课程中，为了让大家不便了解，所以规定：
- 数组的 0 索引处存储 1~100
- 数组的 1 索引处存储 101~200
- 数组的 2 索引处存储 201~300
- 以此类推
然而实际上，咱们个别不会采取这种形式，因为这种形式容易导致一块区域增加的元素过多，导致效率偏低。
更多的是先计算出以后数据的哈希值，用哈希值跟数组的长度进行计算，计算出应存入的地位，再挂在数组的前面造成链表，如果挂的元素太多而且数组长度过长，咱们也会把链表转化为红黑树，进一步提高效率。
具体的过程，大家能够参见 B 站阿玮解说课程：从入门到腾飞。在汇合章节具体解说了哈希表的数据结构。全程采取动画模式解说，让大家高深莫测。
在此不多做论述。
7. 树表查找
本知识点波及到数据结构：树。
倡议先看一下前面阿玮解说的数据结构，再回头了解。
根本思维：二叉查找树是先看待查找的数据进行生成树，确保树的左分支的值小于右分支的值，而后在就行和每个节点的父节点比拟大小，查找最适宜的范畴。这个算法的查找效率很高，然而如果应用这种查找办法要首先创立树。
二叉查找树（BinarySearch Tree，也叫二叉搜寻树，或称二叉排序树 Binary Sort Tree），具备下列性质的二叉树：
1）若任意节点左子树上所有的数据，均小于自身；
2）若任意节点右子树上所有的数据，均大于自身；
二叉查找树性质：对二叉查找树进行中序遍历，即可失去有序的数列。
不同状态的二叉查找树如下图所示：
基于二叉查找树进行优化，进而能够失去其余的树表查找算法，如均衡树、红黑树等高效算法。
具体细节大家能够参见 B 站阿玮解说课程：从入门到腾飞。在汇合章节具体解说了树数据结构。全程采取动画模式解说，让大家高深莫测。
在此不多做论述。
不论是二叉查找树，还是均衡二叉树，还是红黑树，查找的性能都比拟高
十大排序算法：
1. 冒泡排序
冒泡排序（Bubble Sort）也是一种简略直观的排序算法。
它反复的遍历过要排序的数列，一次比拟相邻的两个元素，如果他们的程序谬误就把他们替换过去。
这个算法的名字由来是因为越大的元素会经由替换缓缓 ” 浮 ” 到最初面。
当然，大家能够依照从大到小的形式进行排列。
1.1 算法步骤
- 相邻的元素两两比拟，大的放左边，小的放右边
- 第一轮比拟结束之后，最大值就曾经确定，第二轮能够少循环一次，前面以此类推
- 如果数组中有 n 个数据，总共咱们只有执行 n - 1 轮的代码就能够
1.2 动图演示
1.3 代码示例
public class A01_BubbleDemo {public static void main(String[] args) {
/*
冒泡排序：核心思想：1，相邻的元素两两比拟，大的放左边，小的放右边。2，第一轮比拟结束之后，最大值就曾经确定，第二轮能够少循环一次，前面以此类推。3，如果数组中有 n 个数据，总共咱们只有执行 n - 1 轮的代码就能够。*/
//1. 定义数组
int[] arr = {2, 4, 5, 3, 1};
//2. 利用冒泡排序将数组中的数据变成 1 2 3 4 5
// 外循环：示意我要执行多少轮。如果有 n 个数据，那么执行 n - 1 轮
for (int i = 0; i < arr.length - 1; i++) {
// 内循环：每一轮中我如何比拟数据并找到以后的最大值
//-1：为了避免索引越界
//-i：提高效率，每一轮执行的次数应该比上一轮少一次。for (int j = 0; j < arr.length - 1 - i; j++) {
//i 顺次示意数组中的每一个索引：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. 遍历数组
for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");
}
System.out.println();}
}2. 抉择排序
2.1 算法步骤
- 从 0 索引开始，跟前面的元素一一比拟
- 小的放后面，大的放前面
- 第一次循环完结后，最小的数据曾经确定
- 第二次循环从 1 索引开始以此类推
- 第三轮循环从 2 索引开始以此类推
- 第四轮循环从 3 索引开始以此类推。
2.2 动图演示
public class A02_SelectionDemo {public static void main(String[] args) {
/*
抉择排序：1，从 0 索引开始，跟前面的元素一一比拟。2，小的放后面，大的放前面。3，第一次循环完结后，最小的数据曾经确定。4，第二次循环从 1 索引开始以此类推。*/
//1. 定义数组
int[] arr = {2, 4, 5, 3, 1};
//2. 利用抉择排序让数组变成 1 2 3 4 5
/* // 第一轮：// 从 0 索引开始，跟前面的元素一一比拟。for (int i = 0 + 1; i < arr.length; i++) {
// 拿着 0 索引跟前面的数据进行比拟
if(arr[0] > arr[i]){int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
}
}*/
// 最终代码：// 外循环：几轮
//i: 示意这一轮中，我拿着哪个索引上的数据跟前面的数据进行比拟并替换
for (int i = 0; i < arr.length -1; i++) {
// 内循环：每一轮我要干什么事件？// 拿着 i 跟 i 前面的数据进行比拟替换
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. 遍历数组
for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");
}
System.out.println();}
}
3. 插入排序
插入排序的代码实现尽管没有冒泡排序和抉择排序那么简略粗犷，但它的原理应该是最容易了解的了，因为只有打过扑克牌的人都应该可能秒懂。插入排序是一种最简略直观的排序算法，它的工作原理是通过创立有序序列和无序序列，而后再遍历无序序列失去外面每一个数字，把每一个数字插入到有序序列中正确的地位。
插入排序在插入的时候，有优化算法，在遍历有序序列找正确地位时，能够采取二分查找
3.1 算法步骤
将 0 索引的元素到 N 索引的元素看做是有序的，把 N + 1 索引的元素到最初一个当成是无序的。
遍历无序的数据，将遍历到的元素插入有序序列中适当的地位，如遇到雷同数据，插在前面。
N 的范畴：0~ 最大索引
3.2 动图演示
package com.itheima.mysort;
public class A03_InsertDemo {public static void main(String[] args) {
/*
插入排序：将 0 索引的元素到 N 索引的元素看做是有序的，把 N + 1 索引的元素到最初一个当成是无序的。遍历无序的数据，将遍历到的元素插入有序序列中适当的地位，如遇到雷同数据，插在前面。N 的范畴：0~ 最大索引
*/
int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
//1. 找到无序的哪一组数组是从哪个索引开始的。2
int startIndex = -1;
for (int i = 0; i < arr.length; i++) {if(arr[i] > arr[i + 1]){
startIndex = i + 1;
break;
}
}
//2. 遍历从 startIndex 开始到最初一个元素，顺次失去无序的哪一组数据中的每一个元素
for (int i = startIndex; i < arr.length; i++) {
// 问题：如何把遍历到的数据，插入到后面有序的这一组当中
// 记录以后要插入数据的索引
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. 遍历数组
for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");
}
System.out.println();}
}
4. 疾速排序
疾速排序是由东尼·霍尔所倒退的一种排序算法。
疾速排序又是一种分而治之思维在排序算法上的典型利用。
疾速排序的名字起的是简略粗犷，因为一听到这个名字你就晓得它存在的意义，就是快，而且效率高！
它是解决大数据最快的排序算法之一了。
4.1 算法步骤
- 从数列中挑出一个元素，个别都是右边第一个数字，称为 “ 基准数 ”;
- 创立两个指针，一个从前往后走，一个从后往前走。
- 先执行前面的指针，找出第一个比基准数小的数字
- 再执行后面的指针，找出第一个比基准数大的数字
- 替换两个指针指向的数字
- 直到两个指针相遇
- 将基准数跟指针指向地位的数字替换地位，称之为：基准数归位。
- 第一轮完结之后，基准数右边的数字都是比基准数小的，基准数左边的数字都是比基准数大的。
- 把基准数右边看做一个序列，把基准数左边看做一个序列，依照刚刚的规定递归排序
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 索引的数字为基准数，确定基准数在数组中正确的地位。比基准数小的全副在右边，比基准数大的全副在左边。前面以此类推。*/
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();}*/
long start = System.currentTimeMillis();
quickSort(arr, 0, arr.length - 1);
long end = System.currentTimeMillis();
System.out.println(end - start);//149
System.out.println(Arrays.toString(arr));
// 课堂练习：// 咱们能够利用雷同的方法去测试一下，抉择排序，冒泡排序以及插入排序运行的效率
// 失去一个论断：疾速排序真的十分快。/* for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");
}*/
}
/*
* 参数一：咱们要排序的数组
* 参数二：要排序数组的起始索引
* 参数三：要排序数组的完结索引
* */
public static void quickSort(int[] arr, int i, int j) {
// 定义两个变量记录要查找的范畴
int start = i;
int end = j;
if(start > end){
// 递归的进口
return;
}
// 记录基准数
int baseNumber = arr[i];
// 利用循环找到要替换的数字
while(start != end){
// 利用 end，从后往前开始找，找比基准数小的数字
//int[] arr = {1, 6, 2, 7, 9, 3, 4, 5, 10, 8};
while(true){if(end <= start || arr[end] < baseNumber){break;}
end--;
}
System.out.println(end);
// 利用 start，从前往后找，找比基准数大的数字
while(true){if(end <= start || arr[start] > baseNumber){break;}
start++;
}
// 把 end 和 start 指向的元素进行替换
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
// 当 start 和 end 指向了同一个元素的时候，那么下面的循环就会完结
// 示意曾经找到了基准数在数组中应存入的地位
// 基准数归位
// 就是拿着这个范畴中的第一个数字，跟 start 指向的元素进行替换
int temp = arr[i];
arr[i] = arr[start];
arr[start] = temp;
// 确定 6 右边的范畴，反复刚刚所做的事件
quickSort(arr,i,start - 1);
// 确定 6 左边的范畴，反复刚刚所做的事件
quickSort(arr,start + 1,j);
}
}本文参加了 SegmentFault 思否面试闯关挑战赛，欢送正在浏览的你也退出。
