经典算法实现之二分插入排序

算法

二分法插入排序是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
namespace sorting{
    template<typename T>
    int64_t binary_search(std::vector<T> &arr,T val, int64_t low,int64_t high){
        if(high<=low){
            return (val>=arr[low])?low+1:low;
        }
        int mid = low+(high-low)/2;
        if(arr[mid]>val){
            return binary_search(arr,val,low,mid-1);
        }
        else if(arr[mid]<val){
            return binary_search(arr,val,mid+1,high);
        }
        else{
            return mid+1;
        }
    }

    template<typename T>
    void insertionSort_binsrch(std::vector<T> &arr){
        int64_t n = arr.size();

        for (int64_t i = 1; i < n; i++) {
            T key = arr[i];
            int64_t j = i - 1;
            int64_t loc = sorting::binary_search(arr, key, 0, j);
            while (j >= loc) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

  • 测试

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    static void test(){
        std::vector<int64_t> arr1({2, 2, 1, 1, 7});
        std::cout << "1st test... ";
        sorting::insertionSort_binsrch(arr1);
        assert(std::is_sorted(std::begin(arr1), std::end(arr1)));
        std::cout << "passed" << std::endl;
    }

    int main(){
        test();
    }