preface

Reading “learning JavaScript data structure and algorithm (3rd edition)” have a feeling that I hope every time learning algorithm can output a blog, income column, check their own learning situation ~ article has a mistake welcome various big god correction, don’t spray, if you want to spray, trouble light, thank you ~

Ps: This book “Learning JavaScript Data Structures and Algorithms (3rd edition)” does not talk about Hill sort, so I have to do it myself

start

Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort. Unstable sorting algorithms, insertion sort can only move one neighboring position, hill sort optimizes this (Hill sort can move gap distances at a time), take advantage of the insertion sort is very fast in sorting almost already sorted arrays.

Hill sort is an improved method based on the following two properties of insertion sort:

  • Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort O(n);
  • But insert sort is generally inefficient because it can only move data one bit at a time;

Train of thought

Such as an array[9, 1, 2, 5, 7, 4, 8, 6, 3, 5]

  • First, divide the whole sequence of records to be sorted into several sub-sequences for insertion sorting, for example, divide the first sequence into five sub-sequences (the index of each sub-sequence is a value with gap).
  • The second sort will round down the sequence interval gap/2 and insert sort again
  • The third sorting will take the sequence interval gap = 1, at this time, the records in the whole sequence are “basically orderly”, then all records are directly inserted sort

implementation

function shellSort(array) {
  if (array.length <= 1) return array; // If the array length is 1, return it directly
  var gap = Math.floor(array.length / 2);
  while (gap > 0) {
    for (var i = gap; i < array.length; i++) {
      var j = i;
      var temp = array[j];
      while (j > 0 && array[j - gap] > temp) { Array [j-gap]>temp(array[j])
        array[j] = array[j - gap]; //TODO insertion sort is one bit behind
        array[j - gap] = temp; // Since insertion sort does not compare many elements, but two numbers, we can move the large value forward by a gap bit
        j -= gap; // Out of the loop condition
      }
    }
    gap = Math.floor(gap / 2); // Decrease the increment
  }
  return array;
}
var arr = [9.1.2.5.7.4.8.6.3.5];
console.log(shellSort(arr))
Copy the code

To optimize the

Hill sort is insert sort optimization no other optimization ideas, welcome various gods comment

The complexity of the

  • Time complexity

A single direct insertion sort does not change the relative order of the same elements and is stable. However, the same elements may be moved in their respective insertion sorts during multiple insertion sorts of Hill sort, which may lead to changes in the relative order of the same elements. So hill ordering is not stable. Best case: T(n) = O(n logn). Worst-case: T(n) = O(nlog2n). Average case: T(n) = depends on gap sequence.

  • Spatial complexity

In the process of Hill sorting, only the exchange operation of adjacent data is involved, only the temporary space of constant level is required, and the space complexity is O(1).

other

# Front-end algorithm learning – algorithm complexity # Front-end required algorithm (a) : bubble sort # front-end required algorithm (two) : select sort # front-end required algorithm (three) : Insert sort # front-end required algorithm (four) : merge sort # front-end required algorithm (five) : quick sort

The last

Dregs a, welcome the various gods many correction, not praise, but supervision correction \

reference

ES6 # the beauty of JavaScript data structures and algorithms – merge sort, quicksort, Hill sort, heap sort