thought
The basic idea of quicksort is to select an element in the array as a keyword, through one sort, the array to be sorted into two parts, where the left part is smaller than all the keywords, the right part is larger than all the keywords. Then you do this for the left and the right, until all the elements are ordered, and you get a perfectly ordered array.
In an example, take the array [4, 5, 2, 7, 3, 1, 6, 8], and select the leftmost element of the array as pivot
The first step starts at the right and moves the right pointer to the left until it reaches 8,6, which is greater than 4, until it reaches 1, which is less than 4, so it moves 1 to the left. The right pointer stays still and begins to move the left pointer.
Moving the left pointer shows that 5 is larger than pivot 4, so moving 5 to the right pointer you just recorded moves everything greater than pivot to the right. Then start moving the right pointer.
Move the right pointer and find that 3 is smaller than pivot, so move 3 to the position of the left pointer and start moving the left pointer.
Move the left pointer, 2 is smaller than pivot, and then move again, finding that 7, 7 is larger than pivot, so put 7 in the record position of the right pointer and start moving the right pointer again.
Moving the right pointer, finding that the two Pointers overlap, inserts the pivot value into the position of the pointer (equivalent to finding the exact position where the pivot will be after sorting is complete). This is the end of the sequence.
After the sorting is finished, the overlapping pointer positions are recorded, and the left and right subarrays continue the above operation until they are divided into single-element arrays. When all the operations are done, the entire array becomes an ordered array.
The dynamic graph is shown below. The dynamic graph is illustrated with an unordered array of 20 elements. The gray background is the currently sorting subarray, and the orange is the current pivot. For the convenience of demonstration, the position of the pointer is reflected by swapping elements.
JS implementation
The code is as follows:
const quickSort = (array)=>{ quick(array, 0, array.length - 1) } const quick = (array, left, right)=>{ if(left < right){ let index = getIndex(array, left, right); quick(array, left, index-1) quick(array, index+1, right) } } const getIndex = (array, leftPoint, rightPoint)=>{ let pivot = array[leftPoint]; while(leftPoint < rightPoint){ while(leftPoint < rightPoint && array[rightPoint] >= pivot) { rightPoint--; } array[leftPoint] = array[rightPoint] // swap(array, leftPoint, rightPoint) While (leftPoint < RightPoint &&Array [leftPoint] <= pivot) {leftPoint++; } array[rightPoint] = array[leftPoint] // swap(array, leftPoint, rightPoint) } array[leftPoint] = pivot return leftPoint; } const swap = (array, index1, index2)=>{ var aux = array[index1]; array.splice(index1, 1, array[index2]) array.splice(index2, 1, aux) } const createNonSortedArray = (size)=>{ var array = new Array(); for (var i = size; i > 0; i--) { //array.push(parseInt(Math.random()*100)); array.push(i*(100/size)); Array. Sort (function () {return (0.5 - Math. The random ()); }); } return array; } var arr = createNonSortedArray(20); quickSort(arr) console.log(arr) //[5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100]Time complexity
Quicksort is obviously a divide-and-conquer idea, but it’s pivot, so if you split your data in half every time, then the depth of the recursion tree is logN, so the quicksort time is order NlogN. And if each pivot splits the array into something empty and something full, then the depth of the recursion tree will be n-1, and the time complexity will be O(n ^2).
According to the time complexity analysis above, we find that if a data is completely ordered, then using our quicksort algorithm above is the worst case, so how to choose pivot becomes the focus of optimizing quicksort. If we continue to use the algorithm above, So we can randomly choose the pivot instead of the first element of the array.