Shell Sort 希尔排序

希尔排序（Shell Sort）是一种改进的插入排序算法，其思路如下：首先，选择一个增量序列（通常为n/2，n为数组长度）来划分数组。按照增量序列的步长，对子序列进行插入排序。逐渐缩小增量序列的步长，重复上述步骤，直到增量序列为1，即对整个数组进行最后一次插入排序。

以下是希尔排序的具体步骤：

1. 初始化增量序列，通常为数组长度的一半，并将其逐渐缩小为1。
2. 对于每个增量，从增量位置开始，对子序列进行插入排序。
3. 重复步骤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)，因为算法只需要常数级的额外空间来存储临时变量和增量值。

希尔排序相较于简单插入排序，在大规模数据集上表现更优，但并不如快速排序或归并排序等高级排序算法效率高。