Java使用二分法進(jìn)行查找和排序的示例

2019-11-26 14:27:00

字體：大中小

供稿：網(wǎng)友

實(shí)現(xiàn)二分法查找
二分法查找，需要數(shù)組內(nèi)是一個(gè)有序的序列
二分查找比線性查找：數(shù)組的元素?cái)?shù)越多，效率提高的越明顯
二分查找的效率表示：O(log2N) N在2的M次冪范圍，那查找的次數(shù)最大就是M, log2N表示2的M次冪等于N, 省略常數(shù)，簡(jiǎn)寫(xiě)成O(logN)
如有一個(gè)200個(gè)元素的有序數(shù)組，那么二分查找的最大次數(shù)：
2^7=128, 2^8=256, 可以看出7次冪達(dá)不到200，8次冪包括，所以最大查找次數(shù)就等于8

//循環(huán)，二分查找static int binarySearch(int[] array, int data) {   int start = 0;   int end = array.length - 1;   int mid = -1;   while (start <= end) {    System.out.println("查找次數(shù)");    mid = (start + end) >>> 1;    if (array[mid] < data) {     start = mid + 1;    } else if (array[mid] > data) {     end = mid - 1;    } else {     return mid;    }    System.out.println("start=" + start+",end="+end+",mid="+mid);   }   return -1;  }

//遞歸二分查找 初始start=0, end = array.length - 1  static int binarySearch4Recursion(int[] array, int data, int start, int end) {   int mid = -1;   System.out.println("查找次數(shù)");   if (start > end) {    return mid;   }   mid = (start + end) >>> 1;   if (array[mid] < data) {    return binarySearch4Recursion(array, data, mid + 1, end);   } else if (array[mid] > data) {    return binarySearch4Recursion(array, data, start, mid - 1);   } else {    return mid;   }      }

二分法插入排序

設(shè)有一個(gè)序列a[0],a[1]...a[n];其中a[i-1]前是已經(jīng)有序的,當(dāng)插入時(shí)a[i]時(shí),利用二分法搜索a[i]插入的位置
效率：O(N^2)，對(duì)于初始基本有序的序列，效率上不如直接插入排序；對(duì)于隨機(jī)無(wú)序的序列，效率比直接插入排序要高

