❤查看排序算法动态演示❤查看排序算法动态演示❤查看排序算法动态演示
希尔排序 （Shell Sort）
希尔排序 也称做递减增量排序算法，1959年Shell发明，是插入排序的一种高速而稳定的改进版本
基本思想
希尔排序是先将整个待排序的记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，在对全体记录进行依次直接排序
例如上图中的待排序数组：[49,38,65,97,76,13,27,49,55,4]
将数组按5个间隔为一组划分成5组子序列,每个子序列进行插入排序后，各个子序列就变成了有序的了（整体不一定有序）
将上一步得到的数组按2个间隔为一组划分成3组子序列，各个子序列进行插入排序
将上一步得到的数组按正常插入排序，此时序列基本有序，所以效率较高
上面提到的间隔可以称作增量, 一般初始增量取数组的一半长度, 每轮排序后，增量减半，直至增量为1(存在多种增量序列)
算法描述
选择一个增量序列t1，t2，…，tk，其中t1>t2，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
如下图，其中H表示增量
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 import java.util.Arrays;public class ShellSort public static void main (String[] args) int [] arr = {49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 , 55 , 4 }; System.out.println("排序前:" +Arrays.toString(arr)); int [] a = Arrays.copyOf(arr,arr.length); shellsort1(a); int [] b = Arrays.copyOf(arr,arr.length); shellsort2(arr); } private static void shellsort2 (int [] arr) int gap = 1 , i, j, len = arr.length; int temp; while (gap < len / 3 ){ gap = gap * 3 + 1 ; } for (; gap > 0 ; gap /= 3 ) { for (i = gap; i < len; i++) { temp = arr[i]; for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap){ arr[j + gap] = arr[j]; } arr[j + gap] = temp; } } System.out.println("排序后:" +Arrays.toString(arr)); } private static void shellsort1 (int [] arr) for (int g = arr.length / 2 ; g > 0 ; g /= 2 ) { for (int i = g; i < arr.length; i++) { int inserted = arr[i]; int j; for (j = i - g; j >= 0 && inserted < arr[j]; j -= g) { arr[j + g] = arr[j]; } arr[j + g] = inserted; } } System.out.println("排序后:" +Arrays.toString(arr)); } }
复杂度
希尔排序的复杂度与增量有关，不同的增量会产生不同的复杂度
像我们思路分析中的数组对半取值为增量5，直至为1，其实并不是最优增量序列。
平均时间复杂度
最好情况
最坏情况
空间复杂度
O(n^1.25)
O(n)
O(n²)
O(1)
适用场景
希尔排序时直接插入排序的优化版，解决了直接插入排序在面对大量数据时的效率低问题。
希尔排序适用于大规模无序数组的排序，且相对于直接插入排序数组越大优势越大
