八大排序算法（二） 折半插入排序

---

---

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define SIZE 10
int n[SIZE];

void init(int n[], int len){
    int i;
    srand((unsigned)time(NULL));
    for (i=0; i<len; i++){
        n[i] = rand()%10+1;
    }
}

void printout(int n[], int len){
    int i;
    for (i=0; i<len; i++){
        printf("%d ", n[i]);
    }
    printf("
");
}

void BinaryInsertionSort(int n[], int len){
    int i, k ,r;
    int temp;

    for (i=1; i<len; i++){
        temp = n[i];
        // 把前后两个边界相互固定
        k = 0;
        r = i-1;
        // 开始寻找
        while (k <= r){
            int m;
            m = (k+r)/2;
            if (temp < n[m])
                r = m - 1;
            else
                k = m + 1;
        }
        /* 找到要被插入的位置, 注意: 找到K, 要移动的位置是i .
           此处的i 为要被插入的位置，固无用
        */
        for (r=i; r>k; r--)
            n[r] = n[r-1];
        n[k] = temp;
    //  printout(n, SIZE);
    }


}
int main(){
    init(n, SIZE);
    printout(n, SIZE);
    BinaryInsertionSort(n, SIZE);
    printout(n, SIZE);
    return 0;
}

运行图: