package 算法設(shè)計(jì)與分析;
 public class 歸并排序 {
 //arr是存放原始元素的數(shù)組，left數(shù)組arr的最左邊，left是數(shù)組的最右邊，mid是劃分的終點(diǎn)，數(shù)組tmp是一個(gè)臨時(shí)數(shù)組，就是一個(gè)輔助存儲(chǔ)空間
         public static void main(String[] args) {
             int[] arr = {49,38,65,97,76,13,27};
             int[] tmp = new int[arr.length];    //新建一個(gè)臨時(shí)數(shù)組存放,相當(dāng)于是一個(gè)輔助空間
             mergeSort(arr,0,arr.length-1,tmp);
             for(int i=0;i<arr.length;i++){
                 System.out.print(arr[i]+" ");
             }
         }
         public static void merge(int[] arr,int left,int mid,int right,int[] tmp){
             int i = 0;
             int j = left,k = mid+1;  //左邊序列和右邊序列起始索引
             while(j <= mid && k <= right){
                 if(arr[j] <= arr[k]){
                     tmp[i++] = arr[j++];
                 }else{
                     tmp[i++] = arr[k++];
                 }
             }
             //若左邊序列還有剩余，則將其全部拷貝進(jìn)tmp[]中
             while(j <= mid){
                 tmp[i++] = arr[j++];
             }
             while(k <= right){
                 tmp[i++] = arr[k++];
             }
             for(int t=0;t<i;t++){
                 arr[left+t] = tmp[t];
             }
         }
         public static void mergeSort(int[] arr,int left,int right,int[] tmp){
             if(left<right){
                 int mid = (left+right)/2;
                 mergeSort(arr,left,mid,tmp); //對(duì)左邊序列進(jìn)行歸并排序
                 mergeSort(arr,mid+1,right,tmp);  //對(duì)右邊序列進(jìn)行歸并排序
                 merge(arr,left,mid,right,tmp);    //合并兩個(gè)有序序列，相當(dāng)于用tmp覆蓋原來(lái)的arr
             }
         }
     }

package 算法設(shè)計(jì)與分析;
 public class 快速排序 {
         public static void quickSort(int[] arr,int left,int right){
             int i,j,temp,t;
             if(left>right){
                 return;
             }
             i=left;
             j=right;
             //temp就是基準(zhǔn)位,就是主元，將數(shù)組中的第一個(gè)元素作為主元
             temp = arr[left];
             while (i<j) {
                 //先看右邊，依次往左遞減
                 while (temp<=arr[j]&&i<j) {
                     j--;
                 }
                 //再看左邊，依次往右遞增
                 while (temp>=arr[i]&&i<j) {
                     i++;
                 }
                 //如果滿足條件則交換
                 if (i<j) {
                     t = arr[j];
                     arr[j] = arr[i];
                     arr[i] = t;
                 }
             }
             //最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換
             arr[left] = arr[i];
             arr[i] = temp;
             //遞歸調(diào)用左半數(shù)組
             quickSort(arr, left, j-1);
             //遞歸調(diào)用右半數(shù)組
             quickSort(arr, j+1, right);
         }
         public static void main(String[] args){
             int[] arr = {72,26,57,88,42,80,72,48,60,};
             quickSort(arr, 0, arr.length-1);
             for (int i = 0; i < arr.length; i++) {
                 System.out.print(arr[i]+ " ");
             }
         }
     }

 package 算法設(shè)計(jì)與分析;
 //用遞歸的方法解決二分搜索問(wèn)題
 public class 二分查找 {
     public static void main(String[] args) {
         int[] arr = {-7,-2,0,15,27,54,80,88,102};
         //想要查找的元素
         int key = 80;
         //對(duì)查找到的元素進(jìn)行定位
         int position = Search(arr,key,0,arr.length - 1);
         if(position == -1){
             System.out.println("查找的是"+key+",序列中沒(méi)有該數(shù)！");
         }else{
             System.out.println("查找的是"+key+",找到位置為："+position);
         }
     }
     public static int Search(int[] arr,int key,int left,int right){
         if(key < arr[left] &&key > arr[right] &&left > right){
             return -1;
         }
         int middle = (left + right) / 2;            //初始中間位置
         if(arr[middle] > key){
             //比關(guān)鍵字大則關(guān)鍵字在左區(qū)域
             return Search(arr, key, left, middle - 1);
         }else if(arr[middle] < key){
             //比關(guān)鍵字小則關(guān)鍵字在右區(qū)域
             return Search(arr, key, middle + 1, right);
         }else {
             return middle;
         }
     }
 }