折半插入排序

概述

将折半查找后插入排序相结合，使得查找效率更高，但移动的效率未变，所以折半插入排序的时间复杂度仍然为O(n*n)。

代码实现（C语言）

    #include "pch.h"  
    #include <iostream>  

    using namespace std;  

    void binsert_sort(int A[],int n) {  
        int i, j,low,high,mid;  
        for (i = 2; i <= n; i++) {  
            A[0] = A[i];//将i指针指向数据备份到数组的0位置里  
            low = 1; high = i - 1;  

            while (low <= high) {  
                mid = (low + high) / 2;  
                if (A[mid] < A[0]) {  
                    low = mid + 1;  
                }  
                else {  
                    high = mid - 1;  
                }  
            }  
            //在i指针位置之前的数据都已排好序，此处通过二分查找找到该元素对应位置，循环结束后找到位置为high+1  

            for (j = i - 1; j>=high+1; j--) {  
                A[j + 1] = A[j];  
            }  
            //将i指针之前high+1之后元素整体右移  
            A[high + 1] = A[0];   
            //将数组的0位置里备份的数据放到high+1的位置  
        }  
    }  

    int main()  
    {  
        int A[] = { 999,3,2,1,4 };//定义数组A，0号位999占位  
        binsert_sort(A,4);//对数组A排序  

        //循环输出A数组  
        int i;  
        for ( i = 1; i < 5; i++) {  
            cout << A[i] << endl;  
        }  

        system("pause");  
    }