插入排序与shell排序（希尔排序）

战胜自己

　　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;     //a会被覆盖，临时保存
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<<" ";
}
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 每天进步一点点。