当前位置：首页 > news >正文

排序算法系列之（五）——为目标打好基础的希尔排序

news 来源：原创 2024/5/6 16:24:48

前言

刚刚分析过的插入排序通常被叫做简单插入排序或者直接插入排序，而这篇文章刚好以插入排序为基础来说说希尔排序，还是先从名字开始，结果发现完全没有头绪，说实话第一次听说这个排序时还以为是个特别神奇的高端算法，结果了解一番之后发现其实是一个被改造的插入排序，“希尔”居然是发明者的名字，所以从名字来判断算法思想在这里行不通，甚至说快速排序起码说明了这种方法排序快，而希尔排序等于什么都没说。

希尔排序的基础是插入排序，整个排序也是在新元素不断插入到有序序列适当位置的过程中完成的，唯一的不同的就是通过不同的步长将整个序列划分为不同的小序列不断插入，直到步长为1时就退化成了最基本的直接插入排序，但是此时整个序列已经“基本”有序了，需要交换的元素对比一开始直接插入的方法明显减少，从而可以加快排序的速度，因为最后步长为1的一次插入排序与简单插入排序完全相同，所以前面的几趟排序完全可以看做是最后的排序目标“打基础”，让最后一次的排序序列尽可能有序，下面描述一下希尔排序的过程，前提是你已经了解简单插入排序的过程，可以参考文章抓扑克牌风格的插入排序熟悉一下。

希尔排序

希尔排序的有一个关键的元素是步长，关于步长的选择有很多种方法，比如只选奇数，选择互为质数等等，其目的就是为了减少重复比较的次数，我们现在只为了解希尔排序的过程，所以先选择一种简单的步长选定方法，以元素个数的一半为基础，每次减少一半直到步长降为1，比如10个元素的步长选择分别为5,2,1，本质思想就是分别以步长5,2,1对整个待排序列进行简单的插入排序，最后就完成了整个序列的排序。

我们用物品重量排序作为例子吧，原来插入排序的例子是将新得到的扑克牌不断插入到有序序列中得到最终排序，这次可以直接先给出物品质量序列的初始排列，假设为99, 34, 54, 65, 11, 1, 5, 12, 89, 42，一共10件物品摆在面前，目标为将物品重量从小到大排序，首先选取步长5开始排序过程：

最开始的排序序列如下:
99, 34, 54, 65, 11, 1, 5, 12, 89, 42
以步长为5将整个序列分为5组，分组情况如下：
99, _, _, _, _, 1, _, _, _, _
_, 34, _, _, _, _, 5, _, _, _
_, _, 54, _, _, _, _, 12, _, _
_, _, _, 65, _, _, _, _, 89, _
_, _, _, _, 11, _, _, _, _, 42
将这五组子序列分别使用简单插入排序，得到以下序列：
1, _, _, _, _, 99, _, _, _, _
_, 5, _, _, _, _, 34, _, _, _
_, _, 12, _, _, _, _, 54, _, _
_, _, _, 65, _, _, _, _, 89, _
_, _, _, _, 11, _, _, _, _, 42
这五个子序列组成完整的中间临时序列为：
1, 5, 12, 65, 11, 99, 34, 54, 89, 42
然后以步长为2将整个序列划分，得到以下分组情况：
1, _, 12, _, 11, _, 34, _, 89, _
_, 5, _, 65, _, 99, _, 54, _, 42
将这两组子序列使用简单插入排序，得到以下序列：
1, _, 11, _, 12, _, 34, _, 89, _
_, 5, _, 42, _, 54, _, 65, _, 99
将子序列整体来看得到中间临时序列：
1, 5, 11, 42, 12, 54, 34, 65, 89, 99
最后再将整个待排序列进行一次简单插入排序，便可得到最终排好的序列，实际上最后一次插入排序只有中间几个元素需要移动了：
1, 5, 11, 12, 34, 42, 54, 65, 89, 99

代码实现

/*
功能：  交换两个变量
参数：  element1--被交换的第一个元素的地址
        element2--被交换的第二个元素的地址
返回值：无
注意：  只用来表示思路，不考虑指针为空等特殊情况
*/
void swap_data(int* element1, int* element2)
{
    int middle_value = *element1;
    *element1 = *element2;
    *element2 = middle_value;
}

/*
功能：  希尔排序，实现数组元素从小到大排列
参数：  array--表示待排序的数组，此处会退化成指针
        count--数组元素的个数
返回值：无
注意： 只用来表示思路，不考虑指针为空等特殊情况
*/
void shell_sort(int array[], int count)
{
    int step = count / 2;
    while (step > 0)
    {
        for (int pos = step; pos < count; ++pos)
        {
            for (int insert_index = pos; insert_index >= step; insert_index -= step)
            {
                if (array[insert_index] < array[insert_index - step])
                    swap_data(&array[insert_index], &array[insert_index - step]);
            }
        }
        step /= 2;
    }
}

对比插入排序源代码，找找不同

void insert_sort(int array[], int count)
{
    for (int pos = 1; pos < count; ++pos)
    {
        for (int insert_index = pos; insert_index > 0; --insert_index)
        {
            if (array[insert_index] < array[insert_index - 1])
                swap_data(&array[insert_index], &array[insert_index - 1]);
        }
    }
}

代码分析

以上代码就是希尔排序的实现方式了，对比直接插入的源代码发现，如果将希尔排序的初始步长设置成1，那么整个希尔排序的代码就和简单插入排序完全一样了，这也符合我们之前分析的过程，其实希尔排序就是分多次，每次用不同的步长执行简单插入排序。

还有一点就是代码执行的过程与上面示例中的分组插入看起来有些不同，只是因为这个写起来更方便一些，分组只是为了人脑能更快的理解算法的思想，但是代码编写时还要考虑复杂性，将数据拆分成几组然后分别进行插入排序完全可以做到，但是实际上完全没有必要。

比如分成两组排序的那一步，直观上先排索引为0,2,4,6,8上的元素，依次做插入操作，然后排索引为1,3,5,7,9上的元素，在依次做插入操作，但是在实现的代码中就做了变通，反正都要做插入操作，并且步长都是2，所以可以直接对索引是0,1,2,3,4,5,6,7,8,9上的元素做插入排序，只要注意步长是2，就不会影响到其他组（实际上并不存在）的元素了，整个过程顺着代码，一步步执行就明白了。