希尔排序

Li_XiaoJin

发布于 2022-06-10 21:54:28

1850

发布于 2022-06-10 21:54:28

文章被收录于专栏：Lixj's Blog

希尔排序相关内容。
来还债了，拖了这么久，终于更了。

希尔排序的思路：https://lixj.fun/upload/2021/07/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F-3d0d7c36d19e49cdbc93487df55a28d3.mp4

把数组分割成若干(h)个小组(一般数组长度length/2)，然后对每一个小组分别进行插入排序。每一轮分割的数组的个数逐步缩小，h/2->h/4->h/8，并且进行排序，保证有序。当h=1时，则数组排序完成。

算法复杂度：O(nlog2n)

算法空间复杂度：O(1)

算法稳定性：稳定

public class ShellSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        int length = arr.length;
        int temp;
        
        int gap = length / 2;
        while (gap > 0) {
            for (int i = gap; i < length; i++) {
                temp = arr[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && arr[preIndex] > temp) {
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                arr[preIndex + gap] = temp;
            }
            gap /= 2;
        }
    }

    public static void main(String[] args){
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}