前言

一种将无序数组进行排序的方法。

希尔排序是插入排序的一个变种。
wiki 参考：https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F

对于普通的插入排序，数组无论是物理上还是逻辑上都是当作一维数组来对待。
希尔排序则将一维数组转化为逻辑上的多维数组（类似于矩阵，虽然不严谨），对矩阵的每一列进行独立的普通插入排序。通过不断的减少列的数量，最后变为只有一列的矩阵再进行独立的普通插入排序。

递归，主要思想：将任务转换为单一目的的循环，可以找到退出条件。

递归希尔排序， 主要思想：每次递归改变矩阵的列，直到矩阵列为1，插入排序结束后即退出。

环境

编辑器：vs2019
文件：.c类型

正文

代码参考：

#include <stdio.h>




// 希尔排序，从小到大
// wiki源码
// 对于学习来说，这种算法的源码，已经做出各种优化，并不能很直观的反映出逻辑。
void shell_sort(int arr[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap >>= 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}


// 希尔排序，从小到大
void shell_sort_normal(int source_array[], int source_array_length)
{
    // 参考wiki
    // 希尔排序的核心，将一维数组逻辑划分为矩阵形式，依次减少矩阵的列，最后形成只有一列的数组。在每一次划分逻辑矩阵时，均对每一列进行插入操作，让每一列变得更加有序。
    // 在代码中定义一个跨度--gap，从而生成逻辑上的矩阵。
    // gap 一般可以通过列表反复除2得出，直到为0终止(整型除法特点)
    for (int gap = source_array_length / 2; gap > 0; gap = gap / 2)
    {
        // 按列插入排序
        // 插入排序有个特点：已插入排序的数组都是有序的，因此后面的元素可以直接单向往前比较即可找到合适的位置。
        // 从插入排序得出的经验，从第二个元素开始插入，在这里就是第二行。因此 i=gap 开始。
        // 这里的插入方法借鉴于wiki，当然可以使用自己的逻辑进行插入。上一篇的【插入排序】使用的就是自己最原始直观的逻辑。
        int j;
        int tmp;
        for (int i = gap; i < source_array_length; i++)
        {
            tmp = source_array[i];
            // 开始插入，其它元素移位。按已排序数组的后端开始移位
            for (j = i - gap; j >=0; j -= gap)
            {
                // 如果当前元素 tmp 小于该位置元素，则该位置元素向后移动
                // wiki 中退出循环逻辑，通过for中的条件控制，这里为了方便思考，顾单独拿出来。
                if (tmp < source_array[j])
                {
                    // 前一个元素后移
                    source_array[j + gap] = source_array[j];
                }
                else
                {
                    // 若当前元素 tmp 不小于该位置元素，证明找到了合适的位置。接下来就是将当前位置赋值为tmp
                    // 不在else中直接赋值，是因为存在 tmp是整列最小的情况，不会进入else，直接退出了循环。因此在循环外对合适的位置赋值更加好。当然，在这里进行赋值也是可以实现的。
                    break;
                }
            }
            source_array[j + gap] = tmp;
        }
    }
}


// 递归希尔排序，从小到大
// 这里的loop_num 初始值设为 source_array_length / 2, 参考普通希尔排序的 gap，控制矩阵的列
void shell_sort_recursive(int source_array[], int source_array_length, int gap)
{
    int j;
    int tmp;
    for (int i = gap; i < source_array_length; i++)
    {
        tmp = source_array[i];
        for (j = i - gap; j >= 0; j -= gap)
        {
            if (tmp < source_array[j])
            {
                source_array[j + gap] = source_array[j];
            }
            else
            {
                break;
            }
        }
        source_array[j + gap] = tmp;
    }
    gap = gap / 2;
    if (gap <= 0)
    {
        return 0;
    }
    shell_sort_recursive(source_array, source_array_length, gap);
}


int* upset_array(int source_list[], int source_list_length)
{
    for (int i = 0; i < source_list_length; i++)
    {
        int rand_index = rand() % source_list_length;
        int tmp_value = source_list[i];
        source_list[i] = source_list[rand_index];
        source_list[rand_index] = tmp_value;
    }
    return source_list;
}


int main()
{
    // 生成随机测试列表
    int test_list[10];
    int test_list_length = sizeof(test_list) / sizeof(int);
    printf("测试列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        test_list[i] = rand() % 100;
        printf("%d ", test_list[i]);
    }
    printf("\n");


    // 希尔排序
    shell_sort_normal(test_list, test_list_length);
    printf("普通希尔排序结果： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    // 打乱数组
    upset_array(test_list, test_list_length);
    printf("打乱测试列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    // 递归希尔排序
    shell_sort_recursive(test_list, test_list_length, test_list_length / 2);
    printf("递归希尔排序结果： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");
}

执行结果参考：

image.png