📑前言
什么是希尔排序？希尔排序是如何实现的？它的思想和由来又是什么？
本文将从多方面，精细的带你了解希尔排序，让你彻底掌握它！
🌤️希尔排序
☁️希尔排序的由来
希尔排序（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。
☁️希尔排序特性总结
-
希尔排序是对直接插入排序的优化。
-
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
-
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在有些书中给出的
-
希尔排序的时间复杂度都不固定：
🌤️全篇总结
经过对希尔排序的由来，思想以及希尔排序是如何实现的，并且对希尔的特性进行了总结。文章来源：https://www.toymoban.com/news/detail-714694.html
☁️ 好了，由于篇幅有限,本章专对希尔排序进行了详细的讲解，后序会出更多的排序算法哦！
看到这里了还不给博主留个：👍 点赞🌟收藏 ⭐️ 关注！
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。
文章来源地址https://www.toymoban.com/news/detail-714694.html
到了这里，关于【排序算法】希尔排序！(保姆级教学)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
