希尔排序

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

算法步骤

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

动图演示

Sorting_shellsort_anim.gif

复杂度

时间复杂度 = O(n*1.3) 空间复杂度 = O(1)

代码实现

public static int[] insertsort(int[] arr) {

        int[] nums = Arrays.copyOf(arr,arr.length);

        for (int i = 1; i < nums.length; i++) {

            for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--) {

                RandomUtils.swap(nums,j,j - 1);
            }

        }

        return nums;
 }