Quick sort, also known as partitioning and swap sorting. A quick sorting algorithm implemented with the strategy of dividing and conquer.
This article mainly talks about using javascript to implement quick sorting of in-place ideas
Dividing and treating methods:
In computer science, the division and conquer method is a very important algorithm paradigm based on multiple branch recursion. The literal explanation is "dividing and conquering", which means dividing a complex problem into two or more identical or similar sub-problems until the end of the sub-problem can be simply and directly solved, and the solution of the original problem is the merger of the solutions of the sub-problem. (Excerpt from Wikipedia)
Quick sorting idea
Specify an element in the array as a ruler, place the larger than it and put the smaller than it before the element, repeat this until all are arranged in the positive order.
Quick sorting is divided into three steps:
Select a benchmark: Select an element as the benchmark in the data structure (pivot)
Partition: refer to the size of the reference element value, divide the unordered area. All data smaller than the reference element is placed in one interval, and all data larger than the reference element is placed in another interval. After the partition operation is completed, the position of the reference element is the position where it should be after the final sorting.
Recursion: Recursively call the algorithms in Step 1 and Step 2 for the first time until there is only one element left in all the unordered intervals.
Now let’s talk about the common implementation methods (no in-place algorithm is used)
function quickSort(arr) {if (arr.length <= 1) return ;//Please the digit benchmark closest to the middle of the array, odd numbers and even numbers take values different, but I don’t think so. Of course, you can choose the first or the last number as the benchmark, and there is no too much description here var pivotIndex = Math.floor(arr.length / 2);var pivot = arr.splice(pivotIndex, 1)[0];//Left and left intervals are used to store sorted numbers var left = [];var right = [];console.log('Basic is: ' + pivot + ' when');for (var i = 0; i < arr.length; i++) {console.log('The '+ (i + 1) + ' loop of partition operation:');//There is less than the reference, put in the left interval, greater than the reference, put in the right interval if (arr[i] < pivot) {left.push(arr[i]);console.log('Left:' + (arr[i]))} else {right.push(arr[i]);console.log('Right:' + (arr[i]))}}//The concat operator is used here to splice the left interval, reference, and right interval into a new array //Then recursively 1 and 2 steps until all unordered intervals have only one element left, and the recursive end returns quickSort(left).concat([pivot], quickSort(right));}var arr = [14, 3, 15, 7, 2, 76, 11];console.log(quickSort(arr));/** When the base is 7, the first partition is obtained with two subsets on the left and right [ 3, 2,] 7 [14, 15, 76, 11];* With the base is 2, the left subset [3, 2] is partitioned and sorted to obtain [2] 3. All sorting of the left subset ends* With the reference as 76, the right subset is divided and sorted to obtain [14, 15, 11] 76* At this time, the above [14, 15, 11] is divided and sorted to the above [14, 15, 11] is divided and sorted to the above [14, 11] is divided and sorted to the above [14, 11] is divided and sorted to the above [14, 11] is divided and sorted to the above [14, 11] is divided and sorted to the above [11] is divided and sorted to the base 11, 11 [14]* There is only one element left in all unordered intervals, and the recursive end**/Through breakpoint debugging, the results can be obtained.
Disadvantages:
It requires extra storage space of Ω(n), which is as bad as merge sorting. In a production environment, additional memory space is required, affecting performance.
At the same time, many people think that the above is a real quick sort. Therefore, below, it is necessary to recommend the quick sorting of the in-place algorithm
For information about the in-situ algorithm, please refer to Wikipedia. The students who are under the wall are similar to Baidu.
in-place
Quick sorting is generally implemented with recursion. The most important thing is the partition segmentation function, which divides the array into two parts, one is smaller than pivot and the other is larger than pivot. The specific principle has been mentioned above
function quickSort(arr) {// swap function swap(arr, a, b) {var temp = arr[a];arr[a] = arr[b];arr[b] = temp;}// partition function partition(arr, left, right) {/*** At the beginning, you don't know the final pivot storage location, you can swap pivot to the back first* Here you directly define the rightmost element as the reference*/var pivot = arr[right];/*** When storing elements smaller than pivot, they are next to the previous element, otherwise the element stored in the gap may be larger than pivot, * Therefore, a storeIndex variable is declared and initialized to left to store elements smaller than pivot next to each other. */var storeIndex = left;for (var i = left; i < right; i++) {if (arr[i] < pivot) {/*** traverse the array and find the element smaller than pivot, (elements larger than pivot will be skipped) * Put the element obtained when looping i times to storeIndex through swap exchange, * and increment the storeIndex by 1 to indicate the next position that may be swapped*/swap(arr, storeIndex, i);storeIndex++;}}// Finally: swap pivot to storeIndex, place the benchmark element at the final correct position swap(arr, right, storeIndex);return storeIndex;}function sort(arr, left, right) {if (left > right) return;var storeIndex = partition(arr, left, right);sort(arr, left, storeIndex - 1);sort(arr, storeIndex + 1, right);}sort(arr, 0, arr.length - 1);return arr;}console.log(quickSort([8, 4, 90, 8, 34, 67, 1, 26, 17]));Partition optimization
Careful students here may ask whether there will be different performance performance when selecting different benchmarks. The answer is yes, but because I am a front-end person and don’t know much about the algorithm, so this pit is left to powerful people to fill.
Complexity
Quick sorting is the fastest sorting algorithm, and its time complexity is O(log n)
In the average situation, the order of n items requires Ο(n log n) comparisons. In the worst case, Ο(n2) comparisons are required.
https://github.com/LYZ0106/
The above is the quick sorting method of JavaScript implementation in-place ideas introduced by the editor. I hope it will be helpful to everyone. If you have any questions, please leave me a message. The editor will reply you in time. Thank you very much for your support for the Wulin Network website!