JIYIK CN >

Current Location:Home > Learning > ALGORITHM >

The road to learning sorting algorithms - Hill sort

Author:JIYIK Last Updated:2025/03/19 Views:

Hill sort is named after the designer of the algorithm, Hill. It is an improvement of Hill on the basis of insertion sort and can be said to be a special insertion sort.

Here are the properties of insertion sort:

First of all, the insertion sort algorithm is very efficient when operating on already ordered data, and can achieve the efficiency of linear sorting.

Secondly, when inserting sort, only one data can be moved in each sorting, so this sorting method is relatively inefficient.

Based on this property, the designer of Hill sort invented the Hill sort algorithm, whose basic idea is:

First, the entire sequence of records to be sorted is divided into several subsequences and sorted by direct insertion. The method of dividing the subsequence is to set an increment. When each subsequence is in order, the increment is reduced by half (divided by 2, rounded up), and the subsequence is sorted again. This is done in sequence. When the records in the entire sequence are basically in order, all records are sorted by direct insertion in sequence. At this time, the increment is reduced to 1, because direct insertion sort is very efficient when the elements are basically in order (according to the first point above, close to the best case).

Therefore, to sum up, Shell sort is a group insertion method. Because an increment is set and the increment is reduced by 1 in sequence, Shell sort is also called a descending incremental sorting algorithm.

The algorithm steps of Hill sort can be represented by the following figure:

Schematic diagram of Hill sort algorithm 1

Hill sort algorithm principle diagram 2

Hill sort algorithm principle diagram 3

It should be mentioned here that Shell sort is a stable sort. We can set a set of data to be sorted in the above way, and we can find that it is a stable sort.

After Hill sort is grouped by increments, insertion sort can be used to sort within the group. Of course, bubble sort, selection sort, etc. can also be used.

Here is the PHP implementation code of Hill sort

$arr = array(10,6,20,50,30,7,23,35,40,1,17);
/*
 * 首先初始化 增量  数组长度/2 取整 floor() 函数向下取整  对于增量每次循环都由 当前增量/2
 */
for($dl=floor(count($arr)/2);$dl>=1;$dl=floor($dl/2)){
    /*
     * 每次从 增量的位置开始,直到数组递增变量达到数组的长度
     */
    for($j=$dl;$j<count($arr);$j++){
        for($i=$j-$dl;$i>=0;$i-=$dl){
            if($arr[$i+$dl]<$arr[$i]){
                $temp = $arr[$i+$dl];
                $arr[$i+$dl]=$arr[$i];
                $arr[$i]=$temp;
            }
        }
    }
}

The above code is just one of the implementation methods. There are many ways to implement it. There are many ways to sort within a group. If you have any good method, please leave a message below so that we can discuss and improve together.

For reprinting, please send an email to 1244347461@qq.com for approval. After obtaining the author's consent, kindly include the source as a link.

Article URL:

Related Articles

Check if a Post exists in PHP

Publish Date:2025/04/13 Views:170 Category:PHP

PHP $_POST is a super global variable that can contain key-value pairs of HTML form data submitted through the post method. We will learn different ways to check $_POST if a and contains some data in this article. These methods will use iss

PHP with Ajax

Publish Date:2025/04/13 Views:139 Category:PHP

We will use PHP and ajax by printing a simple sum of two numbers 2 and . Also, print a php array in JSON. 3 object We will also use PHP with ajax by getting the HTML formatted output from the number division in PHP. Printing simple addition

Store Div Id in PHP variable and pass it to JavaScript

Publish Date:2025/04/13 Views:51 Category:PHP

This article shows you how to div id store a in a PHP variable and pass it to JavaScript code. We will answer the following questions. What is div id ? How to div id store in a PHP variable? How to pass variables to JavaScript code? Let’s

Returns the article tag with ID from the action page

Publish Date:2025/04/13 Views:80 Category:PHP

Let's say you're in a login form and you enter the wrong information; in this case, you probably want to go back to the login page. PHP has a built-in function header() to redirect a page to a specific page. But what if the login page is at

Switching PHP versions on Ubuntu

Publish Date:2025/04/13 Views:78 Category:PHP

Different tasks may require running multiple versions of PHP. You may need to switch PHP versions by running two sites on the same server or testing older versions of code using outdated methods. We can switch PHP versions on Ubuntu using t

Resizing images in PHP

Publish Date:2025/04/13 Views:155 Category:PHP

In this tutorial article, we will discuss about resizing images in PHP. Load the image before resizing Before we can resize an image, we must first load it as an image resource in our script. This is file_get_contents() different from using

PHP upload image

Publish Date:2025/04/13 Views:61 Category:PHP

We can upload images in PHP using simple file upload operation, but first, php.ini file upload should be enabled from Files. This tutorial demonstrates how to upload images in PHP. php.ini Enable file upload from file in PHP to upload image

Creating a signature from Hash_hmac() and Sha256 in PHP

Publish Date:2025/04/13 Views:107 Category:PHP

PHP has one of the best encryption functions for data security. Hash_hmac() The encrypt function is one of the most famous encryptors. We'll show you how to use hash_hmac and sha256 encryptors to create 安全签名 one that you can store i

Updating PHP 7.x to 7.4 on CentOS

Publish Date:2025/04/13 Views:131 Category:PHP

This article shows the steps to update the PHP version from 7.x version to 7.4 in CentOS. How to Update PHP from 7.X to 7.4 in CentOS Update operating system packages. yum update -y Check your PHP version in CentOS. php -v Prints a list of

Scan to Read All Tech Tutorials

Social Media
  • https://www.github.com/onmpw
  • qq:1244347461

Recommended

Tags

Scan the Code
Easier Access Tutorial