因为直接排序的元素集合越接近有序,插入排序的时间效率越高,因此希尔排序就是先让集合尽可能的接近有序,再进行一个插入排序。
我们还是将数组 arr[] = { 9,8,7,6,5,4,3,2,1 } 改为升序排列。
首先确定一个gap的值(这里取gap=3),让每隔gap-1的数进行比较并进行交换来进行一个预排序。这时再进行插入排序,就会快的多了。
但是如果数组中的较多的时候,比如数组中含有1亿个数,那么只交换一次再进行插入排序,并不能比插入排序快多少,因此我们需要调整gap的值。
因为gap的值越大,数组中大的值越快排到后面,小的数越快到前面,但是不接近有序。而gap的值越小,越接近有序,当gap等于1时,就是插入排序。因此我们可以取gap等于数组长度n或n/2等,并且在预排序时逐渐的减小gap的值,直到gap=1,就可以完成集合的排序。
| 时间复杂度 | 到 |
| 稳定性 | 不稳定 |
void ShellSort(int*arr,int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;//防止gap为0,且最后一次执行时gap一定为1
for (int i = 0; i < n - gap; i++)//最后gap个会在end+gap时被比较
{
int end = i;
int tmp = arr[i + gap];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];
end=end-gap;
}
else
break;
}
arr[end + gap] = tmp;
}
}
}



