/**
 * @author
 */
public class Demo09 {
    public static void main(String[] args) {
	// 冒泡排序--基本實現(xiàn)
	//待排序的數(shù)組
	int[] arr = { 1, 3, 46, 22, 11 };
	//控制需要比較幾輪
	for (int i = 0; i < arr.length; i++) {
            //控制每一輪的比較次數(shù)
            for (int j = 0; j < arr.length - 1; j++) {
            //如果前面的比后面的數(shù)字大，則兩者就進(jìn)行交換
		if (arr[j] > arr[j + 1]) {
                    //兩數(shù)交換，需要一個“第三方”，好比兩杯水互換，需要第三個杯子。
                    //交換兩個變量的值，必須借助一個臨時變量。
                    //定義一個新的臨時變量，將數(shù)組中的前面的元素先賦值給臨時變量
                    int temp = arr[j];
                    //后面的值賦值到前面的位置上
                    arr[j] = arr[j + 1];
                    //再將臨時變量的值賦值到后面的位置上
                    arr[j + 1] = temp;
		}
            }
	}
	//遍歷排序后的數(shù)組
	for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i]+"\t");
	}
    }
}

/**
 * @author 
 */
public class Demo10 {
    public static void main(String[] args) {
	// 冒泡排序--優(yōu)化比較次數(shù)
	// 待排序數(shù)組
	int[] arr = { 1, 3, 46, 22, 11 };
	for(int j = 0; j < arr.length; j++) {//控制輪數(shù)
	    for(int i = 0; i < arr.length - 1 - j; i++) {//控制每一輪的次數(shù)
	        if(arr[i] > arr[i+1]) {
	            int temp = arr[i];
	            arr[i] = arr[i+1];
	            arr[i+1] = temp;
	        }
	    }
	}
        //遍歷排序后的數(shù)組
	for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i]+"\t");
	}
    }
}

/**
 * @author
 */
public class Demo11 {
    public static void main(String[] args) {
	// 冒泡排序--優(yōu)化比較輪數(shù)
	// 待排序數(shù)組
	int[] arr = { 1, 3, 46, 22, 11 };
	for (int j = 0; j < arr.length - 1; j++) { //輪數(shù)
	    //假設(shè)這一輪已經(jīng)拍好序，設(shè)置一個標(biāo)簽進(jìn)行記錄
	    boolean flag = true;
	    for (int i = 0; i < arr.length - 1 - j; i++) {//每一輪比較的次數(shù)
	        if(arr[i] > arr[i+1]) {
	            //更改是否比較過的標(biāo)簽
	            flag = false;
	            int temp = arr[i];
	            arr[i] = arr[i+1];
	            arr[i+1] = temp;
	        }
	    }
	    //如果本輪已排序好，則直接跳過，避免沒必要的比較。
	    if(flag) {
	        break;
	    }
	}
	//遍歷排序后的數(shù)組
	for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i]+"\t");
	}
    }
}

/**
 * @author
 */
public class Demo12 {
    public static void main(String[] args) {
	// 選擇排序
	// 待排序的數(shù)組
	int[] arr = { 1, 3, 46, 22, 11 };
	for (int j = 0; j < arr.length-1; j++) {
	    //選擇下標(biāo)為0的位置
	    int min = j;
	    //將當(dāng)前這個數(shù)與后面的每個數(shù)進(jìn)行比較
	    for (int i = j+1; i < arr.length; i++) {
	        //如果當(dāng)前數(shù)字小于標(biāo)記的最小值，則將當(dāng)前數(shù)字標(biāo)記為最小值
	        if(arr[min] > arr[i]) {
	            min = i;
	        }
	    }
	    //如果當(dāng)前數(shù)字不是最小的，則進(jìn)行交換
	    if(min != j) {
	        int temp = arr[j];
	        arr[j] = arr[min];
	        arr[min] = temp;
	    }
	}
        //遍歷排序后的數(shù)組
        for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i]+"\t");
        }
    }
}

/**
 * @author 
 */
public class Demo13 {
    public static void main(String[] args) {
	// 選擇排序
	//遍歷排序后的數(shù)組
	String[] names = { "cxk", "rose", "lihua", "lilei", "zhaosi" };
	//直接利用Arrays類提供的數(shù)組排序的方法，內(nèi)部是基于“快速排序”實現(xiàn)的。
	Arrays.sort(names);
	for (int i = 0; i < names.length; i++) {
            System.out.print(names[i] + "\t");
	}
    }
}

/**
 * @author 
 */
public class Demo14 {
    public static void main(String[] args) {
	// 二分查找法--折半查找法
	// 遍歷排序后的數(shù)組
	int[] arr = { 1, 3, 46, 22, 11 };
	int index = search(arr,46);
	System.out.println("46所在的索引位置="+index);
    }
    //定義一個方法，實現(xiàn)二分查找
    public static int search(int[] arr,int num) {
	//1. 獲取最小、大值的下標(biāo)
	int min = 0;
	int max = arr.length -1;
	while(min <= max) {
	    //2. 獲取中間值的下標(biāo)
	    int middle = (min + max) / 2;
	    //3. 將要查找的數(shù)字與中間值做比較
	    if(num > arr[middle]) {
	        min = middle +1;
	    }else if(num < arr[middle]) {
	        max = middle -1;
	    }else {
	        return middle;
	    }
        }
	return -1;
    }
}