算法思想简单描述：

复杂度分析

实施步骤

C源码

java源码

算法思想简单描述：

在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们

中间的那个元素比，如果小，则对前半再进行折半，否则对后半

进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间

的所有元素后移，再把第i个元素放在目标位置上。

二分法没有排序，只有查找。所以当找到要插入的位置时。移动必须从最后一个记录开始，向后移动一位，再移动倒数第2位，直到要插入的位置的记录移后一位。

复杂度分析

二分插入排序是稳定的与二分查找的复杂度相同；

最好的情况是当插入的位置刚好是二分位置 所用时间为O(n);

最坏的情况是当插入的位置不在二分位置 所需比较次数为

n

S<=∑n「log₂n「-2^n「log₂n「+1

k= 1

平均时间O(n2)

实施步骤

1、二分法查找插入位置

如果R<R[m]成立，那右指针就要向左移动中间指针一位，否则，左指针要向右移动中间指针一位。反复查找，直到左指针大于右指针时停止。

2、后移，有点迷惑，什么时候需要后移呢？有哪些记录需要移动呢？

虽然我们很清楚的知道，我们需要后移那些排序码大于R的记录，但难免会问自己这样几个问题。其实它相当于需要移动从i-1到左指针的记录。

3、插入

由1中得到的左指针其实就是元素要插入的位置。

C源码

/* 二分法插入排序的算法源程序*/

#include<stdio.h>

#define MAXNUM 100

typedef int KeyType;

typedef int DataType;

typedef struct {

KeyType key; /* 排序码字段 */

/*DataType info; 记录的其它字段 */

} RecordNode;

typedef struct {

int n; /* n为文件中的记录个数，n<MAXNUM */

RecordNode record[MAXNUM];

} SortObject;

void binSort(SortObject * pvector) { /* 按递增序进行二分法插入排序 */

int i, j, left, mid, right;

RecordNode temp;

RecordNode *data = pvector->record;

for( i = 1; i < pvector->n; i++ ) {

temp = data;

left = 0; right = i-1; /* 置已排序区间的下、上界初值 */

while (left <= right) {

mid = (left + right)/2; /* mid指向已排序区间的中间位置 */

if (temp.key < data[mid].key)

right = mid-1; /* 插入元素应在左子区间 */

else left = mid+1; /* 插入元素应在右子区间 */[Page]

}

for (j = i-1; j >= left; j--)

data[j+1] = data[j]; /* 将排序码大于ki的记录后移 */

if (left != i) data[left] = temp;

}

}

SortObject vector={10, 49,38,65,97,76,13,27,49,50,101};

int main(){

int i;

binSort(&vector);

for(i = 0; i < vector.n; i++)

printf(\\"%d \\", vector.record);

getchar();

return 0;

}

java源码

public static int[] BarnarySort(int[] data) {

int[] temp = new int[data.length];

for (int i = 0; i < temp.length; i++) {

if (i == 0) {

temp[i] = data[i];

} else {

for (int j = 0, k = i - 1; j < i && k >= 0;) {

if (temp[(j + k) / 2] >= data[i]) {

if ((j + k) / 2 == 0) {

for (int iter = i; iter > 0; iter--) {

temp[iter] = temp[iter - 1];

}

temp[0] = data[i];

break;

} else if (temp[(j + k) / 2 - 1] <= data[i]) {

for (int iter = i; iter > (j + k) / 2; iter--) {

temp[iter] = temp[iter - 1];

}

temp[(j + k) / 2] = data[i];

break;

} else {

k = (k + j) / 2-1;

}

} else if (temp[(j + k) / 2] < data[i]) {

if ((j + k) / 2 == i - 1) {

temp[i] = data[i];

break;

} else {

j=(k + j) / 2+1;

}

}

}

}

}

return temp;

}