Detailed explanation of sorting of JS Hill algorithm

Hill algorithm is also a kind of insertion sort in principle. Before understanding Hill algorithm, you must understand insertion sort; previously we shared with you JS insertion sort detailed explanation, I hope this article can Help everyone.

Principle:
Hill sorting groups the data based on insertion sorting, divides the original data into several subsets, and then sorts each The subsets are sorted, and so on, continuously divided into subsets, until finally they are completely sorted.

Sequence: [3,5,2,4,7,6,8,9,1]
First divide the entire sequence into subsets based on gap, and sort the subsets; (The gap is generally Math.floor(arr.length/2))
gap:4
The divided subsets are: 3,7,1 5,6 2,8 4,9 are subsets
After sorting the subsets: 1,3,7 5,6 2,8 4,9
The number is: [1,5,2,4,3,6,8,9,7]

Modify the gap value and sort again
gap: 2
……..
Stop until the gap value is 0

JS code implementation:

var arr=[3,5,2,4,7,6,8,9,1];var gap=Math.floor(arr.length/2);       
while(gap>0){    for(var i=gap;i<arr.length;i++){        var temp=arr[i];        var j=i-gap;        while(j>=0&&arr[j]>temp){
            arr[j+gap]=arr[j];
            arr[j]=temp;
            j-=gap;
        }
        arr[j+gap]=temp;
        }
    gap=Math.floor(gap/2); 
}

输出结果： [1, 2, 3, 4, 5, 6, 7, 8, 9]

Related recommendations:

Detailed explanation of JS insertion sort

Example analysis of basic commonly used sorting algorithms in JavaScript

javascript array deduplication and quick sort algorithm examples detailed explanation

The above is the detailed content of Detailed explanation of sorting of JS Hill algorithm. For more information, please follow other related articles on the PHP Chinese website!