1.算法思想
每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。
2.C语言代码实现
// 直接插入排序
void InsertSort(int arr[],int n){
int i, j, temp;
for(i=1; i<n; i++){ // 将各元素插入已经排好序的序列中
if(arr[i] < arr[i-1]){ // 若arr[i]关键字小于前驱
temp = arr[i]; // 使用temp暂存arr[i]
for(j=i-1; j>=0 && arr[j]>temp; --j){
arr[j+1] = arr[j]; // 所有大于temp的元素都向后挪位
}
arr[j+1] = temp; // 复制到插入位置
}
}
}
其它语言殊途同归
3.优化插入排序——折半查找排序
思想：先使用折半查找找到应该插入的位置，再移动元素。
在使用书的哨兵模式插入排序时：当low > high时折半查找停止，应将[low，length-1]内的元素全部右移，并将arr[0]复制到low所指的位置
代码如下：
注：此处使用哨兵模式
// 折半插入排序
void InsertSortHalf(int arr[], int n){
int i,j,low,high,mid;
for(i=2; i<=n; i++){ // 依次将arr[2]到arr[n]插入前面的已排好序的序列中
arr[0] = arr[1]; // 将arr[i]暂存到arr[0]
low = 1; // 设置折半查找的范围
high = i-1;
while(low <= high){ // 折半查找
mid = (low+high)/2; // 取中间点
if(arr[mid] > arr[0]){
high = mid-1;
}else{
low = mid+1;
}
}
for(j = i-1;j >= high+1; --j){
arr[j+1] = arr[j]; // 统一后移元素，空出插入位置
}
arr[high+1] = arr[0]; // 插入操作
}
}
