三河燕郊最新消息_泰安网络诈骗案件_杭州seo营销公司_百度收录技术

✨博客主页
何曾参静谧的博客
📌文章专栏
「C/C++」C/C++程序设计
📚全部专栏
「VS」Visual Studio	「C/C++」C/C++程序设计	「UG/NX」BlockUI集合
「Win」Windows程序设计	「DSA」数据结构与算法	「UG/NX」NX二次开发
「QT」QT5程序设计	「File」数据文件格式	「PK」Parasolid函数说明

---

希尔排序（Shell Sort）详解

一、引言

希尔排序，又称缩小增量排序（Diminishing Increment Sort），是直接插入排序的一种更高效的改进版本。希尔排序的基本思想是将数组元素按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个数组恰好被分成一组，算法便终止。

二、算法步骤

1. 选择增量序列：选择一个递减的增量序列gap，通常从数组长度的一半开始，逐步减半，直到gap为1。
2. 分组排序：对于每个gap值，将数组分为gap个组，每组包含gap个元素（最后一组可能不足gap个）。对每个组内的元素进行直接插入排序。
3. 重复步骤：减小gap的值，重复分组排序的过程，直到gap为1，此时整个数组被当作一个组进行排序。
4. 完成排序：当gap为1时，整个数组已经基本有序，再进行一次直接插入排序即可得到完全有序的数组。
   
   动图来源：博主：双鱼211《六大排序》

三、时间复杂度分析

• 最坏情况：O(n²)，这取决于增量序列的选择。如果增量序列选择不当，希尔排序的性能可能接近直接插入排序。
• 最好情况：O(n log² n)，这是使用某些高效增量序列（如Hibbard增量序列、Sedgewick增量序列等）时可以达到的时间复杂度。
• 空间复杂度：O(1)，希尔排序是原地排序算法，不需要额外的存储空间。

四、C++实现

下面是一个用C++实现希尔排序的完整代码：

#include <iostream>
#include <vector>
#include <cmath> // 用于计算平方根// 希尔排序函数
void shellSort(std::vector<int>& arr) {int n = arr.size();// 使用Hibbard增量序列：1, 3, 7, ..., 2^k - 1// 或者其他有效的增量序列，如Sedgewick增量序列for (int gap = static_cast<int>(std::floor(n / 2.0)); gap > 0; gap /= 2) {// 对每个gap分组进行插入排序for (int i = gap; i < n; ++i) {int temp = arr[i];int j;// 对当前分组进行插入排序for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}// 打印数组函数
void printArray(const std::vector<int>& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;
}int main() {std::vector<int> arr = {12, 34, 54, 2, 3};std::cout << "排序前的数组: ";printArray(arr);shellSort(arr);std::cout << "排序后的数组: ";printArray(arr);return 0;
}

五、代码解析

1. 函数shellSort：

   • 接受一个整数向量arr作为参数。
   • 使用Hibbard增量序列（或其他有效的增量序列）来确定gap的初始值，并逐步减半直到gap为0（但循环在gap为1时结束，因为当gap为0时没有意义）。
   • 对于每个gap值，使用两层循环进行分组插入排序。外层循环控制当前要插入的元素位置i，内层循环用于在当前分组内找到插入位置，并将元素向后移动。

2. 函数printArray：

   • 接受一个整数向量arr作为参数。
   • 使用范围for循环遍历并打印数组中的每一个元素。

3. 主函数main：

   • 初始化一个待排序的数组arr。
   • 打印排序前的数组。
   • 调用shellSort函数对数组进行排序。
   • 打印排序后的数组。

六、总结

希尔排序是一种基于插入排序的改进算法，通过引入增量序列来减少数据交换和移动的次数，从而提高排序效率。虽然希尔排序的时间复杂度取决于增量序列的选择，但在实际应用中，它通常比直接插入排序要快得多，特别是对于大规模数据集。然而，希尔排序的性能仍然不如一些更高级的排序算法（如快速排序、归并排序等），因此在某些特定场景下可能需要权衡选择。

---