1 .插入排序的过程如同我们平时打扑克牌取牌插入的过程，不断将取出的扑克牌插入已经排好的地方。
插入排序过程初始有序区间大小为1，取出无序区间的首元素，查找有序区间的合适位置，进行插入。不断重复上述过程，即可完成操作。
图解示例
1 //插入排序 2 //karllen @2015 3 void insertSort() 4 { 5 int i ,j ,temp; 6 for(i = 1;i<n;++i) //从第二个元素开始插入 7 { 8 temp = a[i]; //a[i]会被覆盖，临时保存 9 j = i - 1; 10 while(j>=0&&a[j]>temp) //边移动边比较 11 { 12 a[j+1] = a[j]; 13 } 14 a[j+1] = temp; 15 } 16 }
2 .shell 排序算法是插入排序算法的一种，希尔排序先要将排序的一组数据按照某个增量分成若干组，相隔增量个的元素组成一组分别进行
插入排序，然后缩小增量，不断重复上述过程。直到将增量减小到1时，整个要排序的结果只能分成一组，并对其进行插入排序，即可完成。
图解示例：
取增量组为{3,2,1};
增量为3时，分为三组{70,10,90,60}，{30,80,100,45}，{40,20,75}分别进行插入排序，结果为
{10,60,70,90}
{30,45,80,100}
{20,40,75}; 执行完增量为3的分组插入排序后，结果为{10,30,20,60,45,40,70,80,75,90,100}局部有序性增强。
增量为2时，{10,30,40,60,45,20,70,80,75,90,100}被分为两组，{10,20,45,70,75,100},{30,60,40,80,90}分别进行插入排序，结果为
{10,20,45,70,75,100}
{30,40,60,80,90};执行为增量为2的分组插入排序后，结果为{10,30,20,40,45,60,70,80,75,90,100}局部有序性进一步增强。
最后执行增量为1的直接插入排序，结果为{10,20,30,40,45,60,70,75,80,90,100}至此shell排序结束。
要点：分组进行插入排序的过程目的是使数据朝着局部有序的方向发展。
这里涉及增量的选取，增量的选取理论上应该是两两互素的。
代码如下：
#include <iostream> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ // karllen //2015 void shellSort(int *a,int length); //希尔排序 int main(int argc, char** argv) { int a[] = {70,30,40,10,80,20,90,100,75,60,45}; shellSort(a,11); for(int i = 0;i<11;++i) { std::cout<<a[i]<<" "; } return 0; } void shellSort(int *a,int length) //希尔排序 { for(int incrt = length/2; incrt>0;incrt /= 2) { for(int i = 0;i<incrt;++i) //依次排序不同增量构成的子序列 { /*int j = i+incrt; int r; while(j<length) //普通插入排序，先比较后移动 { r = i; while(a[j]>a[r]) { r = r+incrt; } if(r!=j) { int temp = a[j]; int k = j; while(k>=r) { a[k] = a[k-incrt]; k -= incrt; } a[r] = temp; } j = j+incrt; } */ //改进后的直接插入排序，边移动边比较。 int j = i+incrt; int r,temp; while(j<length) { r = j-incrt; temp = a[j]; while(r>=0 && a[r]>temp) //从后往前边移动边比较 { a[r+incrt] = a[r]; r = r-incrt; } a[r+incrt] = temp; // 插入 j = j+incrt; // 转入下一元素的插入过程 } } } }
测试结果：
书到用时方恨少，是非经过不知难。 博观而约取,厚积而薄发。@karllen 每天进步一点点。
原文：http://www.cnblogs.com/Forever-Kenlen-Ja/p/4442343.html