排序技术-插入排序

插入排序是一类借助插入进行排序的方法，其主要思想是：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序。

具体的排序过程是：

（1）将整个待排序的记录序列化分成有序区和无序区，初始时有序区为待排序序列的第一个记录，无序区包括所有剩余待排序的记录；

（2）将无序区的第一个记录插入到有序区合适的位置中，从而使无序区减少一个记录，有序区增加一个记录；

（3）重复执行（2），直到无序区中没有记录为止。

算法描述：

for (i=2;i<=n;i++){
插入第n个记录；

}

下面给出完整的直接插入排序的算法：

void InsertSort(int r[],int n){
    for (i=2;i<=n;i++){
        r[0]=r[i];
        for(j=i-1;r[0]             r[j+1]=r[j];
        }
        r[j+1]=r[0]; 
    }
}