希尔排序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