选择排序、冒泡排序、二分查找法

一、选择排序：数组中的每个元素和其他元素进行比较换位置

比较示例：

arr[0]   arr[1]
arr[0]   arr[2]
arr[0]   arr[3]
arr[1]   arr[2]
arr[1]   arr[3]
arr[2]   arr[3]
           

可以看出，选择排序是先通过首个元素依次跟后面的元素进行比较

代码示例：

//选择排序
	public static void selectSort(int[] arr){
		for(int i=0;i<arr.length-1;i++){
			for(int j=i+1;j<arr.length;j++){
				if(arr[i]>arr[j]){
					//数组换位
					int temp = arr[i];
					arr[i]=arr[j];
					arr[j]=temp;
				}
			}
		}
	}
           

二、数组的冒泡排序：数组的相邻元素换位置

arr[0] arr[1]
arr[1] arr[2]
arr[2] arr[3]

arr[0] arr[1]

arr[1] arr[2]
           

冒泡排序是通过相邻元素之间的比较来排序的

代码示例：

//冒泡排序
	public static void bubbleSort(int[] arr){
		for(int i=0;i<arr.length-1;i++){
			//每次的内循环的比较从0索引开始，每次都在递减
			for(int j=0;j<arr.length-i-1;j++){
				//比较的索引是j和j+1
				if(arr[j]>arr[j+1]){
					int temp = arr[j];
					arr[j]=arr[j+1];
					arr[j+1] =temp;
				}
			}
		}
		
	}
           

三、二分查找法：(折半查找)

前提：被查找的数组中的元素必须是有序的

中间索引计算：

(max+min)/2

指针思想：

折半后的指针索引和被查找元素比较

元素>中间索引上的元素  小指针=中间+1
	元素<中间索引上的元素  大指针=中间-1
	小指针索引>大指针索引，结束
	没找到，返回-1的索引
	元素==数组中间索引上的元素，结束
	返回结果就是中间索引
           

代码示例：

/*
		折半查找
		返回值：索引
		参数：数组，被查找的元素
	*/
	public static int binarySearch(int[] arr,int key){
		//定义三个指针变量
		int min=0;
		int max=arr.length-1;
		int mid = 0;
		//循环折半，条件min<=max
		while(min<=max){
			//公式，计算中间索引
			mid=(min+max)/2;
			//让被找元素，和中间索引元素进行比较
			if(key >arr[mid]){
				min=mid+1;
			}else if(key<arr[mid]){
				max=mid-1;
			}else{
				//找到元素，返回元素索引
				return mid;
			}
		}
		//没有找到元素，返回-1
		return -1;
	}