【排序算法】希尔排序详解！(源码+实现)

在这里插入图片描述

🎥 屿小夏：
个人主页

🔥个人专栏：
算法—排序篇

🌄 莫道桑榆晚，为霞尚满天！

文章目录

📑前言
🌤️希尔排序
- ☁️希尔排序的由来
- ☁️希尔排序的思想
- ☁️希尔排序代码实现
- ☁️代码解析
- - ⭐ShellSort1
  - ⭐ShellSort2
- ☁️希尔排序特性总结
🌤️全篇总结

📑前言

什么是希尔排序？希尔排序是如何实现的？它的思想和由来又是什么？

本文将从多方面，精细的带你了解希尔排序，让你彻底掌握它！

🌤️希尔排序

☁️希尔排序的由来

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

☁️希尔排序的思想

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

在这里插入图片描述

☁️希尔排序代码实现

//希尔排序(便于理解版)
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。