JS implements Hill sorting

This article mainly introduces the implementation of Hill sorting in JS, which has certain reference value. Now I share it with you. Friends in need can refer to it.

Hill sorting is essentially an insertion sort. , but the sequence is grouped at equal intervals, and insertion sorting is performed in each group. This optimization reduces the original time complexity of O(n^2) to O(nlogn).

Basic idea

Hill sorting is to group the arrays according to a certain interval, and then perform insertion sorting in each group; then gradually reduce the interval and perform insertion sorting in each grouping. ...until the interval is equal to 1, do an insertion sort and end.

Then the question is, how big should the interval be and how to reduce it? Usually we take the initial interval to be half the length of the sequence: gap = length/2, and reduce it in the form of gap = gap/2. The entire process is illustrated in detail below.

The original array array is as follows:

#First take the interval as gap = length/2 = 4, and divide the array into the following 4 groups, Implement insertion sort for each group:

For the first sort, the smaller elements of each group are moved to a relatively front position (this state can It is called n-sorted, that is, grouping with n as gap and ordered). It is conceivable that a relatively ordered array may be more conducive to subsequent sorting. Then continue to group, gap = gap/2 = 2, implement insertion sort for each group:

Continue to group the array, gap = gap/2 = 1 , that is, all the elements form a group, and the insertion sorting algorithm is completed:

Code implementation

Inner loop use The insertion sort is basically the same as the ordinary insertion sort, except that the step size of each move becomes gap instead of 1:

// shellSort
function shellSort(arr) {
  for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
    // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
    for(let i = gap; i  0; j -= gap) {
        if(temp >= arr[j-gap]) {
          break;
        }
        arr[j] = arr[j-gap];
      }
      arr[j] = temp;
    }
  }
  return arr;
}

// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10];
alert(shellSort(arr));

The above is the entire content of this article, I hope it will be helpful to everyone's learning, more Please pay attention to the PHP Chinese website for related content!

Related recommendations:

Jquery adds loading transition mask

vue to achieve digital scrolling increase Effect

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