插入排序
直接插入排序
// 直接插入排序
void DirectInsertSort(int arr[], int lhs, int rhs)
{
int temp;
for (int i = lhs+1; i <= rhs; ++i)
{
temp = arr[i];
int j = i - 1; @1
while (j >= 0 && temp < arr[j]) @2
{
arr[j+1] = arr[j];
--j; @3
}
arr[j+1] = temp; @4
}
}
j始终保持在下一个要和temp作比较的元素的位置上，所以一旦j左移出了数组或是j位置的元素小于或等于temp时，内循环会停下来，temp的合适位置也找到，就是j的下一个位置。见@3
直接插入排序是稳定的，在代码中的体现是@2中的（temp < arr[j]），如果temp和前面的某个元素arr[j]相等，则内循环跳出，也就保证了两个相同的元素，后一个会在前一个之后。
直接插入排序对于小规模的输入表现良好，在快速排序或是归并排序这种分治法下，一旦规模足够小就不再往下分而是用直接插入排序解决。但大规模输入下，由于其复杂度为O（n^2），效果远不如O（nlgn）的排序。
折半插入排序
// 折半插入排序
void BinaryInsertSort(int arr[], int lhs, int rhs)
{
int left, right, mid, temp;
for (int i = lhs+1; i <= rhs; ++i)
{
left = 0; @1
right = i - 1;
temp = arr[i];
while (left <= right) @2
{
mid = (left + right) / 2;
if (temp < arr[mid]) @3
{
right = mid - 1; @4
}else
{
left = mid + 1; @5
}
}
for (int j = i-1; j >= left; --j) @6
{
arr[j+1] = arr[j];
}
arr[left] = temp; @7
}
}
折半插入排序是对直接插入排序的改进，因为当前元素的前面已经是有序的，那么折半（二分法）进行查找合适位置要比顺序的找更合适，尤其是在大规模输入时。直接插入在寻找当前元素合适位置是一个一个的尝试，而折半插入是通过二分法+循环最后定位到合适的位置，然后将数组的【合适的位置，当前元素的前一个位置】区间元素右移一个位置，再把当前元素插入到那个找到的合适的位置。
考虑下面的三个输入示例：
1 3 5 7 8 2 4 6
2 3 5 7 8 2 4 6
3 3 5 7 8 2 4 6
假设当前元素为第6个元素（从1开始），其值为2，那么要在区间【1，5】区间内找到一个合适的位置安插值为2的元素，第一个元素的三种取值（1,2,3）可以对应内循环（循环的二分查找）的三种情况。
@1：外层循环和直接插入一致，先设置二分查找要用的left，right，以及保存当前元素temp。
@2：先在区间【1,5】用二分法，temp（2）和arr[mid]（5）比较，进入@4,；然后再在区间【1,2】中用二分法，temp（2）和arr[mid]（1）比较，在最原始的区间【1,5】中不断的用 二分法最终会将区间缩小到相邻的两个位置上，因为用的是（left+right）/2，所以求出的中间位置（mid）永远都是两个相邻位置中的靠左的位置。下面讨论三种实例中的arr[1]。这时候left = 1, right = 2，mid = 1。
1》temp（2）和arr[mid]（1）比较后进入@5，然后left = right = 2，再次进入内循环。mid = 2，temp（2）和arr[mid]（3）比较后进入@4，right = mid -1后小于left不满足内循环条件，进而跳出内循环。
2》和1》一样，而且在@3的比较用的小于号，这也是折半插入是稳定性的关键。
3》temp（3）和arr[mid]（2）比较后进入@4，right = mid（1） - 1，最后right小于left，退出内循环。
这三种情况下最后跳出内循环的前一次if else判断中，总是进入的@4分支，也就是说right减小进而小于了left。这也保证了left在跳出内循环后指向的位置是：第一个大于temp的元素的位置
@6：一次性的将区间右移
@7：将temp安插到合适的位置
希尔排序（一种特殊的直接插入）
// 测试希尔排序
void ShellSort(int arr[], int lhs, int rhs)
{
int gap = rhs - lhs + 1;
int temp;
do
{
gap = gap/3 + 1; @1
for (int i = lhs+gap; i <= rhs; ++i) @2
{
temp = arr[i];
int j = i - gap; @3
while (j >= lhs && temp < arr[j])
{
arr[j+gap] = arr[j];
j = j - gap;
}
arr[j+gap] = temp;
}
} while (gap > 1); @4
}
希尔排序属于减小增量的排序算法，也是不稳定排序，原因：它的有序性不是逐步的，而是整个过程中都没有序，直到最后gap=1时，才算完成排序。所以在整个过程中即使两个相同元素，代码中也没有保证他们顺序的点。
@1：先记录输入规模，然后使用do while()结构，起到了一个作用：最起码可以执行一次循环。
@2：之所以用++i，而不是i+=gap。这么写的好处是一趟下来交替的处理了各个子序列。当gap=1时，就是普通的直接插入排序
@3：整个内循环和直接插入很类似，只是1变成了gap
@4：当gap满足大于1且又小于3时候就是最外层循环的最后一次了，因为当gap等于1时，已经保证输入序列有序了。