十大经典排序(八)--希尔排序
希尔排序思路：
希尔排序也是一种插入排序（对插入排序不熟的同学可以看）
由于插入排序不管数组分布如何，在排序过程中总是一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次
基于这种情况，希尔排序采用跳跃分组的方式，现将原数组按某个跨度分组，然后对每个分组进行插入排序，这样的话后面的元素就能直接交换插入到前面去，之后再缩小跨度、分组、插入排序直至跨度为1，完成整个排序
题外话：希尔与插入排序的不同之处在于，它会优先比较距离排序较远的元素，这样可以大大减少远处数据插入到前面所需要的移动次数
为什么叫希尔排序？
因为这个方法是一个叫希尔的大哥提出的
算法步骤：
设定一个原始跨度k，将原数组分组，第一组元素下标为[0, 0+k, 0 + 2k...]，第二组元素下标为[1, 1+k, 1+2k...]，依次类推
对每组元素进行插入排序
缩小跨度k，重复1、2操作，直至k = 1，数组变成一个组，再对这个组进行排序即可
这里找来一张图方便大家理解：里面的增量就是上面描述的跨度
代码：
1public static void sort(int[] arr) {
2 //设置跨度gap，每次循环缩小gap
3 for (int gap = arr.length / 2; gap > 0; gap /= 2) {
4 //从第gap个元素，逐个对其所在组进行直接插入排序操作
5 for (int i = gap; i < arr.length; i++) {
6 int j = i;
7 while (j - gap >= 0 && arr[j] < arr[j - gap]) {
8 //插入排序采用交换法
9 swap(arr, j, j - gap);
10 j -= gap;
11 }
12 }
13 }
14}
15
16//这里交换数组元素采用类似异或法的思想
17// 有兴趣同学可以玩玩异或法实现
18private static void swap(int arr[], int i, int j) {
19 arr[i] = arr[i] + arr[j];
20 arr[j] = arr[i] - arr[j];
21 arr[i] = arr[i] - arr[j];
22}
时间复杂度：O(n1.3~n2)
空间复杂度：O(1)
以上仅是个人思路解法，觉得还不错欢迎点赞关注分享
往期精彩推荐