数组之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;
	}

}