常用算法.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;  //没有找到
    }