Java学习笔记--数组常见算法:数组翻转,冒泡排序,二分查找

server/2024/11/24 0:39:44/

目录

一,数组翻转

二,冒泡排序

三,二分查找(一尺之锤,日取其半,万世不竭)


一,数组翻转

1.概述:数组对称索引位置上的元素互换,最大值数组序号是数组长度减一

创建跳板temp,进行min和max的互换,然后min自增,max自减,当min>=max的时候停止互换,代表到中间值

用代码实现

java">public class Demo01Reverse {public static void main(String[] args) {//定义一个静态数组 int arr [] ={1,2,3,4,5,6,7};for(int min=0,max = arr.length-1;min<max;min++,max--){//进行换位int temp = arr[min];arr[min]= arr[max];arr[max]= temp;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+" ");}}
}

二,冒泡排序


 数组的排序,是将数组中的元素按照大小进行排序,默认都是以升序的形式进行排序,数组排序的方法很多,我们讲解的是数组的冒泡排序。

  排序,都要进行数组 元素大小的比较,再进行位置的交换。冒泡排序法是采用数组中相邻元素进行比较换位。
  arr[i](前一个元素)   arr[i+1](后一个元素)

比如以下数组

5 4 3 2 1

进行0,1号位的数字比较

4 5 3 2 1

然后又进行1,2号位的数字比较

4 3 5 2 1

然后2,3号位比较

4 3 2 5 1

最后3,4号位比较

4 3 2 1 5

实现位置的交换依然和前面数组翻转一样,创建一个跳板temp进行交换

代码实现

首先,定义数组

java">public class Demo02Bubble {public static void main(String[] args) {int[] arr = {5,4,3,2,1};

进行第一轮冒泡

java">/* 第一圈 */for (int i = 0; i < arr.length; i++) {if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr [i+1];arr[i+1] = temp;}}

测试,出现警告

这是为什么呢

其实是循环的时候突破了数组的最大序号

因为arr.length就等于5,所以i能取到的最大值是4,所以i+1=5,突破了最大限制

改为arr.length-1

成功,然后进行第二圈

java">//第二圈for (int i = 0; i < arr.length-1; i++) {if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr [i+1];arr[i+1] = temp;}}

第二圈代码和第一圈一样,也没问题,但也和第一圈一样比较了4次,但我们可以不必做这个重复功,因为第一次比较完了一个数,所以我们可以减去一次循环来表示可以少比较的次数,所以可以写成arr.length-1-1,最后面减的这个数可以看成是前面冒泡过的数的个数(圈数)

java">//第二圈for (int i = 0; i < arr.length-1-1; i++) {if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr [i+1];arr[i+1] = temp;}}

现在进行第三圈第四圈,同样我们减去前面冒泡过的数的个数

java">//第三圈for (int i = 0; i < arr.length-1-2; i++) {if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr [i+1];arr[i+1] = temp;}}//第四圈for (int i = 0; i < arr.length-1-3; i++) {if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr [i+1];arr[i+1] = temp;}}

运行结果

但我们可以再进行优化,这几圈的变化非常细微,只有一个数一个位置在变

如果最后面减的数是前面的圈数的话,那也就等于i啊,我们可以再在外面套一层循环,利用自加i来代替这几圈唯一变的减数

java">/*
外层循环代表比较了几圈n-1圈
*/for (int j = 0; j < arr.length-1; j++) {for (int i = 0; i < arr.length-1-j; i++) {/*内层循环代表每一圈比较的次数每圈都少比较一次*/if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr [i+1];arr[i+1] = temp;}}}

由此而来,化繁为简,减小了时间,空间复杂度

完整代码如下

java">public class Demo02Bubble {public static void main(String[] args) {int[] arr = {5,4,3,2,1};/*第一圈越界原因:当i变化到4的时候-> arr[4]>arr[5] -> 直接操作了5索引,所以越界了越界解决:我们可以让arr.length-1如果arr.length-1-> 比较就是i<4 -> 此时i最大可以变化到3当i变化到3时 -> arr[3]>arr[4] -> 正好是最后两个元素进行比较*/for (int i = 0; i < arr.length-1-0; i++) {if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr [i+1];arr[i+1] = temp;}}//第二圈/*for (int i = 0; i < arr.length-1-1; i++) {if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr [i+1];arr[i+1] = temp;}}*///第三圈/*for (int i = 0; i < arr.length-1-2; i++) {if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr [i+1];arr[i+1] = temp;}}*///第四圈/*for (int i = 0; i < arr.length-1-3; i++) {if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr [i+1];arr[i+1] = temp;}}*//*外层循环代表比较了几圈n-1圈*/for (int j = 0; j < arr.length-1; j++) {for (int i = 0; i < arr.length-1-j; i++) {/*内层循环代表每一圈比较的次数每圈都少比较一次*/if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr [i+1];arr[i+1] = temp;}}}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+" ");}}
}

三,二分查找(一尺之锤,日取其半,万世不竭)

1.前提:数组中的数据必须是有序的
2.查询思想:
  a.老式查询:遍历数组,一个一个比较 -> 查询效率慢
  b.二分查找:每次找中间索引对应的元素进行比较查询(每一次查询少一半数据)

