希尔排序算法——C/C++

末蓝、 2022-10-01 11:57 163阅读 0赞

## 希尔排序 ##

### 1. 算法思想 ###

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。  
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dn=1(<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

### 2. 排序步骤 ###

2.1、第一次，取一个增量increment，一般是increment=n/3（最开始是n/2，可以根据自己想法修改，只是影响计算时间）。
    2.2、把相差为增量倍数的分为一组。
    2.3、分组后，在组内进行直接插入排序。
    2.4、重复上述三步，直到increment=1结束。

### 3. 动态演示 ###

![在这里插入图片描述][1ee595797336e53d3a40a3e708c2ddf6.png]

### 4. 完整代码 ###

值得说一下，插入排序的间隔是增量大小  
我写的有点复杂，套了四个加一个判断，不过应该条理清晰，理解容易。

#include <stdio.h>
    
    void display(int array[], int size) {
        
        for (int i = 0; i < size; i++) {
        
            printf("%d ", array[i]);
        }
        printf("\n");
    }
    
    void ShellSort(int array[], int size) {
        
        // 初始化临时值，增量
        int key       = 0;
        int increment = size;
        do {
        
            // 每次减小增量，直到increment = 1
            increment = increment / 2;
            printf("%d\n", increment);
            for (int i = 0; i < increment; i++) {
        
                // 对每个划分进行直接插入排序
                for (int j = i + increment; j < size; j = j + increment) {
        
                    if (array[j] < array[j - increment]) {
        
                        key   = array[j];
                        int k = j - increment;
                        do {
        
                            // 移动元素并寻找位置
                            array[k + increment] = array[k];
                            k                    = k - increment;
                        } while (key < array[k] && k >= 0);
                        // 插入元素
                        array[k + increment] = key;
                    }
                }
    
                // 打印每次结果
                display(array, size);
            }
        } while (increment != 1);
    }
    
    int main() {
        
        int array[] = {
        49, 38, 65, 97, 76, 13, 27, 49, 10};
        int size    = sizeof(array) / sizeof(int);
    
        //打印原始数据
        printf("%d \n", size);
        display(array, size);
        ShellSort(array, size);
    
        return 0;
    }

### 5. 结果展示 ###

（显示每次排序结果）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

### 6. 算法分析 ###

时间复杂度：

1.  最好O(n log^1.3 n)
2.  最坏O(n log^2 n)

空间复杂度：O(1)

稳定性：不稳定

[1ee595797336e53d3a40a3e708c2ddf6.png]: /images/20220118/10ba3230ea37490e8900e41bc22a03b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20220118/a966ca9871c545ddabe417cd6a9349d3.png