JavaScript implements quick sort analysis

This article mainly introduces the method of implementing quick sort in JavaScript. It analyzes the principle, implementation method and related operation precautions of quick sort in the form of examples. Friends in need can refer to it. I hope it can help everyone.

Idea:

Use the divide-and-conquer idea and recursive method to decompose the data into different subsequences containing smaller elements and larger elements.

1. Select an element in the array as the base

2. Traverse the array. Elements smaller than the base are moved to the left of the base, and elements larger than the base are moved to the right of the base.

3. Repeat the first two steps for the two subsets on the left and right side of the benchmark until there is only one element left in all subsets

Implementation code:

function sqort(arr){
 if(arr.length===0){
 return [];
}
var left=[];
var right=[];
var pivot=arr[0];//(基准以首元素)
for(var i=1;i<arr.length;i++){
 if(arr[i]<pivot){
 left.push(arr[i]);
}else{
 right.push(arr[i]);
}
}
return sqort(left).concat(pivot,qsort(right));//递归
}
var a=[];
for (i=0;i<10;++i){
a[i]=Math.floor(Math.random()*100+1);
}
console.log(a);
console.log(sqort(a));
//(基准以中间元素的情况)
function sqort(arr){
 if(arr.length<=1){
 return arr;
}
var left=[];
var right=[];
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];//(基准以中间元素)
for(var i=1;i<arr.length;i++){
 if(arr[i]<pivot){
 left.push(arr[i]);
}else{
 right.push(arr[i]);
}
}
return sqort(left).concat(pivot,sqort(right));//递归
}
var a=[12,34,23,78,34,26];
console.log(a);
console.log(sqort(a));

Note: Recursively call the sqort() function for smaller arrays and larger arrays respectively , when the recursion ends, the smaller array is connected to the base and the larger array to form the final ordered array and returned.

Related recommendations:

Example of PHP implementation of quick sorting method

Example of PHP implementation of quick sorting algorithm for two-dimensional arrays

How to implement quick sort

The above is the detailed content of JavaScript implements quick sort analysis. For more information, please follow other related articles on the PHP Chinese website!