本文介绍: ②初始,low=0,high=arr.length-1,mid=(low+high)/2。Java中实际上已经封装好了这些算法,例如Java中提供的一个数组工具类:java.util.Arrays中有一个静态方法sort方法。①设表长n,设置指针low,high和mid分别指向待查元素所在区间的上界、下界和中点,key为要查找的值。—若key=R[mid].key,low=mid+1。—若key==R[mid].key,查找成功。
常见的算法
-
Java中实际上已经封装好了这些算法,例如Java中提供的一个数组工具类:java.util.Arrays中有一个静态方法sort方法。
-
对于其中的一些原理请阅读数据结构学习笔记:
①查找算法:数据结构学习第七章查找
②排序算法:数据结构学习第八章排序
7.冒泡排序算法
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {2,5,23,52,1,34};
for (int i = 0; i < arr.length; i++) {
System.out.printf(String.valueOf(arr[i]) + " "); //2 5 23 52 1 34
}
//冒泡排序实现从小到大排序
for (int i = arr.length-1; i >0; i--) {
for (int j = 0; j < i; j++) {
if(arr[j] > arr[j+1]){
int temp;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1]=temp;
}
} }
System.out.println();
for (int i = 0; i < arr.length; i++) {
System.out.printf(String.valueOf(arr[i]) + " "); //1 2 5 23 34 52
}
}
}
8.选择排序算法
public class SelectSort {
public static void main(String[] args) {
int[] arr = {2,5,23,52,1,34};
for (int i = 0; i < arr.length; i++) {
System.out.printf(String.valueOf(arr[i]) + " "); //2 5 23 52 1 34
}
//从小到大选择排序
for (int i = 0; i < arr.length; i++) {
//记录最小值下标为:第一个元素
int min = i;
for (int j = i+1; j < arr.length; j++) {
if(arr[j]<arr[min]){
//遍历后面的元素,如果元素小于最小值,更新最小值下标
min = j;
}
}
//遍历完后面的元素,如果最小值有变,这需要更换位置。
if(min != i){
int temp;
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
System.out.println();
for (int i = 0; i < arr.length; i++) {
System.out.printf(String.valueOf(arr[i]) + " "); //1 2 5 23 34 52
}
}
}
9.二分查找
public class ArraySearch {
public static void main(String[] args) {
int[] arr = {2,5,23,52,1,34};
int index = Search(arr,52);
System.out.println(index == -1 ? "该元素不存在!" : "该元素下标是:" + index); //该元素下标是:3
int index2 = Search(arr,100);
System.out.println(index2 == -1 ? "该元素不存在!" : "该元素下标是:" + index2); //该元素不存在!
}
public static int Search(int[] arr,int index){
for (int i = 0; i < arr.length; i++) {
if(arr[i] == index){
return i;//结束当前方法
}
}
return -1;
}
}
-
二分法查找核心思想:
①设表长n,设置指针low,high和mid分别指向待查元素所在区间的上界、下界和中点,key为要查找的值。
②初始,low=0,high=arr.length-1,mid=(low+high)/2。(注:由于计算机存储原理,若mid有小数部分,则向下取整数)
public class ArraySearchTwo {
public static void main(String[] args) {
int[] arr = {100,200,235,600,1000,2000,9999 };
//找出arr这个数组中2000所在的下标
int index = binarySeary(arr,2000);
System.out.println(index == -1 ? "该元素不存在" : "该元素的下标为:" + index);//该元素的下标为:5
int index2 = binarySeary(arr,300);
System.out.println(index2 == -1 ? "该元素不存在" : "该元素的下标为:" + index2);//该元素不存在
}
private static int binarySeary(int[] arr, int dest) {
//开始下标low
int low = 0;
//结束下标high
int high = arr.length -1;
while(low <= high){
int mid = (low + high) / 2;
if(arr[mid] == dest){
return mid;
} else if (arr[mid] < dest) {
//目标在中间的右边,开始元素下标low变化
low = mid + 1;
}else {
//目标在中间的右边,结束下标high变化
high = mid - 1;
}
}
return -1;
}
}
10. Arrays工具类使用
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {3,6,45,21,47,51,31,4,7};
//使用工具类排序
Arrays.sort(arr);
//输出排序好的结果
for (int i = 0; i < arr.length; i++) {
System.out.printf(arr[i] + " "); //3 4 6 7 21 31 45 47 51
}
System.out.println();
//二分查找(需要已经排序好的数组),使用工具类
int index = Arrays.binarySearch(arr,45);
System.out.println(index == -1 ? "该元素不存在" : "该元素下标:"+index); //该元素下标:6
}
}
原文地址:https://blog.csdn.net/weixin_46016581/article/details/134777149
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_39896.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。