Writing in the front

  • Sorting classical sorting algorithm
  • Record learning

1. ShellSort

1.1 concept

Hill sort is a sort algorithm proposed by Donald Shell in 1959. Hill sort is also an insertion sort, which is a more efficient version of simple insertion sort, also known as reduced incremental sort, and was one of the first algorithms to break out of O(n2). It differs from insertion sort in that it compares distant elements first. Hill sort is also called reduced increment sort.

Hill sort is to group the records in a certain increment of the following table, and sort each group using the direct insert 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.

1.2 Algorithm Description

Let’s take a look at the basic steps of Hill sorting. Here we select the increments gap=length/2, and continue to narrow the increments by gap= gap/2. The increments can be represented by a sequence {n/2,(n/2)/2… 1}, called an incremental sequence. It is a mathematical problem to select and prove the delta sequence of Hill sort. The delta sequence we choose is more commonly used and also the delta suggested by Hill, called Hill delta, but in fact this delta sequence is not optimal. Here we do an example using Hill increments.

Firstly, the whole record sequence to be sorted is divided into several sub-sequences for direct insertion sorting. The specific algorithm is described as follows:

  • Select a delta sequence T1, T2… , where Ti >tj, tk=1;
  • Sort the sequence k times according to the number of incremental sequences k;
  • In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.

Schematic diagram

Reference article: Ten classic sorting algorithms

1.3 Code Demonstration

package com.zhuang.algorithm;

import java.util.Arrays;

/ * * *@Classname ShellSort
 * @DescriptionHill sort@Date2021/6/13 * therefore,@Created by dell
 */

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {51.46.20.18.65.97.82.30.77.50};
        shellsort(arr);
        System.out.println("The sequence after Hill sort is :");
        System.out.println(Arrays.toString(arr));//[18, 20, 30, 46, 50, 51, 65, 77, 82, 97]
    }

    public static void shellsort(int[] array) {
        int len = array.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap /= 2; }}}Copy the code

1.5 Algorithm Analysis

  • Best case: T(n) = order nlog2^n^)
  • Worst case: T(n) = order nlog2^n^)
  • Average case: T(n) = order nlog2^n^)

1.6 stability

We all know that insertion sort is a stable algorithm. Shell sorting, however, is a process of multiple inserts. In a single insert we can be sure that the order of the same elements is not moved, but in multiple inserts it is entirely possible for the same elements to be moved in different insert rounds and the stability to be broken, so Shell sorting is not a stable algorithm.

1.7 Application Scenarios

While Shell sorting is fast, it is not a good algorithm for large amounts of data. However, it is perfectly acceptable for small – and medium-sized data.

Write in the last

  • Learning stage, improper description, please also point out in the comments section
  • Keep it up!