Detailed explanation of Javascript quick sort algorithm

Detailed explanation of Javascript quick sort algorithm_Basic knowledge

WBOY

Release： 2016-05-16 16:29:14

Original

1419 people have browsed it

Quick sort is an improvement on bubble sort. Divide the data to be sorted into two independent parts through one-pass sorting. All the data in one part is smaller than all the data in the other part. Then use this method to quickly sort the two parts of the data respectively. The entire sorting process can Proceed recursively, and finally the entire data becomes an ordered sequence.

Assume that the array to be sorted is A[0]...A[N-1]. First, randomly select a data (usually the first number of the array) as the benchmark data, and then all numbers smaller than it are Put it in front of it, and all numbers larger than it are put behind it. This process is called one-pass quick sort. It is worth noting that quick sort is not a stable sorting algorithm, that is, the relative positions of multiple identical values may change at the end of the algorithm.
The algorithm of one-pass quick sort is:
1) Set two variables low and high. When sorting starts: low=0, high=N-1;
2) Use the first array element as the reference data and assign it to base, that is, base=A[0];
3) Search forward from high, that is, search forward from back (high--), find the first value A[high] that is less than base, and exchange A[high] and A[low];
4) Search backward from low, that is, search from front to back (low), find the first A[low] that is greater than base, and exchange A[low] and A[high];
5) Repeat steps 3 and 4 until low=high;

Copy code The code is as follows:

function partition(elements, low, high){

//By default, the first element on the left is used as the base element 

var base=elements[low];

while(low < high){

//Search from back to front until an element smaller than the base element is found and exchange it 

While(low < high && elements[high] >= base) high--;

var swap1=elements[low];elements[low]=elements[high];elements[high]=swap1;

//Search from front to back until an element larger than the base element is found and exchange it 

While(low < high && elements[low] <= base) low ;

var swap2=elements[low];elements[low]=elements[high];elements[high]=swap2;

}

//Return the position of the reference element as the split position of the sequence

Return low;

}

function sort(elements, low, high){

if(low
// Divide the sequence into two and divide it into the sequence before and after the split position. The former sequence has a smaller value than the split position, and the latter sequence has a larger value than the split position 

var partitionPos=partition(elements, low, high);

//Continue recursively sorting the previous sequence

Sort(elements, 0, partitionPos-1);

//Continue recursively sorting the subsequent sequence

Sort(elements, partitionPos 1, high);

}

}

var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];

console.log('before: ' elements);

sort(elements, 0, elements.length-1);

console.log(' after: ' elements);

Efficiency:

Time complexity: Best: O(nlog2n), Worst: O(n^2), Average: O(nlog2n).

Space complexity: O(nlog2n).

Stability: Unstable.