This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

One, foreword

Hill sort: is a sort algorithm proposed by Hill, it is an improved version of insertion sort.

  • Hill sort divides an array into subsequences for insertion sort by introducing a step gap, which allows an element to jump a big step toward its final position.

  • The step size decreases after each round of sorting, and finally decreases to 1, which becomes simple insertion sort.

  • At this point, the array is basically in order, and only a few more comparisons and moves are required to complete the final sort.

Ju Li, the GIF is as follows:

How did you come up with this method?

Remember the reverse order, right?

Remember? The following points also have a list, remember to review oh.

According to the reverse pair, to improve the efficiency of the algorithm, we must:

  1. It cancels out more than one inversion pair at a time

  2. Swap two elements far apart at a time

Therefore, Hill sort takes the second way to improve the efficiency of the algorithm ———— increase step size.


Length /2, length/4, length/8…





Two, knowledge points

Knowledge points, as follows:

  1. Time complexity
  2. The reverse of
  3. Implementation: Hill sort is usedgapInsertion sort of a sequence

PS: Intern interview, will encounter


(1) Time complexity

  • Best case: Time complexity O(N * log^2N)

  • Worst case: time complexity O(N ^ 2), delta elements are not mutual, small deltas may not work at all

  • Stability: unstable.

    For example, the original array {4, 1, 4}

    Unstable: The second 4 is ranked before the first 4 in the sorting process.

General sorting diagram, as shown in figure:


(2)

If arr[I] > A [j] for subscript I < j, (I, j) is an inversion pair.

For example, sequence{34, 8, 64, 51, 32, 21}How many inversions are there?

Nine: (34, 8), (34, 32), (34, 21), (64, 51), (64, 32), (64, 21), (51, 32), (51, 21), (32, 21)Copy the code

Obtained theorem:

  • Theorem: ArbitraryNA sequence of different elements has an average ofN(N-1)/4A reverse order to
  • Theorem: The average time complexity of any algorithm that sorts only by swapping two adjacent elements isO(N^2)

So what’s the use of reverse pairs?

  1. It’s the number of swaps you have to make.

  2. It provides the basis for improving the efficiency of the algorithm

In order to improve the efficiency of the algorithm, it is necessary to:

  1. It cancels out more than one inversion pair at a time

  2. Swap two elements far apart at a time


(3) implementation

Sort from front to back as follows:

public class SelectSort {

    // Hill sort
    // Time: O(n^2), Space: O(1)
    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        
        // Each half-fold >> 1 represents: move 1 bit to the right, i.e. /2
        for (int gap = arr.length >> 1; gap > 0; gap >>= 1) {
            for (int i = gap; i < arr.length; ++i) {
                int cur = arr[i];
                int j = i - gap;
                while (j >= 0&& arr[j] > cur) { arr[j+gap] = arr[j]; j -= gap; } arr[j+gap] = cur; }}}// Compare insertion sort as follows:
    // Hill sort is an insertion sort using gap sequences
    // Time: O(n^2), Space: O(1)
    public void insertionSort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        for (int i = 1; i < arr.length; ++i) {
            int cur = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > cur) {
                arr[j + 1] = arr[j];
                j -= 1;
            }
            arr[j + 1] = cur; }}}Copy the code