希尔排序

（1）希尔排序又称缩小增量排序，是对直接插入排序的改进方法。它的基本思想是，将整个待排序序列分割为若干个较小的子序列分别进行排序；在待排序序列的记录达到基本有序时再对整个序列进行一次排序。希尔排序子序列的构成不是简单地逐段分割，而是将相隔某个增量的记录组成一个子序列。

（2）希尔排序的主要步骤：

① 首先确定一个整数d1

② 再继续选择d2

③ 继续取di+1

（3）希尔排序中各组中的排序可以采用直接插入排序，但是排序速度要比直接插入速度快得多。当di取值大时，组内元素个数少，排序速度快，随着di的逐渐减小，组内元素个数增多，但是各元素已接近最终的排序位置，所以位置的调整不需要很多，因而整个希尔排序速度比直接插入排序速度快。

（4）希尔排序算法

void Shellinsert(int list[],int dk,int n){
    int i,j;
    for(i=dk+1;i<=n;i++){
        if(list[i]
            list[0]=list[i];
            for(j=i-dk;j>0&&list[0]
                list[j+dk]=list[j];
            }
            list[j+dk]=list[0];
        }
    }
}
void ShellSort(int list[],int dlta[],int t,int n){
    int i,k;
    for(k=0;k
        Shellinsert(list,dlta[k],n);
    }
}

（5）完整程序

#include
#define N 20
int list[N+1];
void insertSort(int list[],int n){
    int i,j;
    for(i=2;i<=n;i++){
        list[0]=list[i];
        j=i-1;
        while(j>0&&list[0]
            list[j+1]=list[j];
            j--;
        }
        list[j+1]=list[0];
    }
}
void bubbleSort(int list[],int n){
    int i=1,j,t,flag=1;
    for(i=1;i
        flag=0;
        for(j=1;j<=n-1;j++){
            if(list[j]>list[j+1]){
                t=list[j];
                list[j]=list[j+1];
                list[j+1]=t;
                flag=1;
            }
        }
    }
}
void SelectSort(int list[],int n){
    int i,j,k,temp;
    for(i=1;i<=n-1;++i){
        k=i;
        for(j=i+1;j<=n;j++){
            if(list[j]             k=j;
        }
        if(i!=k){
            temp=list[i];
            list[i]=list[k];
            list[k]=temp;
        }
    }
} 
void Shellinsert(int list[],int dk,int n){
    int i,j;
    for(i=dk+1;i<=n;i++){
        if(list[i]
            list[0]=list[i];
            for(j=i-dk;j>0&&list[0]
                list[j+dk]=list[j];
            }
            list[j+dk]=list[0];
        }
    }
}
void ShellSort(int list[],int dlta[],int t,int n){
    int i,k;
    for(k=0;k
        Shellinsert(list,dlta[k],n);
    }
}
int main(){
    int i,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&list[i]);
    }
    //insertSort(list,n);
    //bubbleSort(list,n);
    //SelectSort(list,n);
    int dlta[3]={5,3,1};
    ShellSort(list,dlta,3,n);
    for(i=1;i<=n;i++){
        printf("%d ",list[i]);
    } 
    return 0;
}