排序方法（3）：希尔排序

迈不过友情╰ 2022-05-28 13:36 47阅读 0赞

# 希尔排序 #

参考：  
[https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F][https_baike.baidu.com_item_E5_B8_8C_E5_B0_94_E6_8E_92_E5_BA_8F]

[http://cuijiahua.com/blog/2017/12/algorithm\_3.html][http_cuijiahua.com_blog_2017_12_algorithm_3.html]

## 一、原理 ##

希尔排序是插入排序的一种，又称“缩小增量排序”，是直接插入排序的一种高效改进版。

## 二、步骤 ##

*  1、先取一个增量a1,然后将待排序的序列按照将距离为a1的数放在一组中的原则分成n组，（最后不够a1个的数也为一组）
 *  2、将所有组数分别进行直接插入排序
 *  3、排好序后再将所有组的数拼接在一起
 *  4、重新选择一个增量a2，使得a2<a1，然后重复上诉步骤即可，直到增量为1，排序完成

## 三、例子 ##

假设有一组数\{0,10,1,2,8,5,9,7,3,4,6\}，增量步长为3进行排序：

0    2    9    4
    10   8    7    6
    1    5    3

对每组进行直接插入语排序

0    2    4    9
    6    7    8    10
    1    3    5

将上述每组元素依此拼接在一起得到\{0,2,4,9,6,7,8,10,1,3,5\},然后在以2为增量步长进行排序：

0    4    6    8    1    5
    2    9    7    10   3

对每组进行直接插入排序

0    1    4    5    6    8
    2    3    7    9    10

最后再以1为增量步长进行排序（就是简单的直接插入排序了）。

## 四、算法实现 ##

### C语言 ###

#include "stdio.h"
    
    void shell_sort(int a[], int n);
    
    void shell_sort(int a[], int n)
    {
        int gap,i,j,temp,loop_num=0;
        for (gap = n >> 1; gap > 0; gap >>=1)
        {
            loop_num++;
            for (i = gap; i < n; i++)
            {
                temp = a[i];
                j = i - gap;
                while (j >= 0 && a[j]>temp)
                {
                    a[j + gap] = a[j];
                    j -= gap;
                }
                a[j + gap] = temp;
            }
            printf("第%d次循环,gap=%d：\t", loop_num,gap);
            for (j = 0; j < n; j++)
            {
                printf("%d\t", a[j]);
            }
            printf("\n");
        }
    }
    
    int main()
    {
            int number[] = { 0,10,1,2,8,5,9,7,3,4,6 };
            int i;
            int n = sizeof(number) / sizeof(number[0]);
            printf("原始数据：\n");
            for (i = 0; i < n; i++)
            {
                printf("%d\t", number[i]);
            }
            printf("\n\n");
    
            shell_sort(number, n);
            printf("\n返回结果：\n");
            for (i = 0; i < n; i++)
            {
                printf("%d\t", number[i]);
            }
            printf("\n");
    }

### 运行结果 ###

![这里写图片描述][SouthEast]

[https_baike.baidu.com_item_E5_B8_8C_E5_B0_94_E6_8E_92_E5_BA_8F]: https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
[http_cuijiahua.com_blog_2017_12_algorithm_3.html]: http://cuijiahua.com/blog/2017/12/algorithm_3.html
[SouthEast]: /images/20220528/6d0fc8afb108432888d0135fd06dfd4a.png