Detailed explanation of examples of java Hill sorting

This article mainly introduces the Java data structure and algorithm Hill sorting, and analyzes the concept, principle, implementation method and related precautions of Hill sorting in the form of examples. Friends in need can refer to the following

The examples in this article describe the Hill sorting of Java data structures and algorithms. Share it with everyone for your reference, the details are as follows:

What I want to introduce here is Hill sorting (reduced incremental sorting method).

Hill sort: Works by comparing elements that are a certain distance apart; the distance (increment) used for each comparison decreases as the algorithm proceeds until only adjacent ones are compared until the last sort of elements. It is a type of insertion sort and an improvement on the direct insertion sort algorithm.

Algorithmic idea: First divide the sequence to be sorted into several subsequences according to a certain increment d, perform direct insertion sorting on all elements in each subsequence, and then use a smaller Group it by increment, and then sort it in each group. When the increment is reduced to 1, the entire number to be sorted is divided into one group and the sorting is completed. Note: The value of the increment - generally half of the sequence is taken as the increment for the first time, and then halved each time until the increment is 1.

The algorithm implementation code is as follows:

package exp_sort;
public class ShellSort {
  public static void shell(int array[]) {
    int j;
    int average;
    //设置增量的值
    for (average = array.length / 2; average > 0; average /= 2) { //步长
      for (int i = average; i < array.length; i++) { //子序列进行直接插入排序
        int temp = array[i];
        for (j = i; j >= average && temp < array[j - average]; j -= average) {
          array[j] = array[j - average];
        }
        array[j] = temp;
      }
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    shell(array);
  }
}

Algorithm analysis: This algorithm inserts and sorts elements according to different step lengths. When the elements are very disordered at the beginning, the step size is the largest, so the number of elements in insertion sort is very small and the speed is very fast; when the elements are basically ordered, the step size is very small, and insertion sort is very efficient for ordered sequences. Therefore, The time complexity of Hill sorting will be better than O(n^2), which is O(n^1.5), The sorting efficiency is much higher than that of insertion sorting . Due to multiple insertion sortings, we know that one insertion sorting is stable and will not change the relative order of the same elements. However, in different insertion sorting processes, the same elements may move in their respective insertion sortings, and finally their stability will change. is disrupted, so the shell sorting is unstable. Hill sorting is not as fast as quick sorting algorithm O(N*(logN)), so it is more suitable for sorting medium-sized data, but is not the optimal choice for sorting very large-scale data. But it is much faster than the O(N^2) complexity algorithm. And Hill sorting is very easy to implement, and the algorithm code is short and simple. In addition, the difference between the performance efficiency of Hill's algorithm in the worst case and the average case is not much, while the efficiency of quick sort in the worst case will be very poor.

【Related Recommendations】

1. Special Recommendation: "php Programmer Toolbox" V0.1 version download

2. Java Free Video Tutorial

3. YMP Online Manual

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