WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
算法基础简介
枚举
模拟
递归 & 分治
贪心
排序简介
选择排序
冒泡排序
插入排序
计数排序
基数排序
快速排序
归并排序
堆排序
桶排序
希尔排序
锦标赛排序
排序相关 STL
排序应用
前缀和 & 差分
二分
倍增
22 objects
本站非官方,所收集资源均来源于网络。
希尔排序 - 算法基础
本页面将简要介绍希尔排序。 ## 简介 希尔排序(英语:Shell sort),也称为缩小增量排序法,是 [插入排序](#) 的一种改进版本。希尔排序以它的发明者希尔(英语:Donald Shell)命名。 ## 工作原理 排序对不相邻的记录进行比较和移动: 1. 将待排序序列分为若干子序列(每个子序列的元素在原始数组中间距相同); 2. 对这些子序列进行插入排序; 3. 减小每个子序列中元素之间的间距,重复上述过程直至间距减少为 1。 ## 性质 ### 稳定性 希尔排序是一种不稳定的排序算法。 ### 时间复杂度 希尔排序的最优时间复杂度为 $O(n)$ 。 希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取(就是间距如何减小到 1)有关,比如「间距每次除以 3」的希尔排序的时间复杂度是 $O(n^{3/2})$ 。已知最好的最坏时间复杂度为 $O(n \log^2n)$ 。 ### 空间复杂度 希尔排序的空间复杂度为 $O(n)$ 。 ## 实现 ### C++[^ref1] ```cpp template
void shell_sort(T array[], int length) { int h = 1; while (h < length / 3) { h = 3 * h + 1; } while (h >= 1) { for (int i = h; i < length; i++) { for (int j = i; j >= h && array[j] < array[j - h]; j -= h) { std::swap(array[j], array[j - h]); } } h = h / 3; } } ``` ## 参考资料与注释 [^ref1]: [希尔排序 - 维基百科,自由的百科全书](https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F)