常用算法.md

##常用算法 ###排序

冒泡排序

冒泡：比较两个相邻的数：左边小，右边大

• 算法实现

冒泡排序：比较相邻的两个数，小的在左边，大的在右边
public static void bubbleSort(int[] a){
	for(int i = 0;i<a.length-1;i++){  //比较的趟数
		for(int j = 0 ; j <a.length-1-i;j++){ //每一趟比较的次数
			if(a[j]>a[j+1]){
				int t = a[j];
				a[j] = a[j+1];
				a[j+1]= t;
			}
		}	
	}
}

选择排序

选择：每趟基准值，用于存储最小

• 算法实现

public static void selectSort1(int[] a){
	for(int i=0;i<a.length-1;i++){
		for(int j=i+1;j<a.length;j++){
			if(a[i]>a[j]){
				int t = a[i];
				a[i] = a[j];
				a[j] = t;
			}
		}
	}

选择排序---增强版 效率高（建议使用）

public static void selectSort(int[] a){
	for(int i=0;i<a.length-1;i++){
		int minIndex = i ; //最小值的下标
		for(int j = i+1 ;j<a.length;j++){
			if(a[minIndex]>a[j]){
				minIndex = j;
			}
		}
		//循环结束
		if(minIndex!=i){
			int t = a[i];
			a[i] = a[minIndex];
			a[minIndex] = t;
		}
	}
}

插入排序

插入：从第二个数值开始，向前边的数列插入保持原有的顺序

• 算法实现

//插入排序：默认左边的数是有序的
public static void insertSort(int[] a){
	for(int i = 1 ; i<a.length ; i++){
		for(int j=i;j>0;j--){
			if(a[j]<a[j-1]){//保证左边的为最小的数
				int t = a[j];
				a[j] = a[j-1];
				a[j-1] = t;
			}else{
				break;//如果当前值比左边的值大，则不需要比较
			}
		}
	}
}

---

###查找

顺序查找

顺序：挨个比较

• 算法实现

顺序查找:如果找到了，返回对应的下标，如果没有找到返回-1

/*
顺序查找：如果出现了数组中元素重复的情况，不保证找到的是哪一个
 */
static int find(int[] a,int key){
	for(int i=0;i<a.length;i++){
		if(a[i]==key){ //找到了，返回下标
			return i;
		}
	}
	return -1;
}

二分法查找

二分：前提:有序 折半查找

• 算法实现

/*
二分法查找：前提：必须数组有序
确定中间位置：
*/
static  int binaryFind(int[] a,int key){
	int low = 0 ;
	int high = a.length - 1;
	int mid = 0;
	while(low<=high){
		mid = (low+high)/2;//也可以这样写：mid = (low+high)>>1;
		if(a[mid]>key){ //左边区域查找
			high = mid - 1;
		}
		else if(a[mid]<key){ //右边区域查找
			low = mid + 1;			
		}
		else{
			return mid; //找到了
		}
	}
	return  -1;  //没有找到
}