希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

算法步骤

• 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

• 按增量序列个数 k，对序列进行 k 趟排序；

• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

图演示

image

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

//交换数值
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
//打印数组
void printArray(char msg[],int arr[],int len){
    printf("%s:",msg);
    for (int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}
//希尔排序
void shell_sort(int a[], int len){
    //分组:len/2,缩小增量为:g/2，直到最后每个组只有一个元素
    for(int g=len>>1;g>0;g>>=1){
        //选取下标为g的元素为要插入的元素,i累加1为一组，每个组有g个元素
        for(int i=g;i<len;i++ ){
            int temp=a[i];
            //将下标为j的元素与下标为j-g对比，即j,j-g,j-g-g...为一组，对此组做插入排序
            for(int j=i;j>0&&a[j-g]>temp;j-=g){
                a[j] = a[j-g];
                a[j-g]=temp;
            }
        }
        printf("分成%d组",g);
        printArray("",a,len);
    }
}
int main()
{
    int len=10;
    int arr[len];
    srand((unsigned)time(NULL));
    //随机生成长度为"len"的数组
    for(int i=0;i<len;i++){
        arr[i]=rand()%200;
    }
    printArray("未排序前",arr,len);
    shell_sort(arr,len);
    printArray("希尔排序",arr,len);
    //防止windows下控制台窗口闪退
    int s;
    scanf("%d",&s);
    return 0;
}

运行结果：

未排序前:163 54 134 74 10 69 167 198 57 151
分成5组:69 54 134 57 10 163 167 198 74 151
分成2组:10 54 69 57 74 151 134 163 167 198
分成1组:10 54 57 69 74 134 151 163 167 198
希尔排序:10 54 57 69 74 134 151 163 167 198