/*  * 二分(折半)插入排序  * 設(shè)有一個(gè)序列a[0],a[1]...a[n];其中a[i-1]前是已經(jīng)有序的,當(dāng)插入時(shí)a[i]時(shí),利用二分法搜索a[i]插入的位置  */ public class BinaryInsertSort {   public static void main(String[] args) {   int len = 10;   int[] ary = new int[len];   Random random = new Random();   for (int j = 0; j < len; j++) {    ary[j] = random.nextInt(1000);   }   binaryInsert(ary);   /*    * 復(fù)雜度分析： 最佳情況，即都已經(jīng)排好序，則無(wú)需右移，此時(shí)時(shí)間復(fù)雜度為：O(n lg n) 最差情況，全部逆序，此時(shí)復(fù)雜度為O(n^2)    * 無(wú)法將最差情況的復(fù)雜度提升到O(n|logn)。    */   // 打印數(shù)組   printArray(ary);  }  /**   * 插入排序   * @param ary   */  private static void binaryInsert(int[] ary) {   int setValueCount = 0;   // 從數(shù)組第二個(gè)元素開(kāi)始排序，因?yàn)榈谝粋€(gè)元素本身肯定是已經(jīng)排好序的   for (int j = 1; j < ary.length; j++) {// 復(fù)雜度 n    // 保存當(dāng)前值    int key = ary[j];    // ∆ 利用二分查找定位插入位置 //   int index = binarySearchAsc(ary, ary[j], 0, j - 1);// 復(fù)雜度：O(logn) //   int index = binarySearchDesc(ary, ary[j], 0, j - 1);// 復(fù)雜度：O(logn)    int index = binarySearchDesc2(ary, ary[j], 0, j - 1);// 復(fù)雜度：O(logn)    printArray(ary);    System.out.println("第" + j +"個(gè)索引上的元素要插入的位置是：" + index);    // 將目標(biāo)插入位置，同時(shí)右移目標(biāo)位置右邊的元素    for (int i = j; i > index; i--) {// 復(fù)雜度,最差情況：(n-1)+(n-2)+...+n/2=O(n^2)     ary[i] = ary[i - 1]; //i-1 <==> index     setValueCount++;    }    ary[index] = key;    setValueCount++;   }   System.out.println("/n 設(shè)值次數(shù)(setValueCount)=====> " + setValueCount);  }   /**   * 二分查找 升序 遞歸   *   * @param ary   *   給定已排序的待查數(shù)組   * @param target   *   查找目標(biāo)   * @param from   *   當(dāng)前查找的范圍起點(diǎn)   * @param to   *   當(dāng)前查找的返回終點(diǎn)   * @return 返回目標(biāo)在數(shù)組中，按順序應(yīng)在的位置   */  private static int binarySearchAsc(int[] ary, int target, int from, int to) {   int range = to - from;   // 如果范圍大于0，即存在兩個(gè)以上的元素，則繼續(xù)拆分   if (range > 0) {    // 選定中間位    int mid = (to + from) / 2;    // 如果臨界位不滿(mǎn)足，則繼續(xù)二分查找    if (ary[mid] > target) {     /*      * mid > target, 升序規(guī)則，target較小，應(yīng)交換位置 前置， 即target定位在mid位置上，      * 根據(jù) 查找思想， 從from到 mid-1認(rèn)為有序， 所以to=mid-1      */     return binarySearchAsc(ary, target, from, mid - 1);    } else {     /*      * mid < target, 升序規(guī)則，target較大，不交換位置，查找比較的起始位置應(yīng)為mid+1      */     return binarySearchAsc(ary, target, mid + 1, to);    }   } else {    if (ary[from] > target) {//如 5,4, 要插入的是4     return from;    } else {     return from + 1;    }   }  }  /**   * 二分查找 降序， 遞歸   */  private static int binarySearchDesc(int[] ary, int target, int from, int to) {   int range = to - from;   if (range > 0) {    int mid = (from + to) >>> 1;    if (ary[mid] > target) {     return binarySearchDesc(ary, target, mid + 1, to);    } else {     return binarySearchDesc(ary, target, from, mid - 1);    }   } else {    if (ary[from] > target) {//如 5,4, 要插入的是4     return from + 1;    } else {     return from;    }   }  }    /**   * 二分查找 降序， 非遞歸   */  private static int binarySearchDesc2(int[] ary, int target, int from, int to) { //  while(from < to) {   for (; from < to; ) {    int mid = (from + to) >>> 1;    if (ary[mid] > target) {     from = mid + 1;    } else {     to = mid -1;    }   }   //from <==> to;   if (ary[from] > target) {//如 5,4, 要插入的是4    return from + 1;   } else {    return from;   }  }   private static void printArray(int[] ary) {   for (int i : ary) {    System.out.print(i + " ");   }  }  }

打印

918 562 442 531 210 216 931 706 333 132 第1個(gè)索引上的元素要插入的位置是：1 918 562 442 531 210 216 931 706 333 132 第2個(gè)索引上的元素要插入的位置是：2 918 562 442 531 210 216 931 706 333 132 第3個(gè)索引上的元素要插入的位置是：2 918 562 531 442 210 216 931 706 333 132 第4個(gè)索引上的元素要插入的位置是：4 918 562 531 442 210 216 931 706 333 132 第5個(gè)索引上的元素要插入的位置是：4 918 562 531 442 216 210 931 706 333 132 第6個(gè)索引上的元素要插入的位置是：0 931 918 562 531 442 216 210 706 333 132 第7個(gè)索引上的元素要插入的位置是：2 931 918 706 562 531 442 216 210 333 132 第8個(gè)索引上的元素要插入的位置是：6 931 918 706 562 531 442 333 216 210 132 第9個(gè)索引上的元素要插入的位置是：9

設(shè)值次數(shù)(setValueCount)=====> 24