The road to learning sorting algorithms - Hill sort
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:
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.
Related Articles
The road to learning sorting algorithms - merge sort
Publish Date:2025/03/19 Views:157 Category:ALGORITHM
-
Let's first look at the definition of merge sort Merge sort is an effective sorting algorithm based on the merge operation. This algorithm is a very typical application of the Divide and Conquer method. Merge the ordered subsequences to obt
The road to learning sorting algorithms - merge sort (non-recursive implementatio
Publish Date:2025/03/19 Views:188 Category:ALGORITHM
-
In the article "Merge Sort", we introduced the principles and operation steps of merge sort, and finally implemented the sorting algorithm using PHP code. In the program, we used the principle of recursion to implement the algorithm. In fac
The road to learning sorting algorithms - quick sort
Publish Date:2025/03/19 Views:121 Category:ALGORITHM
-
Quick sort is a sorting algorithm developed by Tony Hall. On average, sorting n items requires O(n log n) comparisons. In the worst case, O(n2) comparisons are required, but this is uncommon. In fact, quick sort is often significantly faste
The road to learning sorting algorithms - quick sort (non-recursive implementatio
Publish Date:2025/03/19 Views:78 Category:ALGORITHM
-
In the article "Quick Sort", we introduced the principles and steps of quick sort, and implemented the algorithm using recursion. In the previous article, we also mentioned the use of non-recursive methods to implement the algorithm. In thi
The road to learning sorting algorithms - heap sort
Publish Date:2025/03/19 Views:145 Category:ALGORITHM
-
Like other sorting algorithms, let's first look at the definition of heap sort. Heapsort : refers to a sorting algorithm designed using the heap data structure. A heap is a structure that approximates a complete binary tree and satisfies th
Common sorting algorithms
Publish Date:2025/03/19 Views:66 Category:ALGORITHM
-
This article introduces several commonly used sorting algorithms in software engineering. The core codes of all sorting algorithms are introduced in "Core Codes of Common Sorting Algorithms" 1. Insertion Sort The basic idea of inserti
The road to learning sorting algorithms - selection sort
Publish Date:2025/03/19 Views:160 Category:ALGORITHM
-
Selection sort is a simple and intuitive sorting algorithm. Its basic idea is to select a maximum (or minimum) element in an unsorted sequence and put it at the end (note: this is the end of the unsorted sequence, which can be considered as
The road to learning sorting algorithms - bubble sort
Publish Date:2025/03/19 Views:80 Category:ALGORITHM
-
Bubble sort is also a simple and intuitive sorting algorithm. The idea is that it repeatedly visits the sequence to be sorted, compares two elements at a time, and swaps them if they are in the wrong order. The work of visiting the sequence
Core code of commonly used sorting algorithms
Publish Date:2025/03/19 Views:122 Category:ALGORITHM
-
In the article "Common Sorting Algorithms", we briefly introduced the ideas and implementation steps of various sorting algorithms. In this article, I will share the core codes of these sorting algorithms with you. The complete code of all