十大排序之希尔排序（C语言实现）

十大排序之希尔排序（C语言实现） 2022-05-22 725

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

从上面我们很容易看出来，它是插入排序的高级版

先说说什么是插入排序插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
那么什么是希尔排序简单来说，希尔排序是将较大的数据集合逻辑上分割成若干个小的集合，然后对每个分组分别进行插入排序。

既然说希尔排序是插入排序的升级版，那么究竟优化在了什么地方呢？？

希尔排序比插入排序做出的优化 • 希尔排序在排序前：将一个序列分成了好几个序列 • 在第一趟排序时：将这几个序列做插入排序。排序后，部分较大的数字往后靠，部分较小的数字往前靠 • 在第二趟排序时：将这个序列又分了好几个序列做插入排序(但比第一次分的数要少,ps:如果第一次分5个，第二次可能就2个了)。排序后，部分较大的数字往后靠，部分较小的数字往前靠 … • 在第n趟排序时：将这个序列又分了好几个序列(直到剩下一个序列)，从宏观上看，此序列就基本是有序的了。这时就用简单插入排序将数列直至已序
代码实现

#include<stdio.h>
int main(){
          
   
    int a[10];
    for (int i = 0;i < 10;i++) {
          
   
        scanf_s("%d" ,& a[i]);
    }
    int i, j, itemp, gap = 10;
    while (gap >1)
    {
          
   
        gap = gap / 2;                /*增量缩小，每次减半*/
        for ( i = gap;i < 10;i+=gap)
            if (a[i] < a[i - gap]) {
          
   
                 j = i - gap;
                 itemp = a[i];
                for (;itemp < a[j] && j>-1;j-=gap) {
          
   
                    a[j + gap] = a[j];
                }
                a[j + gap] = itemp;
            }
    }
    for (int n = 0;n < 10;n++)
        printf_s("%d  ", a[n]);
    printf_s("
");
    return 0;
}