1、如何进行希尔排序
希尔排序是直接插入排序的优化，具体实现是先进行以gap间隔分别进行排序，将数组排成快要接近有序，最后一次gap为1的排序，实际上是直接插入排序，因为直接插入排序在接近有序时时间复杂度最小，所以以此进行优化，gap大于1的排序称为预排序。
2、程序
void ShellSort(int* a,size_t size)
{
assert(a);
int gap = size;
while(gap>1)
{
gap = gap/3+1;//保证最后一次gap为1
//多路排序并行
for(int i = 0; i < size-gap; i++)
{
int end = i;
int tmp = a[end + gap];
while(end >= 0 && tmp < a[end])//间距为gap的插入排序
{
a[end+gap] = a[end];
end -= gap;
}
a[end+gap] = tmp;
}
}
}3、时间复杂度
时间复杂度在O(N)和O(N*N)之间，大概是O(N^1.25 - 1.6N^1.25)。在初始数组数据已经接近有序时，优化效率最低。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
