【排序算法】希尔排序详解！(源码+实现)-Toy模板网

这篇具有很好参考价值的文章主要介绍了【排序算法】希尔排序详解！(源码+实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【排序算法】希尔排序详解！(源码+实现),# 排序篇,算法,排序算法,c语言,开发语言,数据结构

🎥 屿小夏：个人主页 🔥个人专栏：算法—排序篇 🌄 莫道桑榆晚，为霞尚满天！

📑前言

什么是希尔排序？希尔排序是如何实现的？它的思想和由来又是什么？
本文将从多方面，精细的带你了解希尔排序，让你彻底掌握它！

🌤️希尔排序

☁️希尔排序的由来

希尔排序（Shell Sort）是一种排序算法，由美国计算机科学家Donald Shell于1959年提出。希尔排序是插入排序的一种改进版本，旨在减少插入排序的交换操作和比较次数，从而提高排序效率。这个算法的名字是以发明者的名字命名的，虽然它也被称为“递减增量排序”。

☁️希尔排序的思想

希尔排序的关键思想是将待排序的元素分为多个子序列，然后对每个子序列进行插入排序。这些子序列是原始序列中相隔一定增量的元素组成的。然后逐渐减小增量，重复这个过程，最终将增量减小到1，完成最后一轮的插入排序，此时序列已经基本有序，只需进行少量的比较和交换操作，大大提高了排序效率。（上图展示更直观）

【排序算法】希尔排序详解！(源码+实现),# 排序篇,算法,排序算法,c语言,开发语言,数据结构

☁️希尔排序代码实现

//希尔排序(便于理解版)
void ShellSort1(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        //gap /= 2;
        gap = gap / 3 + 1;
        for (int j = 0; j < gap; j++)
        {
            for (int i = j; i < n - gap; i += gap)
            {
                int end = i;
                int tmp = a[end + gap];
                while (end >= 0)
                {
                    if (tmp < a[end])
                    {
                        a[end + gap] = a[end];
                        end -= gap;
                    }
                    else
                    {
                        break;
                    }
                }
                a[end + gap] = tmp;
            }
        }
    }
}
//希尔排序(少一层循环版)
void ShellSort2(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        //gap /= 2;
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                    break;
            }
            a[end + gap] = tmp;
        }
    }
}

☁️代码解析

⭐ShellSort1

这是一个较为直观的实现方式，它使用了两层循环。外层循环控制间隔gap的大小，初始时将gap设为数组长度n。在每次循环中，通过将gap除以3并加1的方式来缩小间隔gap的值。内层循环用于遍历每个间隔为gap的子序列，并进行插入排序。步骤如下：

初始化间隔gap为数组长度n。
当gap大于1时，进行以下操作：
- 将gap除以3并加1，更新gap的值。
- 对于每个间隔为gap的子序列，进行插入排序。
  - 从子序列的第一个元素开始，逐个向后遍历子序列中的元素。
  - 对于当前遍历到的元素，将其与之前的元素进行比较。如果比之前的元素小，则将之前的元素后移gap个位置。
  - 重复上述步骤，直到找到合适的位置插入当前元素。
缩小间隔gap的值。
重复步骤2和3，直到gap为1。

⭐ShellSort2

这是对ShellSort1函数的一种优化，它减少了一层循环。具体实现如下：

初始化间隔gap为数组长度n。
当gap大于1时，进行以下操作：
- 将gap除以3并加1，更新gap的值。
- 对于每个间隔为gap的子序列，进行插入排序。
  - 从子序列的第一个元素开始，逐个向后遍历子序列中的元素。
  - 对于当前遍历到的元素，将其与之前的元素进行比较。如果比之前的元素小，则将之前的元素后移gap个位置。
  - 重复上述步骤，直到找到合适的位置插入当前元素。
缩小间隔gap的值。
重复步骤2和3，直到gap为1。

☁️希尔排序特性总结

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在有些书中给出的
希尔排序的时间复杂度都不固定：

🌤️全篇总结

经过对希尔排序的由来，思想以及希尔排序是如何实现的，并且对希尔的特性进行了总结。

☁️ 好了，由于篇幅有限,本章专对希尔排序进行了详细的讲解，后序会出更多的排序算法哦！
看到这里了还不给博主留个：👍 点赞🌟收藏 ⭐️ 关注！
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。
【排序算法】希尔排序详解！(源码+实现),# 排序篇,算法,排序算法,c语言,开发语言,数据结构文章来源地址https://www.toymoban.com/news/detail-743796.html