算法基础：排序算法：希尔排序

心已赠人 2022-11-20 09:48 180阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]  
希尔排序是一个年过花甲的排序算法，是最早一批冲进时间复杂度n平方之内的算法之一，本质上是插入算法的优化。由Shell-Metzner在1959年所提出，在很长一段时间内都是以希尔排序命名，像我这样的古老的程序员念书的时候，这个排序还是被称为希尔排序的。据说希尔本人认为这个算法不应该以他的名字命名，如果根据希尔排序的原理或者实现方式来命名的话，它可能会被命名为“一种优化的插入排序算法”或者“一种改进的增量递减的插入排序改进算法”，虽然这更像一个专利的名称。这篇文章继续介绍一下希尔排序的主要要点和实现。

### 目录 ###

*  算法思路
 *  算法要点
 *  模拟实现
 *  结果验证

--------------------

# 算法思路 #

>  *  算法的思路非常简单，希尔排序是在插入排序的基础上进行的，增量递减的插入排序改进是希尔算法的核心内容，增量在算法中被称为增量，比如一个待排序列有10个元素，增量递减的思路可以进行自行定制，比如除2，首次增量为10/2=5，然后接下来为5/2=2，然后2/2=1，所以称为增量递减。

--------------------

# 算法要点 #

希尔排序的排序的要点几乎是没有什么要点：

*  外层循环：实现增量递减，这里是/2的方式，还有很多其他的方式可自行拓展
 *  插入排序：内层的两层循环完全就是插入排序，没有任何变动，唯一的区别是标准的插入排序是gap是1，而这里使用递减的gap换掉。

# 模拟实现 #

*  插入排序：在此处仍然列出来就是为了证明，希尔排序使用的完全是插入排序的核

void insert_sort(int* arr, int num) { 
        for (int i=1; i<num; i++) { 
            int value = arr[i], j=i-1;
            for (j=i-1; j>=0 && arr[j] > value; j--) arr[j+1] = arr[j];
            arr[++j] = value;
        }
    }

*  希尔排序

void shell_sort(int* arr, int num) { 
        int gap=num/2;
        while (gap) { 
            for (int i=gap; i<num; i++) { 
                int value = arr[i], j=i-gap;
                for (j=i-gap; j>=0 && arr[j] > value; j-=gap) arr[j+gap]=arr[j];
                arr[j+gap]=value;
            }
            gap /= 2;
        }
    }

> 比较一下while中的两层循环会发现，将1换成gap，代码和变量完全不需要做任何变动。

--------------------

# 结果验证 #

加上打印和调用的示例代码，可以使用如下方式进行验证

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    void shell_sort(int* arr, int num) { 
        int gap=num/2;
        while (gap) { 
            for (int i=gap; i<num; i++) { 
                int value = arr[i], j=i-gap;
                for (j=i-gap; j>=0 && arr[j] > value; j-=gap) arr[j+gap]=arr[j];
                arr[j+gap]=value;
            }
            gap /= 2;
        }
    }
    
    void print_array(int* arr, int num) { 
        for (int i=0; i<num; i++) printf("%d ",arr[i]);
        printf("\n");
    }
    
    int main() { 
        int n = 0;
        while (scanf("%d",&n) != EOF) { 
            int* array = (int *)malloc(sizeof(int)*n);
            memset(array,0,sizeof(int)*n);
            for (int i=0; i<n; i++) { 
                scanf("%d",&array[i]);
            }
            shell_sort(array,n);
            print_array(array,n);
            free(array); array= NULL;
        }
    }

执行结果示例

8
    9 8 7 6 5 4 3 2
    2 3 4 5 6 7 8 9

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/5b8d08517d844e2cbde5429ec9ab5f2f.png