二分法(折半)插入排序

算法思想简单描述：

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

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

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

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

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

　　二分插入排序是稳定的，平均时间O(n2)

　　void binsort(ref int[] data1)

　　1、二分法查找插入位置

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

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

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

　　3、插入

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

　　4、算法

　　{

　　int left,right,num;

　　int middle,j;

　　for( int i = 1;i < data1.Length;i++)

　　{

　　// 准备

　　left = 0;

　　right = i-1;

　　num = data1;

　　// 二分法查找插入位置

　　while( right >= left)

　　{

　　//　指向已排序好的中间位置

　　middle = ( left + right ) / 2;[Page]

　　if( num < data1[middle] )

　　// 插入的元素在右区间

　　right = middle-1;　

　　else

　　//　插入的元素在左区间

　　left = middle+1;

　　}

　　//　后移排序码大于R的记录

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

　　{

　　data1[j+1] = data1[j];

　　}

　　// 插入

　　data1[left] = num;

　　}

　　//　插入的元素在左区间

　　left = middle+1;

　　}

　　//　后移排序码大于R的记录

　　[Page]for( j = i-1;j >= left;j-- )

　　{

　　data1[j+1] = data1[j];

　　}

　　// 插入

　　data1[left] = num;

　　}

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

　　#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;

　　}