希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。
希尔排序代码如下：
1 public static void shellSort(int[] arr) { 2 int num = arr.length >> 1;//Donald Shell最初建议步长选择为(n/2)并且对步长取半直到步长达到1。最坏的时间复杂度为O(n²)。 3 int i, j; 4 int tmp; 5 while (num >= 1) { 6 for (i = num; i < arr.length; i++) { 7 tmp = arr[i]; 8 j = i - num; 9 while (j >= 0 && arr[j] > tmp) { 10 arr[j + num] = arr[j]; 11 j = j - num; 12 } 13 arr[j + num] = tmp; 14 } 15 num = num >> 1; 16 } 17 }
希尔排序空间复杂度为O(1)，最好时间复杂度为O(n)，最坏O(n²)，平均O(n^1.3)。
测试代码：
1 public static void main(String[] args) { 2 int[] arr = {1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22}; 3 4 shellSort(arr); 5 6 for (int i : arr) { 7 System.out.print(i + " "); 8 } 9 }
原文：https://www.cnblogs.com/magic-sea/p/11374033.html