Java中常见的查找算法与排序算法总结

返回列表 >> Java中常见的查找算法与排序算法总结

Java中常见的查找算法与排序算法总结

发布时间：2023-06-13

　　数据结构是数据存储的方式，算法是数据计算的方式。所以在开发中，算法和数据结构息息相关。今天的讲义中会涉及部分数据结构的专业名词，如果各位铁粉有疑惑，可以先看一下哥们后面录制的数据结构，再回头看算法。

1. 基本查找

　　也叫做顺序查找

　　说明：顺序查找适合于存储结构为数组或者链表。

　　基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线的一端开始，顺序扫描，依次将遍历到的结点与要查找的值相比较，若相等则表示查找成功；若遍历结束仍没有找到相同的，表示查找失败。

　　示例代码：

publicclassA01_BasicSearchDemo1 {

publicstaticvoidmain(String[] args) {

//基本查找/顺序查找

//核心：

//从0索引开始挨个往后查找

//需求：定义一个方法利用基本查找，查询某个元素是否存在

//数据如下：{131, 127, 147, 81, 103, 23, 7, 79}

int[] arr = {131, 127, 147, 81, 103, 23, 7, 79};

intnumber = 82;

System.out.println(basicSearch(arr, number));

}

//参数：

//一：数组

//二：要查找的元素

//返回值：

//元素是否存在

publicstaticbooleanbasicSearch(int[] arr, intnumber){

//利用基本查找来查找number在数组中是否存在

for(inti = 0; i < arr.length; i++) {

if(arr[i] == number){

returntrue;

}

returnfalse;

}

2. 二分查找

　　也叫做折半查找

　　说明：元素必须是有序的，从小到大，或者从大到小都是可以的。

　　如果是无序的，也可以先进行排序。但是排序之后，会改变原有数据的顺序，查找出来元素位置跟原来的元素可能是不一样的，所以排序之后再查找只能判断当前数据是否在容器当中，返回的索引无实际的意义。

　　基本思想：也称为是折半查找，属于有序查找算法。用给定值先与中间结点比较。比较完之后有三种情况：

　　相等

　　说明找到了

　　要查找的数据比中间节点小

　　说明要查找的数字在中间节点左边

　　要查找的数据比中间节点大

　　说明要查找的数字在中间节点右边

　　代码示例：

packagecom.itheima.search;

publicclassA02_BinarySearchDemo1 {

publicstaticvoidmain(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));

}

publicstaticintbinarySearch(int[] arr, intnumber){

//1.定义两个变量记录要查找的范围

intmin = 0;

intmax = arr.length - 1;

//2.利用循环不断的去找要查找的数据

while(true){

if(min > max){

return-1;

}

//3.找到min和max的中间位置

intmid = (min + max) / 2;

//4.拿着mid指向的元素跟要查找的元素进行比较

if(arr[mid] > number){

//4.1 number在mid的左边

//min不变，max = mid - 1；

max = mid - 1;

}elseif(arr[mid] < number){

//4.2 number在mid的右边

//max不变，min = mid + 1;

min = mid + 1;

}else{

//4.3 number跟mid指向的元素一样

//找到了

returnmid;

}

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的计算方式即可

　　代码示例：

注册即送1000元现金券

陆零云服务
3天无理由退款
24小时在线服务
在线服务
3分钟急速响应

服务支持: 服务保障; 代理分销; 投诉建议

陆零云: 联系我们; 公司简介; 代理分销

推荐链接: 网站运营; 常见问题; 行业新闻

365天无休服务 7x24小时在线

咨询热线： 800-886-6060

电子邮箱：admin@lu0.com

微信扫一扫关注公众号

常年法律顾问：可安律师事务所

陆零云客服中心

点击按钮可通过QQ进行沟通，请确认启动QQ

综合业务

客服①QQ咨询 客服②QQ咨询 客服③QQ咨询

多人值班加工单维护，为避免丢失消息，请尽量添加好友
业务咨询

在线咨询 在线咨询

业务相关，请咨询售前客服，为避免丢失消息，请尽量添加好友
售后支持

售后QQ技术 工单提交服务

售后问题处理，请QQ在线售后技术，或者提交服务请求，我们会尽全力解决您的问题
投诉/合作

大客户，代理申请联系 服务与合作

处理：投诉，建议，代理联系QQ：913603

负载均衡

云数据库

域名注册

常见问题

云计算