希尔排序是对插入排序的一种优化
插入排序是每个元素依次插入有序数组中
如果比有序数组的最大值大就依次向前比较
而希尔排序则是将数组分组
首先确定一个增量,这里我取得增量是数组长度的一半
将数组元素中距离为增量的各个元素分成一组,进行插入排序
然后增量变成原来一半,重新分组,进行插入排序
直到增量变为1,进行最后一次插入排序。
这样做的好处是可以将元素进行大幅度的移动
因为正常的插入排序每个元素只能一个一个的移动
这里由于分组了,元素的移动是按照增量数移动的
所以提高了效率
下面是希尔排序的代码
void ShellSort(int* arr,int nlength)
{
int len = nlength;
do
{
//计算增量进行分组
len = len/2;
//增量是几就有几组,循环进行插入排序
for(int i=0;i<len;i++)
{
int j; //无序的第一个元素
int k; //有序的最后一个元素
int temp; //标记无序第一个元素的值
for(j = i + len;j < nlength;j += len)
{
temp = arr[j];
k = j-len;
while(temp < arr[k] && k >= 0)
{
arr[k+len] = arr[k];
k -= len;
}
arr[k+len] = temp;
}
}
}while(len != 1);