When I first saw this, I was stunned. Later I read several other people’s articles before I understood

Before I get into this Hill Sorting, I want to play a little game that you’ve probably all played. The Hill ordering principle is similar to this little game

Xiao Ming (player), Angela (test maker)

Angela: please guess a number between 0 and 100. The fewer guesses you make, the higher the score you get

A normal player might start at 0 and try to guess one by one, 0, 1, 2, 3… So if you keep guessing, and you’re not lucky, you might have to guess 99 times to get it right.

Hill Sort is an updated version of insertion sort. The main purpose of Hill Sort is to reduce the number of guesses

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

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

The answer to

Xiaoming: Guess the number is 50

Angela: that suggests the number is too small

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

Angela: that suggests the number is too small

Xiaoming: So the range must be between (75 and 100). This time I’ll guess 87

Angela: that suggests the number is too small

Xiaoming: So the range must be between (87 and 100). I’ll guess 93 this time

Angela: I guess the numbers are too big

Xiao Ming: So the range must be between (87 and 93). Let’s guess 90 this time

Angela: I guess the numbers are too big

Xiaoming: So the range must be between (87 and 90). Let’s guess 89 this time

Angela: I guess the numbers are too big

Xiao Ming: So the range must be between (87 and 89). There are only 3 numbers left, so you can guess them one by one (insert sort). 87, 88, 89

Angela: the answer is eighty-eight

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

Now let’s get down to business

What is Hill Sort?

Hill sort is the grouping (delta for short) of a sequence, and then the insertion sort of each grouping separately. As the increment decreases gradually, each group contains more and more keywords. When the increment decreases to 1, the whole sequence is divided into a group exactly, and the algorithm terminates

Algorithm description

<img src=”https://noxussj.top:3000/24/1.png”></img>

<img src=”https://noxussj.top:3000/24/2.gif”></img>

Graph sorting algorithm (two) Hill sort is worth collecting the ten classic 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 in the GitHub below
  • The ongoing maintenance / 500 + face questions before update/notes 】 https://github.com/noxussj/In…
  • [3D city modeling using three. JS (Zhuhai City)] https://3d.noxussj.top/