Home

# Shell Sort

##1. 介绍
希尔排序是插入排序的一种，它的步骤如下：

1
2
3
2.对这些分组内的项进行单独的直接插入排序。
3.当每个组内的排序完成后，再将整歌序列按另一个更小的Gap来进行分组。
4.重复2、3，直到gap的值变为1，对整个序列进行一次直接插入排序。

##2.Gap 的选值
gap 的选值可以只用最简单的，每次都区 gap／2，第一个 gap 取 arr.len/2。也有一些更加效率的选值方式，此处不提了。

##3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
C语言： 
    void shellSort(int* arr，int len){
    int gap = len/2;
    while(gap>=1){
        for(int i = gap;i<len;i++){
            int temp = arr[i];
            int k = i-gap;
            while(k>=0&&arr[k]>arr[i]){
                arr[i]=arr[k];
                k-=gap;
            }
            // if (k != i - gap) {
                arr[k+gap] = temp;
            }
            gap /=2;
        }
    }