Java使用二分法进行查找和排序的示例
作者:匆忙拥挤repeat 发布时间:2023-03-16 10:16:37
实现二分法查找
二分法查找,需要数组内是一个有序的序列
二分查找比线性查找:数组的元素数越多,效率提高的越明显
二分查找的效率表示:O(log2N) N在2的M次幂范围,那查找的次数最大就是M, log2N表示2的M次幂等于N, 省略常数,简写成O(logN)
如有一个200个元素的有序数组,那么二分查找的最大次数:
2^7=128, 2^8=256, 可以看出7次幂达不到200,8次幂包括, 所以最大查找次数就等于8
//循环,二分查找
static int binarySearch(int[] array, int data) {
int start = 0;
int end = array.length - 1;
int mid = -1;
while (start <= end) {
System.out.println("查找次数");
mid = (start + end) >>> 1;
if (array[mid] < data) {
start = mid + 1;
} else if (array[mid] > data) {
end = mid - 1;
} else {
return mid;
}
System.out.println("start=" + start+",end="+end+",mid="+mid);
}
return -1;
}
//递归二分查找 初始start=0, end = array.length - 1
static int binarySearch4Recursion(int[] array, int data, int start, int end) {
int mid = -1;
System.out.println("查找次数");
if (start > end) {
return mid;
}
mid = (start + end) >>> 1;
if (array[mid] < data) {
return binarySearch4Recursion(array, data, mid + 1, end);
} else if (array[mid] > data) {
return binarySearch4Recursion(array, data, start, mid - 1);
} else {
return mid;
}
}二分法插入排序
设有一个序列a[0],a[1]...a[n];其中a[i-1]前是已经有序的,当插入时a[i]时,利用二分法搜索a[i]插入的位置
效率:O(N^2),对于初始基本有序的序列,效率上不如直接插入排序;对于随机无序的序列,效率比直接插入排序要高
/*
* 二分(折半)插入排序
* 设有一个序列a[0],a[1]...a[n];其中a[i-1]前是已经有序的,当插入时a[i]时,利用二分法搜索a[i]插入的位置
*/
public class BinaryInsertSort {
public static void main(String[] args) {
int len = 10;
int[] ary = new int[len];
Random random = new Random();
for (int j = 0; j < len; j++) {
ary[j] = random.nextInt(1000);
}
binaryInsert(ary);
/*
* 复杂度分析: 最佳情况,即都已经排好序,则无需右移,此时时间复杂度为:O(n lg n) 最差情况,全部逆序,此时复杂度为O(n^2)
* 无法将最差情况的复杂度提升到O(n|logn)。
*/
// 打印数组
printArray(ary);
}
/**
* 插入排序
* @param ary
*/
private static void binaryInsert(int[] ary) {
int setValueCount = 0;
// 从数组第二个元素开始排序,因为第一个元素本身肯定是已经排好序的
for (int j = 1; j < ary.length; j++) {// 复杂度 n
// 保存当前值
int key = ary[j];
// ∆ 利用二分查找定位插入位置
// int index = binarySearchAsc(ary, ary[j], 0, j - 1);// 复杂度:O(logn)
// int index = binarySearchDesc(ary, ary[j], 0, j - 1);// 复杂度:O(logn)
int index = binarySearchDesc2(ary, ary[j], 0, j - 1);// 复杂度:O(logn)
printArray(ary);
System.out.println("第" + j +"个索引上的元素要插入的位置是:" + index);
// 将目标插入位置,同时右移目标位置右边的元素
for (int i = j; i > index; i--) {// 复杂度,最差情况:(n-1)+(n-2)+...+n/2=O(n^2)
ary[i] = ary[i - 1]; //i-1 <==> index
setValueCount++;
}
ary[index] = key;
setValueCount++;
}
System.out.println("\n 设值次数(setValueCount)=====> " + setValueCount);
}
/**
* 二分查找 升序 递归
*
* @param ary
* 给定已排序的待查数组
* @param target
* 查找目标
* @param from
* 当前查找的范围起点
* @param to
* 当前查找的返回终点
* @return 返回目标在数组中,按顺序应在的位置
*/
private static int binarySearchAsc(int[] ary, int target, int from, int to) {
int range = to - from;
// 如果范围大于0,即存在两个以上的元素,则继续拆分
if (range > 0) {
// 选定中间位
int mid = (to + from) / 2;
// 如果临界位不满足,则继续二分查找
if (ary[mid] > target) {
/*
* mid > target, 升序规则,target较小,应交换位置 前置, 即target定位在mid位置上,
* 根据 查找思想, 从from到 mid-1认为有序, 所以to=mid-1
*/
return binarySearchAsc(ary, target, from, mid - 1);
} else {
/*
* mid < target, 升序规则,target较大,不交换位置,查找比较的起始位置应为mid+1
*/
return binarySearchAsc(ary, target, mid + 1, to);
}
} else {
if (ary[from] > target) {//如 5,4, 要插入的是4
return from;
} else {
return from + 1;
}
}
}
/**
* 二分查找 降序, 递归
*/
private static int binarySearchDesc(int[] ary, int target, int from, int to) {
int range = to - from;
if (range > 0) {
int mid = (from + to) >>> 1;
if (ary[mid] > target) {
return binarySearchDesc(ary, target, mid + 1, to);
} else {
return binarySearchDesc(ary, target, from, mid - 1);
}
} else {
if (ary[from] > target) {//如 5,4, 要插入的是4
return from + 1;
} else {
return from;
}
}
}
/**
* 二分查找 降序, 非递归
*/
private static int binarySearchDesc2(int[] ary, int target, int from, int to) {
// while(from < to) {
for (; from < to; ) {
int mid = (from + to) >>> 1;
if (ary[mid] > target) {
from = mid + 1;
} else {
to = mid -1;
}
}
//from <==> to;
if (ary[from] > target) {//如 5,4, 要插入的是4
return from + 1;
} else {
return from;
}
}
private static void printArray(int[] ary) {
for (int i : ary) {
System.out.print(i + " ");
}
}
}
打印
918 562 442 531 210 216 931 706 333 132 第1个索引上的元素要插入的位置是:1
918 562 442 531 210 216 931 706 333 132 第2个索引上的元素要插入的位置是:2
918 562 442 531 210 216 931 706 333 132 第3个索引上的元素要插入的位置是:2
918 562 531 442 210 216 931 706 333 132 第4个索引上的元素要插入的位置是:4
918 562 531 442 210 216 931 706 333 132 第5个索引上的元素要插入的位置是:4
918 562 531 442 216 210 931 706 333 132 第6个索引上的元素要插入的位置是:0
931 918 562 531 442 216 210 706 333 132 第7个索引上的元素要插入的位置是:2
931 918 706 562 531 442 216 210 333 132 第8个索引上的元素要插入的位置是:6
931 918 706 562 531 442 333 216 210 132 第9个索引上的元素要插入的位置是:9
设值次数(setValueCount)=====> 24
931 918 706 562 531 442 333 216 210 132
猜你喜欢
- 使用AS创建ADIL文件时AS会在main文件夹下给我们生成一个aidl文件夹和一个相同包名的包,通常我们会把所有和ADIL相关的类或文件放
- 背景实际开发中,常常需要将比较复杂的 JSON 字符串转换为对应的 Java 对象。这里记录下解决方案。如下所示,是入侵事件检测得到的 JS
- 概念在Java中,对象的生命周期包括以下几个阶段:创建阶段(Created)应用阶段(In Use)不可见阶段(Invisible)不可达阶
- Java包装类基本类型大小包装器类型boolean/Booleanchar16bitBooleanbyte8bitByteshort/16b
- 1. JSCH简介JSch 是SSH2的一个纯Java实现。它允许你连接到一个sshd 服务器,使用端口转发,X11转发,文件传输等等。你可
- Java Memory Model简称JMM, 是一系列的Java虚拟机平台对开发者提供的多线程环境下的内存可见性、是否可以重排序等问题的无
- Json的简介JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。它基于ECMAScript的一个
- 有时候编译器、处理器的优化会导致runtime与我们设想的不一样,为此Java对编译器和处理器做了一些限制,JAVA内存模型(JMM)将这些
- 前言最近参加了21天打卡活动,希望可以让自己养成写博客的习惯…ArrayList和LinkedListArrayLis
- 在使用springmvc的时候,后台@RequestBody接受的是一个json格式的字符串,一定是一个字符串。我们可以通过@Request
- java Mybatis存进时间戳封装了一个实体类,里面有个字段 Integer createTime。要利用这个实体类将一个时间戳存进数据
- 简介对于一个APP来说,肯定会有一个AppBar,这个AppBar一般包含了APP的导航信息等。虽然我们可以用一个固定的组件来做为AppBa
- 前言目前正在做的项目,为了增加用户的体验度,准备增加一些动画效果,其中底部栏中间按钮的点击事件参考了闲鱼的动效,便在此基础上仿写了该动效,并
- Java 用反射设置对象的属性值实例详解/** * 用反射设置对象的属性值 * @param obj 需要設置值的對象 * @param f
- 最近开发项目中,有个在屏幕上任意拖动的悬浮窗功能,其实就是利用 WindowManager的api来完成这个需求,具体的实现的功能如下:1.
- 引言在学习Java过程中,排序sort是我们常用的功能;在Java里,数组有Arrays.sort()可以排序,集合则是Collection
- 面试中可能会被问到为什么我们调用start()方法时会执行run()方法,为什么我们不能直接调用run()方法?Java 创建线程的方法实际
- File类概述File类能新建、删除、重命名文件和目录,但不能访问文件内容本身,如果需要访问文件内容本身,则需要使用后续的输入/输出流。要在
- 将图片上传到webapp路径下 路径获取方式此方法获取到工程webapp文件夹下String contexPath= request.get
- 导语相信大家无论是做前端还是做后端的,都被接口接口文档所折磨过,前端抱怨接口文档和后端给的不一致,后端抱怨写接口文档很麻烦,所以Swagge