How to implement JS Hill sorting and quick sorting

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 it. I hope it can help everyone. .

Hill sorting:

Define an interval sequence, such as 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:

Recursively decompose the data into different subsequences containing smaller elements and larger elements. 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));
}

Quick sorting is suitable for large data sets. Performance will decrease when processing small data sets.

Related recommendations:

Detailed analysis of the method of implementing Hill sorting algorithm in PHP

JavaScript sorting algorithm Hill sorting 2 examples_Basic knowledge

JavaScript Hill sort, quick sort, merge sort algorithm_javascript skills

##

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