希尔排序shellsort的C实现

     shell排序是一种比较高效的排序算法，虽然理论上不是NlogN的算法复杂度。但是不影响shell的速度。

     快速排序quicksort存在两个问题，一个是递归实现，有可能栈溢出。第二个问题是，快速排序在极端情况下，算法复杂度有可能退化成（N^2）。

     如果不确定使用快速排序是否正确的场合，使用shell排序是个不错的选择，因为shell排序，不需要对输入的数据进行太多的分析调查。

     shell排序的算法复杂度，与shellsort中的步长有很大的关系。选择一个好的步长对shellsort很关键。shellsort的始祖Shell提出算法时给出的步长序列是 (2^n)， 后续的研究证明是很烂的一个步长序列。

     简单的步长序列有：

1）  3*n+1   即（1，4，13，40，121，364，1093，3280……）           算法复杂度低于O（N^1.5）

2）  4^(i+1) + 3*2^(i) + 1  即（1，8，23，77，281，1073，4193……） 算法复杂度低于O（N^(4/3)）

OK，理论部分到此结束，下面给出代码。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void shellsort(int array[],int l,int r)
{
                int i,j,hop;
                int curitem;
                for( hop = 1;hop <= (r-l)/9;hop=3*hop+1)
                                ;

                for(;hop>0;hop/=3)
                {
                                for(i = l+hop;i <=  r ; i++)
                                {
                                                j = i;
                                                curitem= array[i];
                                                while( (j>=(l+hop)) && curitem < array[j-hop])
                                                {
                                                                array[j] = array[j-hop];
                                                                j = j-hop;
                                                }
                                                array[j] = curitem;
                                }
                }
}


int test_shellsort()
{
                int i;
                int number = 50;

                int *array = malloc(number*sizeof(int));
                if(array == NULL)
                {
                                printf("malloc failed\n");
                                return -1;
                }


                printf("----------------------------------------before shell sort--------------\n");
                srand(time(NULL));
                for(i = 0;i<number;i++)
                {
                                array[i] = rand()%10000;
                                printf("\tarray[%6d] = %6d\n",i,array[i]);
                }

                printf("----------------------------------------after shell sort-----------------\n");

                shellsort(array,0,number-1);
                for(i = 0;i<number;i++)
                {
                        printf("\tarray[%6d] = %6d\n",i,array[i]);
                }
                free(array);
                return 0;

}
int main()
{
                test_shellsort();
                return 0;
}

----------------------------------------before shell sort--------------
array[     0] =   8164
array[     1] =   4430
array[     2] =   6981
array[     3] =   5061
array[     4] =   6818
array[     5] =   9343
array[     6] =   4056
array[     7] =   4840
array[     8] =    449
array[     9] =   5046
array[    10] =   5614
array[    11] =   1229
array[    12] =   9509
array[    13] =   9703
array[    14] =   9677
array[    15] =   1856
array[    16] =     45
array[    17] =   4645
array[    18] =   5968
array[    19] =   9310
array[    20] =   7043
array[    21] =   5083
array[    22] =   4170
array[    23] =   7518
array[    24] =   4596
array[    25] =   4611
array[    26] =   1613
array[    27] =   5947
array[    28] =   6859
array[    29] =   5396
array[    30] =   6291
array[    31] =   1375
array[    32] =   6179
array[    33] =   9624
array[    34] =   6437
array[    35] =   2997
array[    36] =   5320
array[    37] =    493
array[    38] =   4190
array[    39] =   2121
array[    40] =   1891
array[    41] =   6156
array[    42] =   3350
array[    43] =   1401
array[    44] =   5859
array[    45] =   3027
array[    46] =   9609
array[    47] =   5905
array[    48] =   4025
array[    49] =   5577
----------------------------------------after shell sort-----------------
array[     0] =     45
array[     1] =    449
array[     2] =    493
array[     3] =   1229
array[     4] =   1375
array[     5] =   1401
array[     6] =   1613
array[     7] =   1856
array[     8] =   1891
array[     9] =   2121
array[    10] =   2997
array[    11] =   3027
array[    12] =   3350
array[    13] =   4025
array[    14] =   4056
array[    15] =   4170
array[    16] =   4190
array[    17] =   4430
array[    18] =   4596
array[    19] =   4611
array[    20] =   4645
array[    21] =   4840
array[    22] =   5046
array[    23] =   5061
array[    24] =   5083
array[    25] =   5320
array[    26] =   5396
array[    27] =   5577
array[    28] =   5614
array[    29] =   5859
array[    30] =   5905
array[    31] =   5947
array[    32] =   5968
array[    33] =   6156
array[    34] =   6179
array[    35] =   6291
array[    36] =   6437
array[    37] =   6818
array[    38] =   6859
array[    39] =   6981
array[    40] =   7043
array[    41] =   7518
array[    42] =   8164
array[    43] =   9310
array[    44] =   9343
array[    45] =   9509
array[    46] =   9609
array[    47] =   9624
array[    48] =   9677
array[    49] =   9703

real	0m0.002s
user	0m0.000s
sys	0m0.004s

参考文献：1 算法:C语言实现