Implementation of Hill sorting algorithm

Hill sorting is an improved version of direct insertion sorting, and it is also a kind of insertion sorting. The improvement is to set a step size for each traversal and then perform direct insertion sorting. After completing a traversal, the step size is halved until the step size is less than or equal to 1.

(Recommended tutorial: java introductory tutorial)

Since each move will move a step distance, direct insertion sort only moves one step each time, so Hill sorting is more efficient than direct insertion sorting.

(Learning video recommendation: java course)

Algorithm implementation:

  public static void shellSort(int[] array) {
        int step = array.length;
        while (true) {
            step /= 2;
            for (int i = 0; i < step; i++) {
                for (int j = i + step; j < array.length; j += step) {
                    int tmp = array[j];
                    int k = j;
                    while (k >=step && array[k - step] > tmp) {//将大于tmp的数往后移
                        array[k] = array[k - step];
                        k-=step;
                    }
                    array[k] = tmp;//插入
                }
            }
            if (step <= 1)
                return;
        }
    }

The above is the detailed content of Implementation of Hill sorting algorithm. For more information, please follow other related articles on the PHP Chinese website!