排序算法-希尔排序
希尔排序是插入排序的改进版，通过将原始数组分成多个子序列进行间隔插入排序，逐步缩小间隔直至为1，最终完成整体排序。它也被称为缩小增量排序。
希尔排序步骤
-
选择增量序列（Gap Sequence）：确定一个递减的间隔序列（如
n/2, n/4, ..., 1）。 -
分组插入排序：对每个间隔
gap，将数组分成gap个子序列，分别进行插入排序。 -
逐步缩小间隔：重复上述过程，直到
gap = 1，此时数组基本有序，最后进行一次标准插入排序。
常用的增量序列
- 希尔增量序列：
，其中n为原始数组的长度，这是最常用的序列，但却不是最好的。
-
Hibbard序列：（1, 3, 7, 15, ..., 2^k - 1） 公式：
-
Sedgewick序列：（1, 5, 19, 41, ...） 公式：
或
代码实现
package Sort;public class ShellSort {public static void main(String[] args) {int[] res = getShellSort(new int[]{4,8,6,9,2,5,3,1,7});for (int i = 0; i < res.length; i++) {System.out.print(res[i]+" ");}}public static int[] getShellSort(int[] nums){int len = nums.length;int currentNum;//按增量分组后，每个分组中//gap指用来分组的增量，会依次递减，直到gap=1，一般gap递减可使用/2来实现int gap = len / 2;while (gap > 0){// 对每个子序列进行插入排序for (int i = gap; i < len; i++) {currentNum = nums[i];//组内已被排序数据的索引int preIndex = i - gap;//在组内已被排序过数据中倒序寻找合适位置，如果当前待排序数据更小//则将比较的数据在组内后移//插入排序逻辑（间隔为 gap）while (preIndex>=0 && currentNum < nums[preIndex]){nums[preIndex + gap] = nums[preIndex];preIndex -= gap;}//循环结束，说明已经找到当前待排序数据的合适位置，进行插入。nums[preIndex + gap] = currentNum;}gap /= 2;}return nums;}
}
时间复杂度
-
最坏情况：取决于增量序列（Gap Sequence）。
-
Shell 原始序列（n/2, n/4, ..., 1）：最坏时间复杂度为 O(n²)。
-
Hibbard 序列（1, 3, 7, 15, ..., 2^k - 1）：最坏时间复杂度为 O(n^(3/2))。
-
Sedgewick 序列（1, 5, 19, 41, ...）：最坏时间复杂度为 O(n^(4/3))。
-
-
最好情况：序列已经基本有序，此时希尔排序接近 O(n log n)（取决于增量序列）。
-
平均情况：
-
Shell 原始序列：平均时间复杂度 O(n^(3/2)) ~ O(n²)。
-
优化增量序列（如 Sedgewick）：平均时间复杂度 O(n log n) ~ O(n^(4/3))。
-
空间复杂度
-
O(1)（原地排序），仅需常数级额外空间（如 currentNum变量）。