【数据结构与算法】希尔排序（直接插入排序）

大家好，我是小卡皮巴拉

文章目录

目录

引言

一.直接插入排序的基本思想

二. 直接插入排序算法解析

详细版本的算法思想解析

算法思想提炼

实现代码

画图刨析

三. 直接插入排序的特性

复杂度分析

稳定性分析

四. 希尔排序的基本思想

五. 希尔排序算法解析

详细版本的算法思想解析

算法思想提炼

实现代码

画图刨析

六. 希尔排序的特性

复杂度分析

稳定性分析

兄弟们共勉 ！！！ 

---

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

引言

在计算机科学的浩瀚星空中，排序算法如同璀璨星辰，各自闪耀着独特的光芒。其中，直接插入排序（简称插入排序）以其直观易懂、实现简便的特点，成为了初学者的首选之一，也是理解复杂排序算法的重要基石。

直接插入排序，顾名思义，是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这一过程仿佛我们在整理书架上的书籍，每次拿起一本新书，从已排列好的书堆中寻找合适的空位，小心翼翼地放置进去，直到所有书籍都井然有序。

本文旨在深入探讨直接插入排序及其进阶版本希尔排序的核心思想、实现步骤以及时间空间复杂度分析，帮助读者掌握这一基础而强大的排序工具。

下面，让我们开始学习！

一.直接插入排序的基本思想

直接插如入排序是⼀种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到⼀个已经排好序的有序序列中，直到所有的记录插入完为止，得到⼀个新的有序序列。

实际中我们玩扑克牌时，就用了插入排序的思想

下面我们给出直接插入排序的动图，帮助大家更好的理解

二. 直接插入排序算法解析

详细版本的算法思想解析

1. 初始化：
   • 从数组的第二个元素开始（因为第一个元素默认是有序的），对剩余的每一个元素进行排序。
2. 取待排序元素：
   • 对于当前索引 i，取出 arr[i+1] 作为待排序的元素 tmp，并记录 i 作为已排序数组的最后一个元素的索引 end。
3. 扫描已排序部分：
   • 从 end 向左扫描已排序的数组部分（即从 arr[end] 到 arr[0]）。
   • 在扫描过程中，如果已排序部分的元素 arr[end] 大于 tmp，则将该元素向右移动一个位置（即 arr[end+1] = arr[end]），为 tmp 腾出插入空间。
   • 如果 arr[end] 不大于 tmp，则停止扫描，因为 tmp 应该插入到这个元素之后（或与之相等的位置）。
4. 插入元素：
   • 将 tmp 插入到扫描停止时的位置（即 arr[end+1]）。
5. 重复：
   • 对数组的每一个元素（从第二个元素开始）重复步骤 2 到步骤 4，直到整个数组排序完成。 

算法思想提炼

直接插入排序从数组第二个元素开始，逐个取出作为待排序元素tmp。对于每个tmp，从已排序部分（初始为第一个元素）的末尾向前扫描，若遇到比tmp大的元素则后移，为tmp腾出插入位置。找到不大于tmp的元素或扫描至开头后，将tmp插入。重复此过程直至数组完全排序。

就像整理扑克牌，每次摸一张新牌，找到并插入到已排序牌堆中的正确位置。

实现代码

//直接插入排序
void InsertSort(int* arr, int n)
{// 从第二个元素开始，因为第一个元素默认是有序的  for (int i = 0; i < n - 1; i++){// end 变量表示当前已经排好序的数组的最后一个元素的索引  // tmp 变量保存当前要插入的元素的值  int end = i;int tmp = arr[end + 1];// 向前扫描已经排好序的数组，找到tmp应该插入的位置  while (end >= 0){// 如果已经排好序的数组中的元素比tmp大，  // 就把这个元素向后移动一个位置，为tmp腾出空间  if (arr[end] > tmp){arr[end + 1] = arr[end];end--; // 继续向前扫描  }else {// 如果已经排好序的数组中的元素不大于tmp，  // 那么tmp就应该插入到这个元素之后（或与之相等的位置），  // 循环结束  break;}}// 把tmp插入到正确的位置  arr[end + 1] = tmp;}
}

下面我们给出一个数组int arr[] = {4,6,7,2}

画图刨析

三. 直接插入排序的特性

复杂度分析

• 时间复杂度：
  • 最优情况（数组已排序）：O(n)
  • 最坏情况（数组逆序）：O(n^2)
  • 平均情况：O(n^2)
• 空间复杂度：O(1)，因为直接插入排序是原地排序算法，不需要额外的存储空间。

稳定性分析

在排序算法中，稳定性指的是：如果待排序的记录序列中存在多个具有相同关键字的记录，那么经过排序后，这些具有相同关键字的记录的相对次序应该保持不变。换句话说，如果两个元素在排序前的相对位置是固定的（即一个元素在另一个元素之前），且它们的值相等，那么在排序后，这两个元素的相对位置也应该保持不变。

