数组之Arrays工具类和算法
工具类方法一般是静态的,可以用类名直接来调用
java已经封装好了有一套类库,直接来调用
Arrays工具类(java.util.Arrays)
开发时参考API帮助文档。不需要死记硬背
所有方法是静态的,可以用类名Arrays直接来调用
import java.util.Arrays;//导包
public class Erfen {
public static void main(String[] args) {
int[] arr = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
//利用Arrays工具类中的sort方法排序(默认从小到大排序)
Arrays.sort(arr);
for(int i=0;i<arr.length;i++) {
System.out.println(arr[i]);
}
//二分法查找(基于排序的基础上),返回值是要查询的元素的下标
int index=Arrays.binarySearch(arr,18);
System.out.println(index==-1?"该元素不存在":"该元素的下标是:"+index);
}
以下算法直接理解理论,实际开发有现成的方法调用
冒泡排序
在每一趟中,数据两两比较,不符合就交换,每一趟就选出一个最大值排在最后,同时它也不参与下一趟排序
趟数:length-1
每趟比较次数:趟数减1,i-1
int arr[]= {1,3,6,2,7};
//注意外层循环的写法,控制趟数,从0 到length-1,因为内层是控制每一趟比较的次数从0到i-1
for(int i=arr.length-1;i>0;i--) {
for(int j=0;j<i;j++) {
if(arr[j]>arr[j+1]) {//升序排序
int t;
t = arr[j];
arr[j]=arr[j+1];
arr[j+1]=t;
}
}
}
//输出结果,遍历数组
for(int i=0;i<arr.length;i++) {
System.out.println(arr[i]);
//1 2 3 6 7
}
选择排序
其比冒泡排序的交换位置是有意义的
每循环一次,从“ 参与比较的” 这堆数据中的最小值和最前面的数字交换位置
最小值不再参与下一次循环,然后在剩下的数据中再选出最小值....
关键是找出一堆数据的最小的:假设初始比较起点是最小的,依次和后面的数比较,若有比他小的,更新最小值
int a[]= {1,3,6,2,7};
/*排序过程:
* 1,3,6,2,7
* 在3,6,2,7中找到最小的2,2和3交换
* 1,2,6,3,7,在6,3,7中找到最小的3,交换6和3*/
for(int i=0;i<a.length-1;i++) {
//外层控制循环的次数 共length-1
//i的值是0,1,2,3,正好是“参与比较的数据中最左边的元素的下标”
//则i 就是每次要比较大小的数据中的起点,则下个数从i+1与它比较
//假设起点下标i所对应的数是最小的
int min = i;
for(int j=i+1;j<a.length;j++) {
if(a[j]<a[min]) {
min = j;
}
}
//说明在某一次比较中,起点下标所对应的数据并不是最小的
// 要交换二者,a[min]是最小的 , a[i]是起始数据
if(min!=i) {
int t;
t=a[min];
a[min]=a[i];
a[i]=t;
}
}
//输出结果,遍历数组
for(int i=0;i<a.length;i++) {
System.out.println(a[i]);
//1 2 3 6 7
}
二分法查找(基于排序的基础上)
思路:
/*在数组中找出18:
* 10 11 12 13 14 15 16 17 18 19 20
* 首先找出下标:(0+10)/2=5 就是数组中的15
* 15<18 ,则在15的右边找,开始的元素下标是5+1,再重新计算一个新的中间下标
* 则(6+10)/2=8 就是数组中的18
* */
public class Erfen {
// 二分法查找:在数组中找出18的下标
public static void main(String[] args) {
int[] arr = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
int index = binarySearch(arr, 18);
System.out.println(index == -1 ? "该元素不存在!" : "该元素的下标" + index);
//该元素的下标8
}
//从数组中查找目标元素的下标的方法:
// 形参:arr是被查找的数组,dest是要查找的目标元素
// 返回值:-1表示该元素不存在,其他表示该元素的下标
public static int binarySearch(int[] arr, int dest) {
// 开始元素下标
int begin = 0;
// 结束元素下标
int end = arr.length - 1;
// 中间元素下标
while (begin <= end) {
int mid = (begin + end) / 2;//放在while循环里面
if (arr[mid] == dest) {
return mid;
} else if (arr[mid] < dest) {
// 目标元素在中间元素的右边,开始元素的下标是mid+1
begin = mid + 1;
} else {
// 目标元素在中间元素的右边,结束元素的下标是mid-1
end = mid - 1;
}
}
return -1;
}
}