众所周知，排序算法最重要的就是速度，但是前边介绍的几个算法时间复杂度都是n的平方
这个问题其实困扰了计算机界前辈们很久，一度有人认为“排序算法时间复杂度不可能突破n方”
但是，终有一天还是有科学家发现了，并且接连就出现好几种可以超越n方的排序算法，把内培训算法的时间复杂度提升到了nlogn
希尔排序的时间复杂度是
，比前边几种的
要好
，比前边几种的要好
事实上还是直接插入排序，然后分成几个小组分别排序
#include
void InsertSort(int k[], int n)
{
int i, j, temp;
int gap = n;
do
{
gap = gap/3 + 1;
for( i=gap; i < n; i++ )
{
if( k[i] < k[i-gap] )
{
temp = k[i];
for( j=i-gap; k[j] > temp; j-=gap )
{
k[j+gap] = k[j];
}
k[j+gap] = temp;
}
}
}while(gap > 1);
}
int main()
{
int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
InsertSort(a, 10);
printf("排序后的结果是：");
for( i=0; i < 10; i++ )
{
printf("%d", a[i]);
}
printf("\n\n");
return 0;
}
