數(shù)據(jù)結(jié)構(gòu):二分法插入排序

二分法插入排序
    算法思想簡單描述：
    在插入第i個元素時，對前面的0～i-1元素進(jìn)行折半，先跟他們中間的那個元素比，如果小，則對前半再進(jìn)行折半，否則對后半進(jìn)行折半，直到left>right，然后再把第i個元素前1位與目標(biāo)位置之間的所有元素后移，再把第i個元素放在目標(biāo)位置上。
    二分法沒有排序，只有查找。所以當(dāng)找到要插入的位置時。移動必須從最后一個記錄開始，向后移動一位，再移動倒數(shù)第2位，直到要插入的位置的記錄移后一位。
    二分插入排序是穩(wěn)定的，平均時間O(n2)
    void binsort(ref int[] data1)
    1、二分法查找插入位置
    如果R[i]    2、后移，有點(diǎn)迷惑，什么時候需要后移呢？有哪些記錄需要移動呢？
    雖然我們很清楚的知道，我們需要后移那些排序碼大于R[i]的記錄，但難免會問自己這樣幾個問題。其實(shí)它相當(dāng)于需要移動從i-1到左指針的記錄。
    3、插入
    由1中得到的左指針其實(shí)就是元素要插入的位置。
    4、算法
    {
    int left,right,num;
    int middle,j;
    for( int i = 1;i < data1.Length;i++)
    {
    // 準(zhǔn)備
    left = 0;
    right = i-1;
    num = data1[i];
    // 二分法查找插入位置
    while( right >= left)
    {
    //　指向已排序好的中間位置
    middle = ( left + right ) / 2;
    if( num < data1[middle] )
    // 插入的元素在右區(qū)間
    right = middle-1;　
    else
    //　插入的元素在左區(qū)間
    left = middle+1;
    }
    //　后移排序碼大于R[i]的記錄
    for( j = i-1;j >= left;j-- )
    {
    data1[j+1] = data1[j];
    }
    // 插入
    data1[left] = num;
    }
    //　插入的元素在左區(qū)間
    left = middle+1;
    }
    //　后移排序碼大于R[i]的記錄
    for( j = i-1;j >= left;j-- )
    {
    data1[j+1] = data1[j];
    }
    // 插入
    data1[left] = num;
    }
    /* 二分法插入排序的算法源程序*/
    #include
    #define MAXNUM 100
    typedef int KeyType;
    typedef int DataType;
    typedef struct {
    KeyType key; /* 排序碼字段 */
    /*DataType info; 記錄的其它字段 */
    } RecordNode;
    typedef struct {
    int n; /* n為文件中的記錄個數(shù)，n    RecordNode record[MAXNUM];
    } SortObject;
    void binSort(SortObject * pvector) { /* 按遞增序進(jìn)行二分法插入排序 */
    int i, j, left, mid, right;
    RecordNode temp;
    RecordNode *data = pvector->record;
    for( i = 1; i < pvector->n; i++ ) {
    temp = data[i];
    left = 0; right = i-1; /* 置已排序區(qū)間的下、上界初值 */
    while (left <= right) {
    mid = (left + right)/2; /* mid指向已排序區(qū)間的中間位置 */
    if (temp.key < data[mid].key)
    right = mid-1; /* 插入元素應(yīng)在左子區(qū)間 */
    else left = mid+1; /* 插入元素應(yīng)在右子區(qū)間 */
    }
    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[i]);
    getchar();
    return 0;
    }