Two Examples of JavaScript Sorting Algorithm Hill Sorting

Two Examples of JavaScript Sorting Algorithm Hill Sorting_Basic Knowledge

WBOY

Release： 2016-05-16 16:53:18

Original

1628 people have browsed it

Insertion sort is highly efficient when operating on almost sorted data, that is, it can achieve the efficiency of linear sorting.
But insertion sort is generally inefficient because insertion sort can only move data one bit at a time.
Hill sorting is named after its designer, Donald Shell, and the algorithm was published in 1959. Some older textbooks and reference manuals named the algorithm Shell-Metzner, which contains the name of Marlene Metzner Norton, but according to Metzner herself, "I did nothing for this algorithm, and my name should not appear in the algorithm." "

Two Examples of JavaScript Sorting Algorithm Hill Sorting_Basic Knowledge

The basic idea of Hill sorting: first take an integer d1 less than n as the first increment, and divide all the records in the file into d1 groups. All records whose distance is a multiple of d1 are placed in the same group. First perform direct insertion sorting within each group; then, take the second increment d2 < d1 and repeat the above grouping and sorting until the increment dt=1(dt < dt-l< … < d2 < d1), that is, until all records are placed in the same group for direct insertion sort.

This method is essentially a grouped insertion method.

Example 1:

Copy code The code is as follows:

/**
* Hill sorting, also known as descending incremental sorting algorithm, is a more efficient and improved version of insertion sort. Hill sorting is a non-stable sorting algorithm.
*
* Hill sorting proposes an improved method based on the following two properties of insertion sort:
*
* Insertion sorting is highly efficient when operating on almost already sorted data. , that is, the efficiency of linear sorting can be achieved
* but insertion sorting is generally inefficient, because insertion sorting can only move data one bit at a time
*
*/

function shellSort( list ) {
var gap = Math.floor( list.length / 2 );

while( gap > 0 ) {

for( i = gap; i < list.length; i ) {
temp = list[i];

for( j = i; j >= gap && list[j - gap ] > temp; j -= gap ) {
list[j] = list[j - gap];
list[j] = temp;
}

gap = Math.floor( gap / 2 );
}

return list;
};

// test
var arr = [2, 1, 3 , 12, 5, 66, 23, 87, 15, 32];

shellSort(arr);

Example 2:

Copy code The code is as follows: