【数据结构--八大排序】之希尔排序

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤

📃个人主页 ：阿然成长日记 👈点击可跳转

📆 个人专栏： 🔹数据结构与算法🔹C语言进阶

🚩 不能则学，不知则问，耻于问人，决无长进

🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

文章目录

• 一、希尔定义：
• 二、希尔排序原理
• 三、希尔排序原理图

• 1.gap为3：
• 2.gap为2：
• 3.gap为1：

• 四、细节剖析

• 第1步：`i=0`; a[tmp] > a[end]不做交换
• 第2步：`i=1`; a[tmp] > a[end]不做交换
• 第3步：`i=2`; a[tmp] < a[end]交换
• 第3步：`i=2`; a[tmp] > a[end] 不交换

• 第5步：`i=3`; a[tmp] > a[end]不交换
• 第6步：`i=3`; a[tmp] > a[end]不交换
• 停止

• 五、代码展示：
• 六、测试结果
• 七、 时间复杂度

前言：

本篇将开始希尔排序的讲解。本篇文章适合刚开始学习希尔排序的同学，总结的很全面，整理的很清楚，希望能帮到你，加油！

一、希尔定义：

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法，其也是一种特殊的插入排序，即将简单的插入排序进行改进后的一个更加高效的版本，也称 缩小增量排序

二、希尔排序原理

希尔排序的思路是，它通过将待排序的数组分割成多个子序列来进行排序。然后逐步缩小子序列的规模，最终进行一次插入排序，从而实现将整个数组排序的目的，当被排序的对象越接近有序时，插入排序的效率越高。希尔排序利用这一特点，通过将数组变得接近有序，从而提高插入排序的效率。

三、希尔排序原理图

gap值的计算公式：gap=n/3+1;

1.gap为3：

三组分别进行排序，将较小值换到左边。

是不是看起来就有序多了。继续缩小gap的值。

2.gap为2：

第一组：1，8，7

第二组：4，5，9

对两组进行排序：

看起来更加有序了。继续缩小gap的值。

3.gap为1：

当gap=1时，就相当于插入排序；

排序后：就是一个有序数组了。

插入排序

四、细节剖析

我们分析一下gap=2时的具体排序过程：

注：图中的 tmp>end 指的是 a[tmp] 和 a[end]

第1步：i=0; a[tmp] > a[end]不做交换

i++；

第2步：i=1; a[tmp] > a[end]不做交换

i++；

第3步：i=2; a[tmp] < a[end]交换

在这里就会有一些变化了，end在比较交换完后会执行语句 end -= gap ; 所以，end会继续向前移动gap个位置，再次进行比较交换。从而看起来像是0，2，4位置为一组。

第3步：</fonti=2; a[tmp] > a[end] 不交换

i++；

第5步：i=3; a[tmp] > a[end]不交换

第6步：i=3; a[tmp] > a[end]不交换

停止

i++；这里i的值为4，不满足执行条件 n - gap；退到外层循环，gap的值缩小为1；

五、代码展示：

//希尔排序
//从下标0开始，从0+gap步开始，进行插入排序，
//每次选择一个使用遍历向前寻找是否有比他小的记下位置，最后交换
void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap > 1)
  {
    gap = gap / 3 + 1;
    for (int i = 0; i < n - gap; i++)
    {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0)
      {
        //不符合就向后移动，已经保存到tmp中，不用担心被覆盖
        if (tmp < a[end])
        {
          a[end+gap] = a[end];
          end -=gap;
        }
        else
        {
          break;
        }
      }
      a[end + gap] = tmp;
    }
  }
}

六、测试结果

七、 时间复杂度