插入排序与shell排序(希尔排序)

时间:2023-03-09 14:40:55
插入排序与shell排序(希尔排序)

1 .插入排序的过程如同我们平时打扑克牌取牌插入的过程,不断将取出的扑克牌插入已经排好的地方。

插入排序过程初始有序区间大小为1,取出无序区间的首元素,查找有序区间的合适位置,进行插入。不断重复上述过程,即可完成操作。

图解示例

插入排序与shell排序(希尔排序)

 //插入排序
//karllen @2015
void insertSort()
{
int i ,j ,temp;
for(i = ;i<n;++i) //从第二个元素开始插入
{
temp = a[i]; //a[i]会被覆盖,临时保存
j = i - ;
while(j>=&&a[j]>temp) //边移动边比较
{
a[j+] = a[j];
}
a[j+] = temp;
}
}

2 .shell 排序算法是插入排序算法的一种,希尔排序先要将排序的一组数据按照某个增量分成若干组,相隔增量个的元素组成一组分别进行

插入排序,然后缩小增量,不断重复上述过程。直到将增量减小到1时,整个要排序的结果只能分成一组,并对其进行插入排序,即可完成。

图解示例:

插入排序与shell排序(希尔排序)

取增量组为{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[] = {,,,,,,,,,,}; shellSort(a,); for(int i = ;i<;++i)
{
std::cout<<a[i]<<" ";
} return ;
} void shellSort(int *a,int length) //希尔排序
{
for(int incrt = length/; incrt>;incrt /= )
{
for(int i = ;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>= && a[r]>temp) //从后往前边移动边比较
{
a[r+incrt] = a[r];
r = r-incrt;
}
a[r+incrt] = temp; // 插入
j = j+incrt; // 转入下一元素的插入过程
}
}
}
}

测试结果:

插入排序与shell排序(希尔排序)

书到用时方恨少,是非经过不知难。 博观而约取,厚积而薄发。@karllen 每天进步一点点。