Introduction to the

Shell’s Sort, also known as “Diminishing Increment Sort”, is a more efficient and improved version of direct insert Sort. Hill sort is an unstable sort algorithm. The method is named after D.L.Shell, who proposed it in 1959. Hill sort is to group the records by a certain increment of the index and sort each group by direct insertion sort algorithm. As the increments decrease, each group contains more and more keywords, and when the increments decrease to 1, the entire file is exactly grouped and the algorithm terminates.

For those of you who haven't studied insertion sort, I suggest you study insertion sort first in my sorting algorithm series and then hill sort, which is a lot easier.Copy the code

Time complexity

O(nlog2n)

Thought analysis

Order: From smallest to largest

Code implementation

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {9.2.5.3.1};
        //shellSort(arr);
        //shellSortMoveFor(arr);
        shellSortMoveWhile(arr);
        System.out.println(Arrays.toString(arr));
    }

    // The exchange method is inefficient
    public static void shellSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int temp;
        // Shrink increments each time
        for (int gap = arr.length / 2; gap >= 1; gap /= 2) {
            // The two loops are insert sort, but the insert loop is 1 step and the increment is reduced

            // I =gap because the insertion sort algorithm compares the previous element from the last one each time
            // The first time there is an element in the ordered table the first element in the unordered table is compared with the element in the ordered table
            // If gap = 2, then the index of the elements in the ordered table is 0
            for (int i = gap; i < arr.length; i++) {
                for (int k = i - gap; k >= 0; k -= gap) {
                    // Compare the current element with the elements in the sorted table
                    if (arr[k] > arr[k + gap]) {
                        temp = arr[k];
                        arr[k] = arr[k + gap];
                        arr[k + gap] = temp;
                    }
                }
            }
        }
    }

    // The move method for mode is efficient
    public static void shellSortMoveFor(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int curVal;
        int insertIndex;
        for (int gap = arr.length / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                curVal = arr[i];
                for (insertIndex = i - gap; insertIndex >= 0; insertIndex -= gap) {
                    if (curVal < arr[insertIndex]) {
                        arr[insertIndex + gap] = arr[insertIndex];
                    } else {
                        break; }}if(insertIndex + gap ! = i) { arr[insertIndex + gap] = curVal; }}}}// Move while is efficient
    public static void shellSortMoveWhile(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int curVal;
        int insertIndex;
        for (int gap = arr.length / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                curVal = arr[i];
                insertIndex = i - gap;
                while (insertIndex >= 0 && curVal < arr[insertIndex]) {
                    arr[insertIndex + gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                if(insertIndex + gap ! = i) { arr[insertIndex + gap] = curVal; } } } } }Copy the code

Run the output

[1, 2, 3, 5, 9]

conclusion

In fact, it is optimized on the basis of insertion sort. Avoid too many small elements in the back row by constantly moving the smaller elements to the front row by step size. It takes multiple cycles to find the right place.

Hill sort is good for large numbers of data and is very fast when large and smaller numbers are at the back or end of the array.