快捷導(dǎo)航

Java經(jīng)典排序算法之二分插入排序詳解

更新時間：2021年08月27日 09:10:17 作者：歐陽鵬

這篇文章主要為大家詳細介紹了Java經(jīng)典排序算法之二分插入排序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

一、折半插入排序（二分插入排序）

將直接插入排序中尋找A[i]的插入位置的方法改為采用折半比較，即可得到折半插入排序算法。在處理A[i]時，A[0]……A[i-1]已經(jīng)按關(guān)鍵碼值排好序。所謂折半比較，就是在插入A[i]時，取A[i-1/2]的關(guān)鍵碼值與A[i]的關(guān)鍵碼值進行比較，如果A[i]的關(guān)鍵碼值小于A[i-1/2]的關(guān)鍵碼值，則說明A[i]只能插入A[0]到A[i-1/2]之間，故可以在A[0]到A[i-1/2-1]之間繼續(xù)使用折半比較；否則只能插入A[i-1/2]到A[i-1]之間，故可以在A[i-1/2+1]到A[i-1]之間繼續(xù)使用折半比較。如此擔負，直到最后能夠確定插入的位置為止。一般在A[k]和A[r]之間采用折半，其中間結(jié)點為A[k+r/2]，經(jīng)過一次比較即可排除一半紀錄，把可能插入的區(qū)間減小了一半，故稱為折半。執(zhí)行折半插入排序的前提是文件紀錄必須按順序存儲。

二、算法原理

折半插入排序的算法思想：

算法的基本過程：
（1）計算 0 ~ i-1 的中間點，用 i 索引處的元素與中間值進行比較，如果 i 索引處的元素大，說明要插入的這個元素應(yīng)該在中間值和剛加入i索引之間，反之，就是在剛開始的位置到中間值的位置，這樣很簡單的完成了折半；
（2）在相應(yīng)的半個范圍里面找插入的位置時，不斷的用（1）步驟縮小范圍，不停的折半，范圍依次縮小為 1/2 1/4 1/8 .......快速的確定出第 i 個元素要插在什么地方；
（3）確定位置之后，將整個序列后移，并將元素插入到相應(yīng)位置。

三、代碼實現(xiàn)

public class BinarySort { 
  public static void binarySort(int[] source) { 
    int i, j; 
    int high, low, mid; 
    int temp; 
    for (i = 1; i < source.length; i++) { 
      // 查找區(qū)上界 
      low = 0; 
      // 查找區(qū)下界 
      high = i - 1; 
      //將當前待插入記錄保存在臨時變量中 
      temp = source[i]; 
      while (low <= high) { 
        // 找出中間值 
        // mid = (low + high) / 2; 
        mid = (low + high) >> 1; 
        //如果待插入記錄比中間記錄小 
        if (temp<source[mid] ) { 
          // 插入點在低半?yún)^(qū) 
          high = mid - 1; 
        } else { 
          // 插入點在高半?yún)^(qū) 
          low = mid + 1; 
        } 
      } 
       //將前面所有大于當前待插入記錄的記錄后移  
      for (j = i - 1; j >=low; j--) { 
        source[j + 1] = source[j]; 
      } 
      //將待插入記錄回填到正確位置.  
      source[low] = temp; 
      System.out.print("第" + i + "趟排序："); 
      printArray(source); 
    } 
  } 
 
  private static void printArray(int[] source) { 
    for (int i = 0; i < source.length; i++) { 
      System.out.print("\t" + source[i]); 
    } 
    System.out.println(); 
  } 
 
  public static void main(String[] args) { 
    int source[] = new int[] { 12, 15, 9, 14, 4, 18, 23, 6 }; 
    System.out.print("初始關(guān)鍵字："); 
    printArray(source); 
    System.out.println(""); 
 
    binarySort(source); 
 
    System.out.print("\n\n排序后結(jié)果："); 
    printArray(source); 
  } 
}

四、運行結(jié)果

初始關(guān)鍵字： 12 15 9  14 4  18 23 6 
 
第1趟排序： 12 15 9  14 4  18 23 6 
第2趟排序： 9  12 15 14 4  18 23 6 
第3趟排序： 9  12 14 15 4  18 23 6 
第4趟排序： 4  9  12 14 15 18 23 6 
第5趟排序： 4  9  12 14 15 18 23 6 
第6趟排序： 4  9  12 14 15 18 23 6 
第7趟排序： 4  6  9  12 14 15 18 23 
 
 
排序后結(jié)果： 4  6  9  12 14 15 18 23

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: