希尔排序

算法 评论

希尔排序

算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列个数k，对序列进行k 趟排序；
  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

images

image

image-20191120141958866

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//希尔排序  //var Java10新类型 让编译器自己推断类型
    public void shellSort(int[] a) {
        for (var gap = a.length / 2; gap > 0; gap = gap / 2) {
            for (var i = gap; i<a.length; i++) {
                var j = i;
                var current = a[i];
                while (j - gap >= 0 && current < a[j-gap]) {
                    a[j] = a[j - gap];
                    j = j - gap;
                }
                a[j] = current;
            }
        }
    }

总结

根据间隔分组，分组后排序，减小分组间隔
分组后使用插入排序

xyongs初涉江湖

任重道远，砥砺前行