希尔排序
入门理解"间隔排序"如何将 O(n²) 优化到接近 O(n log n)。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void shellSort(int arr[], int n) {
2 for (int gap = n / 2; gap > 0; gap /= 2) {
3 for (int i = gap; i < n; i++) {
4 int temp = arr[i];
5 int j = i;
6 while (j >= gap && arr[j - gap] > temp) {
7 arr[j] = arr[j - gap];
8 j -= gap;
9 }
10 arr[j] = temp;
11 }
12 }
13}
复杂度分析
时间 O(n log²n)
空间 O(1)
最优 O(n log n)
最坏 O(n²)
算法讲解
希尔排序先按较大间隔分组进行插入排序，然后逐步缩小间隔。
随着间隔减小，数组越来越接近有序，插入排序的效率也越高。
间隔序列的选择影响性能，常用 Knuth 序列或 Sedgewick 序列。
时间复杂度取决于间隔序列，最优可达 O(n log²n)。