希尔排序是直接插入排序的优化,通过预处理先将目标数组进行简单的排序,使目标数组进行一定的规则化,以达到简化直接插入排序次数的目的
例如我们现在有数组a[8]{5,8,6,3,9,2,1,7}现将其以数组长度的一半为跨度分组,也就是每隔4个元素一组,在a数组中5与9一组,8与2一组,6与1一组3与7一组,进行直接插入排序,然后我们得到新的数组 a{5,2,1,3,9,8,6,7} ,继续分组,这次以2为跨度分组即,5,1,9,6一组,2,3,8,7一组分别对两组进行直接插入排序于是得到a{1,2,5,3,6,7,9,8},最后以1为跨度进行分组,也就是直接进行直接插入排序
也有更加高效的其他分组方法,其中最具代表性的是Hibbard增量和Sedgewick增量。
Hibbard的增量序列如下:
1,3,7,15……
通项公式 2^k-1
利用此种增量方式的希尔排序,最坏时间复杂度是O(n^(3/2))
Sedgewick的增量序列如下:
1, 5, 19, 41, 109……
通项公式
$$
94^k - 92^k + 1 或者 4^k - 3*2^k + 1
$$
利用此种增量方式的希尔排序,最坏时间复杂度是O(n^(4/3))
#include<stdio.h>
#include<stdlib.h>
void Shell_Sort(int *pArr,int size){
int i = 0;
int key = 0;
int end = 0;
int gap = 3;
while (gap > 0)
{
for (i = gap; i < size; i++)
{
key = pArr[i];
end = i - gap;
while (end >= 0 && key<pArr[end])
{
pArr[end + gap] = pArr[end];
end=end-gap;
}
pArr[end + gap] = key;
}
gap--;
}
}
int main(){
int i = 0;
int array[9] = { 2, 6, 4, 9, 5, 8, 7, 0, 1 };
int size = sizeof(array) / sizeof(array[0]);
Shell_Sort(array, size);
for (i = 0; i < size; i++)
{
printf("%d ", array[i]);
}
printf("\n");
system("pause");
return 0;
}
Comments NOTHING