What is Hill sort

Hill sorting is a kind of insertion sort, also known as "reducing incremental sorting". It is a more efficient and improved version of the direct insertion sorting algorithm. Hill sorting is a non-stable sorting algorithm. This method is due to " D.L.Shell" was proposed in 1959 and named after it.

Hill Sorting

Divide a set of elements to be sorted into several elements at certain intervals. Sequences are inserted and sorted separately. The "interval" set at the beginning is larger, and the interval is gradually reduced in each round of sorting, until the "interval" is 1, that is, the last step is to perform simple insertion sorting

Time complexity: and increment Sequence selection is related to non-stable sorting

Introduction:

Hill sort (Shell's Sort) is a kind of insertion sort, also known as "Diminishing Increment Sort" (Diminishing Increment Sort), which is a direct A more efficient and improved version of the insertion sort algorithm. Hill sorting is a non-stable sorting algorithm. This method is named after D.L. Shell proposed it in 1959.

Hill sorting is to group records by a certain increment of the subscript, and use the direct insertion sorting algorithm to sort each group; as the increment gradually decreases, each group contains more and more keywords. When the amount is reduced to 1, the entire file is divided into one group, and the algorithm terminates.

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