About JS Hill sorting algorithm (detailed tutorial)

This article mainly introduces the implementation methods of Hill sorting and quick sorting of the JS sorting algorithm. It analyzes the principles of Hill sorting and quick sorting and the JavaScript implementation techniques in the form of examples. Friends in need can refer to the following

The examples in this article describe the implementation methods of Hill sorting and quick sorting of JS sorting algorithm. Share it with everyone for your reference, the details are as follows:

Hill sorting:

Define an interval sequence, for example, 5, 3, 1 . The first time it is processed, all elements with an interval of 5 will be processed, the next time it will be processed with an interval of 3, and the last time it will process elements with an interval of 1. That is, adjacent elements perform standard insertion sort.

When starting the last processing, most of the elements will be in the correct position, and the algorithm will not have to exchange many elements, which is more advanced than inserting elements.

Time complexityO(n*logn)

function shellSort(){
  var N=arr.length;
  var h=1;
  while(h<N/3){
    h=3*h+1;//设置间隔
  }
  while(h>=1){
    for(var i=h; i<N; i++){
      for(j=i; j>=h && arr[j]<arr[j-h]; j-=h){
        swap(arr, j, j-h);
      }
    }
    h=(h-1)/3;
  }
}
function swap(array, i, j){//两个数调换
  var temp =array[j];
  array[j]=array[i];
  array[i]=temp;
}

Quick sort:

Passed Recursively decompose the data into different subsequences containing smaller elements and larger elements, and repeat this step until all the data is ordered.

Choose a benchmark value, and put it in an array if it is smaller than the benchmark value. Those greater than the benchmark value are placed in an array.

Time complexityO(n*logn)

function quickSort(arr){
  if(arr.length==0){
    return [];
  }
  var left=[];
  var right=[];
  var p=arr[0];
  for(var i=1; i<arr.length; i++){
    if(arr[i]<p){
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(p,quickSort(right));
}

The above is what I compiled for everyone. I hope it will be helpful to everyone in the future.

Related articles:

What to say about null and false values ​​in javaScript

About automated builds in Webpack (detailed tutorial )

How to implement a series of functions such as image uploading in the WeChat applet

How to build a universal data simulation framework for the front end (detailed tutorial)

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