排序之希尔排序
程序员文章站
2024-03-16 11:42:22
...
一、定义
希尔排序为较复杂的一种排序算法,其时间复杂度为nlog2n(这是平均复杂度),它是一种不
稳定的排序方法但它也只是插入排序的一种(被优化过),对中等大小规模的数据排序时表现良
好,但当数据规模变的非常大时希尔排序并不是最优的方法。
算法思想:其基本的思想和插入算法是相同的但是,它并不是以相邻之间进行对比而是分组进行
对比,具体思想见下图。
二、使用
void shell_sort(int *p,int length)
{
int gap = length;
int s = 0;
int i=0,j=0;
do
{
gap = gap/3+1;//初始时增量(行业规范即长度除以三后加一)
for(i=gap;i<length;i+=gap)//希尔排序本体
{
s = p[i];
for (j=i;j>0&&(s>p[j-gap]);j-=gap)
{
p[j] = p[j-gap];
}
p[j] = s;
}
}while(gap>1);
for (i=0;i<10;i++)
{
printf("%d\n",p[i]);
}
}
int main()
{
int array[10]= {49,38,65,97,76,13,27,48,55,4};
shell_sort(array,10);
}
欢迎大家指出不足之处