直接插入排序和二分法插入排序的區(qū)別。

• 相同之處:

插入第i個(gè)元素時(shí), 前i-1個(gè)元素已經(jīng)是有序的

• 不同之處:

直接插入排序在尋找子數(shù)組(前i-1個(gè)元素組成的有序數(shù)組)中的插入位置時(shí),是拿待插入的元素和子數(shù)組里的元素按順序從左到右或從右到左一個(gè)一個(gè)比較來(lái)確定待插入的位置。

二分法插入排序是拿待插入元素和有序子數(shù)組中間位置的元素比較,以當(dāng)前的中間位置為分界點(diǎn)來(lái)確定待插入元素在該分界點(diǎn)的左邊還是右邊, 如果在左邊, 就把分界點(diǎn)左邊的元素序列當(dāng)作下一次的要尋找的子數(shù)組(不包括中間元素)。 如果在右邊, 就把分界點(diǎn)右邊的元素序列當(dāng)作下一次的要尋找的子數(shù)組(不包括中間元素)。重復(fù)上述過(guò)程直到子數(shù)組的長(zhǎng)度小于1查找結(jié)束。

/**
 * 二分法插入排序
 *
 */
public class BinaryInsertSort {

    public void binaryInsertSort(int[] array) {

        for (int i = 1; i < array.length; i++) {
            int temp = array[i];    // 待插入的元素
            int left = 0;           // 已有序序列的起始下標(biāo)
            int right = i - 1;      // 已有序序列的結(jié)束下標(biāo)
            int middle = 0;         // 已有序序列的中間下標(biāo)
            // 利用二分法尋找插入位置
            while (left <= right) { 
                middle = (left + right) / 2;
                if (temp > array[middle]) {
                    left = middle + 1;
                } else {
                    right = middle - 1;
                }
            }
            // 找到了元素的插入位置, 把下標(biāo)從left開(kāi)始往后的所有元素后移一位(包括left位置的元素)
            for(int j = i - 1; j >= left; j--) {
                array[j + 1] = array[j];
            }
            
            // 待插入的元素歸位
            if(i != left) {
                array[left] = temp;
            }
        }
        display(array);
    }

    public void display(int[] array) {
        for(int x: array) {
            System.out.print(x + " ");
        }
    }
    
    public static void main(String[] args) {
        int[] array = {1,3,4,3,8,3,2,6,7,4,9,10,0,-1,-7,4,2,9,7,20};
        BinaryInsertSort insertSort = new BinaryInsertSort();
        insertSort.binaryInsertSort(array);
        //結(jié)果： -7 -1 0 1 2 2 3 3 3 4 4 4 6 7 7 8 9 9 10 20 
    }

}