在直接插入排序中，如果两个元素相等，插入操作不会改变它们的相对位置。也就是说，如果 A 在 B 之前，且 A 和 B 的键值相等，那么在排序过程中，A 会被插入到它原本应该在 B 之前的位置，从而保持了它们的相对顺序。因此，直接插入排序是稳定的

四. 希尔排序的基本思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数（通常是gap=n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每一组内的记录进行排序，然后gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。

通过把数组不断拆分成多个直接插入排序，经过多次这样的预排序，保证了大数据在前，小数据在后，当gap = 1时，再进行最终的直接插入排序。

它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。

五. 希尔排序算法解析

详细版本的算法思想解析

1. 初始化增量：将增量gap初始化为数组的长度n。

2. 缩小增量：使用Hibbard增量序列（或其他有效的增量序列），在每次循环中将gap缩小为gap / 3 + 1，直到gap变为1。这个过程形成了多个逐渐减小的子序列。

3. 分组插入排序：对于每个gap值，将数组分成若干个子序列，每个子序列由相隔gap个位置的元素组成。然后对每个子序列进行插入排序，但这里的插入排序与传统的插入排序略有不同，因为它是基于gap间隔进行的。

4. 元素移动与插入：在插入排序的过程中，如果当前元素（tmp）小于它前面的元素（在同一个子序列中，相隔gap个位置），则将前面的元素向后移动gap个位置，为当前元素腾出插入空间。这个过程一直进行，直到找到当前元素应该插入的位置。

5. 重复步骤：对每个gap值，重复步骤3和步骤4，直到gap变为1。当gap为1时，整个数组就变成了一个子序列，此时进行一次最终的插入排序，完成整个排序过程。

算法思想提炼

希尔排序的核心算法思想很简单：它先不急着对整个数组进行排序，而是先将数组“拆分”成若干个小子数组（这些子数组是通过每隔一定距离——我们称之为“增量gap”——选取元素形成的），然后对每个小子数组分别进行插入排序。随着排序的进行，这个“增量gap”会逐渐变小，直到最后变成1，此时整个数组就被当作一个大的子数组来进行最后一次插入排序。

换句话说，希尔排序就是先通过大间隔的插入排序让数组元素部分有序，然后逐渐缩小间隔，让元素越来越接近它们最终的位置，直到最后通过一次完整的插入排序将整个数组完全排序好。这种方法的好处是，它可以在较短的时间内让数组变得大致有序，从而减少了后续排序的工作量，提高了排序效率。

实现代码

//希尔排序
void ShellSort(int* arr, int n)
{// 初始化增量gap为数组长度nint gap = n;// 当gap大于1时，继续执行循环while (gap > 1){// 使用Hibbard增量序列：gap = gap / 3 + 1，逐步缩小增量gap = gap / 3 + 1;// 对每个子序列进行插入排序for (int i = 0; i < n - gap; i++){// end记录当前考虑的元素在子序列中的位置int end = i;// tmp记录要插入的元素int tmp = arr[end + gap];// 在子序列中从后向前扫描，为tmp找到正确的插入位置while (end >= 0 && arr[end] > tmp){// 将大于tmp的元素向后移动gap个位置arr[end + gap] = arr[end];// 向前移动end，继续比较前一个元素end -= gap;}// 将tmp插入到正确的位置arr[end + gap] = tmp;}}
}

画图刨析

六. 希尔排序的特性

复杂度分析

1. 时间复杂度：

   • 最坏情况：希尔排序的时间复杂度依赖于所选的增量序列（gap sequence）。常见的增量序列有希尔增量（初始为n/2，每次减半）、Hibbard增量（形如1, 3, 7, ...）、Sedgewick增量等。对于不同的增量序列，最坏情况的时间复杂度会有所不同，但通常在O(n(3/2))之间。

   • 平均情况：尽管最坏情况的时间复杂度可能较高，但希尔排序在实际应用中通常表现较好，其平均时间复杂度接近于O(n^(3/2))或更优，具体取决于增量序列的选择。

   • 最好情况：在最佳情况下，希尔排序的时间复杂度可以达到O(n log n)，但这依赖于特定的输入数据和增量序列。

2. 空间复杂度：

   • 希尔排序是原地排序算法（in-place sorting algorithm），它只需要O(1)的额外空间。

稳定性分析

• 稳定性：希尔排序不是稳定的排序算法。稳定排序算法是指如果两个元素相等，它们在排序后的相对顺序与排序前相同。然而，希尔排序在比较和交换元素时可能会破坏这种相对顺序。例如，在较大的间隔上进行插入排序时，原本相邻且相等的元素可能会被分开，并在后续步骤中重新排序，导致它们的相对顺序发生变化。

总结

• 时间复杂度：通常在O(n(3/2))之间，取决于增量序列的选择。

• 空间复杂度：O(1)，因为它是原地排序算法。

• 稳定性：希尔排序不是稳定的排序算法。

兄弟们共勉 ！！！ 

码字不易，求个三连

抱拳了兄弟们！