首先,因为min和max会因为查找数所在数组的位置不同而改变所以不能定义min就是arr[0]或max就是arr[8],min默认为0,max为arr.length-1,mid就是二者取中。

key为查询数,是指想查的数组中的数,查询出的是数组序数代表 含的数。

前提:当min<=max时

当查询数大于或小于数组序数上所代表的数时,通过移动min和max直接排掉一半的数,来不断的锁定范围,直到找到查询数所在的位置(这个方法很像一尺之锤,日取其半,万世不竭,不过是有目标的取),当查询数等于数组序数上所代表的数时,停止查找,返回序数表示找到了。

当然还有特殊情况,就是查询数不存在在数组中,那么当min>max时,就不找了,返回-1表示找不到。

代码实现

java">public static int binary(int[] arr,int data){//定义三个变量,分别代表最大索引,最小索引,中间索引int min = 0;int max = arr.length-1;int mid = 0;//查找while (min<=max){mid = (min+max)/2;if(data>arr[mid]){min = mid+1;}else if(data<arr[mid]){max = mid-1;}else{return mid;}}return -1;}

我们发现代码实现和理论方法步骤不同,没有在一开始表示mid = (min+max)/2,因为要循环的算中间索引,在一进入循环时,在while(外层循环)内,再进行计算。

在main函数内调用方法进行输出,完整代码如下

java">public class Demo03Binary {public static void main(String[] args) {int[] arr = {1,2,3,4,5,6,7,8,9};int index = binary(arr, 7);System.out.println(index);}public static int binary(int[] arr,int data){//定义三个变量,分别代表最大索引,最小索引,中间索引int min = 0;int max = arr.length-1;int mid = 0;//查找while (min<=max){mid = (min+max)/2;if(data>arr[mid]){min = mid+1;}else if(data<arr[mid]){max = mid-1;}else{return mid;}}return -1;}
}

输入7


http://www.ppmy.cn/server/144400.html

相关文章

PHP 数组

数组能存放多个值&#xff0c;需要在array()这个函数里存放&#xff0c;如果需要获取并使用&#xff0c;还需要用一个变量来存储。 <?php $color array("喜欢","黄色","跑车"); echo 我 . $color[0] . $color[1] . 的 . $color[2]; …

深入理解Rust的模式匹配

文章目录 基础用法匹配各种类型模式匹配赋值提取绑定值解构Option 高级用法添加匹配守卫范围匹配切片模式变量绑定使用..进行模糊匹配使用_进行值忽略固定某个字段的匹配多分支匹配 其它匹配方式if let匹配方式使用matches!宏进行匹配 在Rust编程语言中&#xff0c;模式匹配是一…

1、HCIP之RSTP协议与STP相关安全配置

目录 RSTP—快速生成树协议 STP STP的缺点&#xff1a; STP的选举&#xff08;Listening状态中&#xff09;&#xff1a; RSTP P/A&#xff08;提议/同意&#xff09;机制 同步机制&#xff1a; 边缘端口的配置&#xff1a; RSTP的端口角色划分&#xff1a; ensp模拟…

C++设计模式行为模式———中介者模式

文章目录 一、引言二、中介者模式三、总结 一、引言 中介者模式是一种行为设计模式&#xff0c; 能让你减少对象之间混乱无序的依赖关系。 该模式会限制对象之间的直接交互&#xff0c; 迫使它们通过一个中介者对象进行合作。 中介者模式可以减少对象之间混乱无序的依赖关系&…

蓝桥杯模拟

【问题描述】 如果一个数 p 是个质数&#xff0c;同时又是整数 a 的约数&#xff0c;则 p 称为 a 的一个质因数。 请问 2024 有多少个质因数。 【答案提交】 这是一道结果填空的题&#xff0c;你只需要算出结果后提交即可。本题的结果为一个整数&#xff0c;在提交答案时只…

2022 年中高职组“网络安全”赛项-海南省省竞赛任务书-1-B模块B-1-Windows操作系统渗透测试

前言 本章节我将带领大家一起重新模拟操作一次Windows渗透测试模块&#xff0c;并加固的流程。 任务概览 环境部署 我的实验复现环境&#xff1a; 服务器Windows server 2008 R2 攻击机Kali Linux 场景操作系统Windows 7 额外还有台交换机支持&#xff1a; 这里我使用的是…

Unreal从入门到精通之如何绘制用于VR的3DUI交互的手柄射线

文章目录 前言实现方式MenuLaser实现步骤1.Laser和Cursor2.移植函数3.启动逻辑4.检测射线和UI的碰撞5.激活手柄射线6.更新手柄射线位置7.隐藏手柄射线8.添加手柄的Trigger监听完整节点如下:效果图前言 之前我写过一篇文章《Unreal5从入门到精通之如何在VR中使用3DUI》,其中讲…

web——sqliabs靶场——第十二关——(基于错误的双引号 POST 型字符型变形的注入)

判断注入类型 a OR 1 1# 发现没有报错 &#xff0c;说明单引号不是闭合类型 测试别的注入条件 a) OR 1 1# a)) OR 1 1# a" OR 11 发现可以用双引号闭合 发现是")闭合 之后的流程还是与11关一样 爆破显示位 先抓包 是post传参&#xff0c;用hackbar来传参 unam…