郑州做网站哪家最好,wordpress 极简 文字,女人和男人做床上爱网站,买空间的网站好常见的七种查找算法#xff1a;
数据结构是数据存储的方式#xff0c;算法是数据计算的方式。所以在开发中#xff0c;算法和数据结构息息相关。今天的讲义中会涉及部分数据结构的专业名词#xff0c;如果各位铁粉有疑惑#xff0c;可以先看一下哥们后面录制的数据结构…常见的七种查找算法
数据结构是数据存储的方式算法是数据计算的方式。所以在开发中算法和数据结构息息相关。今天的讲义中会涉及部分数据结构的专业名词如果各位铁粉有疑惑可以先看一下哥们后面录制的数据结构再回头看算法。
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 - 1max 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(lowhigh)/2, 即midlow1/2*(high-low);
我们可以将查找的点改进为如下
midlow(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--即下次循环,midf[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); ---- 2int 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 4if(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索引的元素看做是有序的把N1索引的元素到最后一个当成是无序的。
遍历无序的数据将遍历到的元素插入有序序列中适当的位置如遇到相同数据插在后面。
N的范围0~最大索引
3.2 动图演示 package com.itheima.mysort;public class A03_InsertDemo {public static void main(String[] args) {/*插入排序将0索引的元素到N索引的元素看做是有序的把N1索引的元素到最后一个当成是无序的。遍历无序的数据将遍历到的元素插入有序序列中适当的位置如遇到相同数据插在后面。N的范围0~最大索引*/int[] arr {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};//1.找到无序的哪一组数组是从哪个索引开始的。 2int 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);//149System.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);}
}} 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);}}
其他排序方式待更新~
