希尔排序-白红宇

希尔排序的时间复杂度，最好的情况下仍然是正序时，可达到O(n),平均复杂度为O(nlogn)。

算法思想：

　　采用跳跃式处理数组，使得数组粗粒度的实现基本有序。在进行细粒度的处理，最终使得网络在跳越数为1时，实现基本有序的排序，以减少插入排序的复杂度。

主要程序：

void shellSort(int *arr,int length){    int i,j,k;    int increment = length;    while(increment>0){        if(increment != 1)            increment = increment/3+1;        else            break;        for(i = increment; i
      
       =0 && k < arr[j] ; j-=increment){                    arr[j+increment] = arr[j];                }                arr[j+increment] = k;            }        }    }}

全部代码：

#include 
         #include 
          #include 
           int arrtest1[10] = {
      3,4,7,8,0,9,1,2,6,5};int arrtest2[10] = {
      0,1,2,3,4,5,6,7,8,9};int arrtest3[10] = {
      9,8,7,6,5,4,3,2,1,0};void copy(int *from,int *arr,int length);void print(int *arr,int length);void shellSort(int *arr,int length);int main(){    clock_t start,end;    int Arr[10];    int i;    copy(arrtest1,Arr,10);    print(Arr,10);    shellSort(Arr,10);    print(Arr,10);    start = clock();    for(i=0;i<100000;i++){        copy(arrtest1,Arr,10);        //print(Arr,10);        shellSort(Arr,10);        //print(Arr,10);    }    end = clock();    printf("first test:%d\n",end-start);    start = clock();    for(i=0;i<100000;i++){        copy(arrtest2,Arr,10);        //print(Arr,10);        shellSort(Arr,10);        //print(Arr,10);    }    end = clock();    printf("first test:%d\n",end-start);    start = clock();    for(i=0;i<100000;i++){        copy(arrtest3,Arr,10);        //print(Arr,10);        shellSort(Arr,10);        //print(Arr,10);    }    end = clock();    printf("first test:%d\n",end-start);        getchar();    return 0;}void shellSort(int *arr,int length){    int i,j,k;    int increment = length;    while(increment>0){        if(increment != 1)            increment = increment/3+1;        else            break;        for(i = increment; i
            =0 && k < arr[j] ; j-=increment){                    arr[j+increment] = arr[j];                }                arr[j+increment] = k;            }        }    }}void copy(int *from,int *arr,int length){    int i;    for(i=0;i

运行示例：

本文转自博客园xingoo的博客，原文链接：，如需转载请自行联系原博主。