Summary of Java sorting algorithm Hill sorting

This paper gives an example of hill sorting, a summary of Java sorting algorithms. Share with you for your reference. The specific analysis is as follows:

Shell sort is a kind of insertion sort. It is an improvement of direct insertion sorting algorithm. This method, also known as reduced incremental sorting, is named after dl. Shell in 1959. This paper mainly introduces how Hill sorting is implemented in Java.

Hill sort (reduced increment method) belongs to insertion sort, which divides the whole non sequence into several small subsequences for insertion sort respectively. Hill sorting is not stable. The additional space of O (1) has a time complexity of O (n * (logn) ^ 2). The execution efficiency in the worst case is not much different from that in the average case.

Basic idea:

Take an integer D1 less than n as the first increment, and divide all the records of the file into D1 groups. All records whose distance is a multiple of D1 are placed in the same group. First, perform direct insertion sorting in each group; Then, take the second increment D2 < D1 and repeat the above grouping and sorting until the increment DT = 1 (DT < dt-l <... < D2 < D1), that is, all records are placed in the same group for direct insertion sorting.

Code implementation:

There is almost no worst case for Hill sorting. Whether it is in positive order, reverse order or out of order, the time used is not much. The additional storage is O (1), which is really very good. It's really a good choice before you know about quick sort and heap sort. I hope it can help you.

I hope this article will be helpful to your Java programming.