When I first started watching this, I was so confused. After reading a few more articles by others, I understood it

Before I get into this Hill sorting, I want to play a little game that you’ve probably played before. Hill’s sorting principle is pretty much the same as this little game

Xiao Ming (player), Angela (test maker)

Angela: Please guess a number between 0 and 100. The lower the number of guesses, the higher the score

A normal player would guess from zero, zero, one, two, three… So if you keep guessing, you’re going to have to guess 99 times to get it right.

Hill sort is an updated version of insertion sort, the main purpose of which is to reduce the number of guesses

Xiao Ming finally used the method of /2 to guess the number (this is the Hill sort)

---------------------------------------------------

The answer to

Xiaoming: Guess the number is 50

Angela: The hint is that the number is small

Xiaoming: So the range must be between (50~100). I guess 75 this time

Angela: The hint is that the number is small

Xiaoming: So the range must be between (75~100), this time I guess 87

Angela: The hint is that the number is small

Xiaoming: So the range must be between (87~100), this time I guess 93

Angela: The hint was that the number was higher

Xiaoming: So the range must be between (87~93), guess 90 this time

Angela: The hint was that the number was higher

Xiaoming: So the range must be between (87~90), I guess 89 this time

Angela: The hint was that the number was higher

Ming: So the range must be (87~89). There are 3 numbers left, so we can guess one by one (insertion sort). 87, 88, 89

Angela: The answer is 88

---------------------------------------------------

Now let’s get down to business

What is a Hill order?

Hill sort is grouping (delta for short) in a sequence and inserting sort each group separately. As the increments decrease gradually, each group contains more and more keywords. When the increments decrease to 1, the whole sequence is just divided into one group, and the algorithm terminates

Algorithm description

Figure sorting algorithm (2) of the Hill sorting worthy of the collection of the top ten classical sorting algorithm

additional

  • This article is published through multiple platforms of “we media” and will not be maintained after publication. If you have any objection to the content, you can discuss it on GitHub below

  • Continuous maintenance/update 500+ github.com/noxussj/Int…

  • 3D city modeling using three.js (Zhuhai