在学习希尔排序之前,我们先来了解一下插入排序
基本思想:把待排序的记录其关键码值得大小逐个插入到一个排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。
具体代码如下:
void Insertsort(int* a,int n)
{
for(int i=0;i=0)
{
if(a[end]>temp)
{
a[end+1]=a[end];
end--;
}
else
{
break;
}
}
a[end+1]=temp;
}
}
接下来我们就来了解一下希尔排序
希尔排序分为两步:
(1)预排序(接近顺序有序)
(2)插入排序(有序)
何为预排序,那就是让一个无序数组接近有序,即分组插入预排,我们可以将其分为gap组,我们假设gap为3,不同颜色代表不同的组
具体代码如下:
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}



