【12，2，16，30，8，128，4，10，20，6，18】按照希尔排序

Question

上面的数字请按照希尔排序，并且有每一步详细的过程，还有它这种算法好在哪里，
不还是要用直接插入排序吗。

Answer 1

写了一个shell排序，把每一步的输出结果打印了一下

#include <stdio.h>

void shell_sort(int array[], int length){
    int i;
    int j;
    int k;
    int gap;
    int temp;
    for(gap=length/2; gap>0; gap=gap/2){
        for(i=0; i<gap; i++){
            for (int ii = 0; ii < length; ii++)
                printf("%d ", array[ii]);
            printf("\n");
            for(j=i+gap; j<length; j=j+gap){
                if(array[j] < array[j - gap]){
                    temp = array[j];
                    k = j - gap;
                    while(k>=0 && array[k]>temp){
                        array[k + gap] = array[k];
                        k = k - gap;
                    }
                    array[k + gap] = temp;
                }
            }
        }
    }
}

int main()
{
    int arr[] = {12,2,16,30,8,128,4,10,20,6,18};
    shell_sort(arr, 11);
    for (int ii = 0; ii < 11; ii++)
        printf("%d ", arr[ii]);
   printf("\n");
   return 0;
}

12 2 16 30 8 128 4 10 20 6 18
12 2 16 30 8 18 4 10 20 6 128
12 2 16 30 8 18 4 10 20 6 128
12 2 10 30 8 18 4 16 20 6 128
12 2 10 20 8 18 4 16 30 6 128
12 2 10 20 6 18 4 16 30 8 128
4 2 6 20 10 18 12 16 30 8 128
4 2 6 8 10 16 12 18 30 20 128
2 4 6 8 10 12 16 18 20 30 128

如果不理解，这里有动画过程，自己看看吧
https://en.wikipedia.org/wiki/Shellsort