Shell Sort 希尔排序
希尔排序（Shell Sort）是一种改进的插入排序算法，其思路如下：首先，选择一个增量序列（通常为n/2，n为数组长度）来划分数组。按照增量序列的步长，对子序列进行插入排序。逐渐缩小增量序列的步长，重复上述步骤，直到增量序列为1，即对整个数组进行最后一次插入排序。
以下是希尔排序的具体步骤：
- 初始化增量序列，通常为数组长度的一半，并将其逐渐缩小为1。
- 对于每个增量，从增量位置开始，对子序列进行插入排序。
- 重复步骤2，直到增量为1，即对整个数组进行最后一次插入排序。
以下是希尔排序的示例代码：
public class Sort { public static void shellSort(int[] arr) { int n = arr.length; int gap = n / 2; while (gap > 0) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i; while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } gap /= 2; } } public static void main(String[] args) { int[] array = {5, 2, 8, 12, 1, 6}; shellSort(array); System.out.println("排序结果："); for (int num : array) { System.out.print(num + " "); } } }
希尔排序的时间复杂度取决于增量序列的选择，最坏情况下为O(n^2)，最好情况下可达到O(n log n)。
希尔排序的空间复杂度为O(1)，因为算法只需要常数级的额外空间来存储临时变量和增量值。
希尔排序相较于简单插入排序，在大规模数据集上表现更优，但并不如快速排序或归并排序等高级排序算法效率高。
