Shell Sort

Hill sort related content .

To pay off the debt , It took so long , Finally .

Hill's idea of sorting ：https://lixj.fun/upload/2021/07/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F-3d0d7c36d19e49cdbc93487df55a28d3.mp4

Divide an array into several (h) A group ( General array length length/2), Then insert and sort each group separately . The number of arrays divided in each round is gradually reduced ,h/2->h/4->h/8, And sort it out , Keep order . When h=1 when , Then the array sorting is completed .

Algorithm complexity ：O(nlog2n)

Algorithm space complexity ：O(1)

Algorithm stability ： Stable

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));
    }
}

Copy

Copyright: use Creative Commons signature 4.0 International license agreement to license Links:https://lixj.fun/archives/ Shell Sort