排序—希尔排序

思想

希尔排序是一种插入排序，简单插入排序的思想是每次将一个数插入有序序列中，这意味着每个待排序元素都要和有序序列进行比较，即时间复杂度度为$O(n^2)$。希尔排序通过设定一个步长$gap$，将待排序序列分组，每一次进行组内排序，通过缩小步长到1，最后执行一次简单插入排序，因此也称为缩小增量排序。

步骤，可以查看网上一些大佬通过图解的方式讲解的排序过程，可参考资料1

• step1 设定gap初始值为待排序序列长度的一半$gap = length / 2$，且后续$gap = gap/2$。
• step2 对以$gap$分组的序列进行插入排序。

动图展示（来源资料2）

代码实现

import java.util.Arrays;

public class ShellSortDemo {

    public static void main(String[] args) {
        int[] arr = {3,-1, 3, 45, 98, 0, 2, 1, 34, 56, 0, -2, -89,2};
        System.out.println(Arrays.toString(shellSort(arr)));
    }

    /**
     * 希尔排序(升序)
     * @param arr 待排序数组
     */
    public static int[] shellSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr;
        }
        for (int gap = arr.length / 2; gap > 0; gap /= 2) { // 控制希尔增量
            for (int i= gap; i < arr.length; i++) { // 按照希尔增量进行分组
                for (int j = i - gap; j >= 0; j -= gap) { // 对每个分组进行插入排序
                    // 每次向前探索gap个距离，如果gap=1，则每次比较前一个，即简单插入排序。
                    if (arr[j] > arr[j + gap]) {
                        swap(arr, j, j + gap);
                    }
                }
            }
        }
        return arr;
    }

    /**
     * 交换数组中两个元素
     */
    public static void swap(int[] arr,int i,int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

算法分析

时间复杂度：$O(nlog_2n)$
空间复杂度： $O(1)$
稳定性：不稳定