数据结构排序法之插入法

插入排序是一种简单直观的排序算法。它的工作原理非常类似于我们抓扑克牌。

对于未排序数据(右手抓到的牌)，在已排序序列(左手已经排好序的手牌)中从后向前扫描，找到相应位置并插入。

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
具体算法描述如下：

1、从第一个元素开始，该元素可以认为已经被排序
2、取出下一个元素，在已经排序的元素序列中从后向前扫描
3、如果该元素（已排序）大于新元素，将该元素移到下一位置
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5、将新元素插入到该位置后
重复步骤2~5
代码如下：

// 插入排序法
void Insert (int* a, int len)
{int i, j, get;// 从数组第二个开始向后遍历，和他之前的比较并找到插入的位置for (i = 1; i < len; i++){get = a[i];                     // 保存要插入的数j = i-1;                        // 比较对象从他前一位开始// 找到比他小的，并且进行移位while (j >= 0 && a[j] > get){a[j+1] = a[j];j--;}a[j+1] = get;                   // 插入元素}
}

对于插入排序，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的次数，我们称为二分插入排序。
代码：

// 二分插入排序法
void Half_Insert (int* a, int len)
{int i;  // 从数组第二个开始向后遍历，和他之前的比较并找到插入的位置for (i = 1; i < len; i++){int left  = 0;int right = i - 1;int get   = a[i];// 缩小范围，直到找到插入的位置while (left <= right){int mid = (right+left) / 2;if (a[mid] > get){right = mid - 1;}else{left = mid + 1;}       }// 移位int j;for (j = i-1; j >= left; j--){a[j+1] = a[j];}a[left] = get;                      // 插入元素 }
}