溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家介紹利用Java如何實現一個二分插入排序，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。
一、折半插入排序（二分插入排序）
將直接插入排序中尋找A[i]的插入位置的方法改為采用折半比較，即可得到折半插入排序算法。在處理A[i]時，A[0]……A[i-1]已經按關鍵碼值排好序。所謂折半比較，就是在插入A[i]時，取A[i-1/2]的關鍵碼值與A[i]的關鍵碼值進行比較，如果A[i]的關鍵碼值小于A[i-1/2]的關鍵碼值，則說明A[i]只能插入A[0]到A[i-1/2]之間，故可以在A[0]到A[i-1/2-1]之間繼續使用折半比較；否則只能插入A[i-1/2]到A[i-1]之間，故可以在A[i-1/2+1]到A[i-1]之間繼續使用折半比較。如此擔負，直到最后能夠確定插入的位置為止。一般在A[k]和A[r]之間采用折半，其中間結點為A[k+r/2]，經過一次比較即可排除一半紀錄，把可能插入的區間減小了一半，故稱為折半。執行折半插入排序的前提是文件紀錄必須按順序存儲。
二、算法原理
折半插入排序的算法思想：
算法的基本過程：
（1）計算 0 ~ i-1 的中間點，用 i 索引處的元素與中間值進行比較，如果 i 索引處的元素大，說明要插入的這個元素應該在中間值和剛加入i索引之間，反之，就是在剛開始的位置 到中間值的位置，這樣很簡單的完成了折半；
（2）在相應的半個范圍里面找插入的位置時，不斷的用（1）步驟縮小范圍，不停的折半，范圍依次縮小為 1/2 1/4 1/8 .......快速的確定出第 i 個元素要插在什么地方；
（3）確定位置之后，將整個序列后移，并將元素插入到相應位置。
三、代碼實現
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++) {
// 查找區上界
low = 0;
// 查找區下界
high = i - 1;
//將當前待插入記錄保存在臨時變量中
temp = source[i];
while (low <= high) {
// 找出中間值
// mid = (low + high) / 2;
mid = (low + high) >> 1;
//如果待插入記錄比中間記錄小
if (temp<source[mid] ) {
// 插入點在低半區
high = mid - 1;
} else {
// 插入點在高半區
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("初始關鍵字：");
printArray(source);
System.out.println("");
binarySort(source);
System.out.print("\n\n排序后結果：");
printArray(source);
}
}
四、運行結果
初始關鍵字： 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 排序后結果： 4 6 9 12 14 15 18 23
關于利用Java如何實現一個二分插入排序就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
