Two instances of hill sort of JavaScript sorting algorithm

Insertion sort is efficient in the operation of almost sorted data, that is, it can achieve the efficiency of linear sort.
But insertion sort is generally inefficient because it can only move the data one bit at a time.
Hill sort, named after its designer, Donald Shell, was published in 1959. Some older textbooks and reference manuals have named the algorithm shell-metzner, which includes the name Marlene Metzner Norton, but according to Metzner, "I didn't do anything for the algorithm, and my name should not be in the name of the algorithm."

< img border = 0 id = theimg onclick = window. The open this. (SRC) SRC = "/ / files.jb51.net/file_images/article/201404/201444153716757.gif? 201434153859 ">

The basic idea of hill sorting: take an integer less than n, d1, as the first increment, and divide all the records of the file into d1 groups. All records of distance multiples of d1 are placed in the same group. First, direct insertion sort is performed in each group. And then you take the second increment, d2 < D1 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.

The method is essentially a grouping insertion method.

Example 1:

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:

<script type="text/javascript">
//Document. The write (" -- -- -- -- -- -- -- -- -- -- hill sort, insertion sort of upgrade, shell out in 1959 -- -- -- -- -- - when incremental take the correct time complexity for n 1.3 power -- -- -- -- -- -- -- ");
//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 /> The first " + count + " The result of sorting through is :";
         for (var n = 0; n < array.length; n++) {
            result += array[n] + ",";
          }
 }
 return result;
}
//shallSort(array);
//document.write("<br /><br />");
</script>