Inserting sorting is efficient when operating on almost 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 by one at a time.
Hill sorting is named after its designer Donald Shell, an algorithm published in 1959. Some old textbooks and reference manuals named the algorithm Shell-Metzner, which contains the name Marlene Metzner Norton, but according to Metzner himself, "I did nothing for this algorithm, my name shouldn't appear in the algorithm. in the name of
The basic idea of Hill sorting: first take an integer d1 smaller than n as the first increment, and divide all records of the file into groups of d1. All records with multiples of distance d1 are placed in the same group. First perform direct insertion sorting in each group; then, take the second increment d2 < d1 and repeat the above grouping and sorting until the increment dt=1 taken (dt < dt-l< … < d2 < d1) , that is, all records are placed in the same group and sorted directly.
This method is essentially a grouping insertion method.
Example 1:
The code copy is as follows:
/**
* Hill sorting, also known as the decreasing incremental sorting algorithm, is a more efficient and improved version of insert sorting. Hill sorting is a non-stable sorting algorithm.
*
* Hill sorting proposes an improved method based on the following two properties of insert sorting:
*
* Insert sorting is efficient when operating on almost sorted data, which means that the efficiency of linear sorting can be achieved.
* But insertion sort is generally inefficient because insertion sort can only move data by one 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:
The code copy is as follows:
<script type="text/javascript">
//document.write("---------------------------------------------------------------------------------------------------------------------- n to the power of 1.3 --------");
//document.write("<br /><br />")
//var array = new Array(12, 25, 32, 16, 18, 27, 59, 69, 36);
function shellSort(array) {
var j, i, v, h=1, s=3, k,n = array.length;
var result = "";
var count = 0;
while(h < n)
h=s*h+1;
while(h > 1) {
h=(h-1)/s;
for (k=0; k<h; k++)
for (i=k+h,j=i; i<n; i+=h, j=i) {
v=array[i];
While(true)
if ((j-=h) >= 0 && array[j] > v)
array[j+h]=array[j];
else
break;
array[j+h]=v;
}
count++;
result += "<br />Thread" + count + "The result of ordering through the pass is:";
for (var n = 0; n < array.length; n++) {
result += array[n] + ",";
}
}
return result;
}
//shallSort(array);
//document.write("<br /><br />");
</script>