Summary of the hill sort of the Java sort algorithm

This article illustrates the hill sort summary of the Java sort algorithm. Share with you for your reference. Specific analysis is as follows:

preface : Shell Sort is a type of insertion Sort. It is an improvement of direct insertion sort algorithm. This method, also known as reduced delta sort, got its name from dl.shell, which was proposed in 1959. This article focuses on how hill sort is implemented in Java.

Hill sort (reduction increment method) belongs to insertion sort, which is to divide the whole non-sequence into several small sub-sequences for insertion sort. The hill sort is not stable, O of 1 extra space, time order N times logN ^ 2. The worst case performance is comparable to the average performance.

Basic ideas:

Take an integer less than n, d1, as the first increment, and divide all the records in the file into d1 groups. All records of distance multiples of d1 are placed in the same group. First, direct insertion sort is performed in each group. And then you take the second increment, d2< D1 repeat the above grouping and sorting until the increment dt=1(dt< Dt - l< ... < D2 < D1), that is, until all records are placed in the same group for direct insertion sort.

Code implementation:

public class Test { 
  public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
  //Default data array
  public static void main(String args[]) { 
    int i; //Loop count variable
    int Index = a.length;//Data index variable
    System.out.print(" Before ordering : "); 
    for (i = 0; i < Index - 1; i++) 
      System.out.printf("%3s ", a); 
    System.out.println(""); 
    ShellSort(Index - 1); //Selection sort
    //Sorted result
    System.out.print(" After ordering : "); 
    for (i = 0; i < Index - 1; i++) 
      System.out.printf("%3s ", a); 
    System.out.println(""); 
  } 
  public static void ShellSort(int Index) { 
    int i, j, k; //Loop count variable
    int Temp; //Temporary variable
    boolean Change; //Whether the data has changed or not
    int DataLength; //The interval length of the split set
    int Pointer; //The location where the processing takes place
    DataLength = (int) Index / 2; //Length of initial set interval
    while (DataLength != 0) //The sequence can still be partitioned
    { 
      //The individual sets are processed
      for (j = DataLength; j < Index; j++) { 
        Change = false; 
        Temp = a[j]; //Store the value of Data[j] temporarily to be exchanged
        Pointer = j - DataLength; //Calculate the location of the processing
        //Compare and exchange the values of the values in the set
        while(Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index){ 
          a[Pointer + DataLength] = a[Pointer]; 
          //Calculate the next position to be processed
          Pointer = Pointer - DataLength; 
          Change = true; 
          if (Pointer < 0 || Pointer > Index) 
            break; 
        } 
        //With the final value
        a[Pointer + DataLength] = Temp; 
        if (Change) { 
          //Print the current sorted results
          System.out.print(" The sorting of : "); 
          for (k = 0; k < Index; k++) 
            System.out.printf("%3s ", a[k]); 
          System.out.println(""); 
        } 
      } 
      DataLength = DataLength / 2; //Calculate the interval length of the next partition
    } 
  } 
}

Hill sort has almost no worst-case scenarios, whether it's positive order, reverse order, out of order, it doesn't take a lot of time, the additional storage is O (1), which is really good. Before you figure out quicksort, heap sort, it's a good choice. I hope I can help you.

I hope this article has been helpful to your Java programming.