直接插入排序算法及其改进

插入排序，分为直接插排，和二分插排

直接插入排序

大体思路：选取<数组>，将其余数依次按顺序往里放。 （C语言实现）

#include <stdio.h>
void insertSort(int *a);
int main() {
    int a[6] = { 5,2,4,6,1,3 };   //这里也可以改成自定义数组
    insertSort(a);
    int k;
    for (k = 0; k < 6;k++) {
        printf("%d ", a[k]);
    }
    getchar();
    return 0;
}
void insertSort(int *a) {
    int i, j,key;
    //这里是从第二个元素开始的
    for (j = 1; j < 6; j++) {
        key = a[j];
        //上一个元素
        i = j - 1;

        //数组下标0开始所以>=0
        while (i >= 0 && a[i] > key){   //一定要有 i>=0 这步，这关系到 i=i-1 的下一步是否进行while循环
            a[i + 1] = a[i];
            i = i - 1;
        }
       a[i + 1] = key;
    }
}

上面代码中为什么要有"key=a[i]"：选取“傀儡变量”，下面令a[i+1]=a[i];若a[i]没有提前准备好“副本”，经过这一步时，原a[j]的位置已经变成了a[i]（下面a[i+1]被a[i]赋值），毫无意义。。。。。。

算法改进：

二分插入排序

与直接插排的区别：在有序区查找新元素插入位置时，为了减少元素比较次数，提高效率，采用二分查找法确定插入位置。 算法分析： 设数组为a[0…n]。

1. 将原序列分成有序区和无序区。a[0…i-1]为有序区，a[i…n] 为无序区。（i从1开始）
2. 从无序区中取出第一个元素，即a[i]，使用二分查找算法在有序区中查找要插入的位置索引j。
3. 将a[j]到a[i-1]的元素后移，并将a[i]赋值给a[j]。
4. 重复步骤2~3，直到无序区元素为0。

// 二分插入排序
void BinInsertSort(vector<int> &vi)
{
    for(int i=1;i<vi.size();i++)
    {
        int left=0;
        int right=i-1;
        int temp=vi[i]
        while(left<=right)
        {
            int mid=(left+right)/2; //二分区域
            if(vi[mid]>temp)
            {
                right=mid-1;       //向左缩小区域
            }
            else
            {
                left=mid+1;        //向右缩小区域
            }
        }
        for(int j=i-1;j>left;j--)  //vi[left,i-1]的元素整体后移
        {
            vi[j+1]=vi[j];
        }
        vi[left]=temp;
    }
}