前言
一种将无序数组进行排序的方法。
希尔排序是插入排序的一个变种。
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
