带你图解排序算法之——希尔排序算法（三）
最新回答
小格调
2026-07-29 19:43:15
希尔排序是一种基于插入排序的高效改进算法，通过分组插入排序逐步缩小增量，最终实现整体有序。
算法思想
分组插入排序：将待排序序列按增量分割为若干子序列，对每个子序列进行插入排序。随着增量减小，子序列逐渐变长，最终增量为1时完成整体排序。
增量选择：初始增量通常取数组长度的一半，后续增量按increment = increment / 2递减，直至增量为1。
排序过程
初始状态：以数组[3,1,5,2,4]为例，初始增量为5/2=2（向下取整），分为两组：[3,5,4]和[1,2]。
分组排序：
对第一组[3,5,4]进行插入排序：比较3和5，顺序正确；比较5和4，交换后得到[3,4,5]。
对第二组[1,2]进行插入排序：顺序正确，无需调整。
缩小增量：增量变为2/2=1，此时对整个数组进行插入排序：
比较3和1，交换得到[1,3,4,5,2]；
比较3和2，交换得到[1,2,3,4,5]，排序完成。
代码实现
#include <iostream>using namespace std;void ShellSort(int arr[], int len) { int temp, increment = len; do { increment = increment / 2; for (int i = increment; i < len; i++) { temp = arr[i]; int j = i - increment; while (j >= 0 && arr[j] > temp) { arr[j + increment] = arr[j]; j -= increment; } arr[j + increment] = temp; } } while (increment > 1);}void printArray(int arr[], int len) { for (int i = 0; i < len; i++) cout << arr[i] << " "; cout << endl;}int main() { int arr[] = {3, 1, 5, 2, 4}; int len = sizeof(arr) / sizeof(arr[0]); ShellSort(arr, len); printArray(arr, len); // 输出：1 2 3 4 5 return 0;}关键点
非稳定排序：相同元素可能因分组交换顺序。
时间复杂度：取决于增量序列，最优可达O(n log n)，最坏为O(n2)。
空间复杂度：O(1)，原地排序。
示例演示
初始数组：[3,1,5,2,4]
增量2排序后：[1,2,3,4,5]
增量1排序后：确认整体有序。
通过逐步缩小增量并分组插入，希尔排序高效地减少了数据移动次数，适用于中等规模数据排序。
热门标签
