歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

排序算法之二分法(折半)插入排序算法

基本思想
折半插入排序的基本思想與直接插入排序一樣,在插入第i(i≥1)個元素時,前面i-1個元素已經排好序。區別在於尋找插入位置的方法不同,折半插入排序是采用折半查找法來尋找插入位置的。
折半查找法的基本思路是:用待插元素的值與當前查找序列的中間元素的值進行比較,以當前查找序列的中間元素為分界,確定待插元素是在當前查找序列的左邊還是右邊,如果是在其左邊,則以該左邊序列為當前查找序列,右邊也類似。按照上述方法,遞歸地處理新序列,直到當前查找序列的長度小於1時查找過程結束。

代碼
//待排數據存儲在數組a中,以及待排序列的左右邊界
public void BinaryInsertSort(int[] a, int left, int right) {
    int low, middle, high;
        int temp;
    for (int i = left + 1; i <= right; i++) {
            temp = a[i];
            low = left;
            high = i - 1;
            while (low <= high) {
                middle = (low + high) / 2;
                if (a[i] < a[middle])
                    high = middle - 1;
                else
                    low = middle + 1;
        }

            for (int j = i - 1; j >= low; j--)
                    a[j + 1] = a[j];

            a[low] = temp;
        }
}

性能分析
時間復雜度
折半插入排序適合記錄數較多的場景,與直接插入排序相比,折半插入排序在尋找插入位置上面所花的時間大大減少,但是折半插入排序在記錄移動次數方面和直接插入排序是一樣的,所以其時間復雜度為O(n2)。
其次,折半插入排序的記錄比較次數與初始序列無關。因為每趟排序折半尋找插入位置時,折半次數是一定的,折半一次就要比較一次,所以比較次數也是一定的。
空間復雜度
同直接插入排序一樣,為O(1)。
穩定性
折半插入排序是一種穩定的排序算法。

Copyright © Linux教程網 All Rights Reserved