The idea of "quick sorting" is very simple, and the entire sorting process only requires three steps:
(1) In the dataset, select an element as the "base" (pivot).
(2) All elements smaller than the "reference" are moved to the left of the "reference"; all elements larger than the "reference" are moved to the right of the "reference".
(3) For the two subsets on the left and right of the "baseline", repeat the first and second steps until there is only one element left in all subsets.
For example, there is now a dataset {85, 24, 63, 45, 17, 31, 96, 50}. How to sort it?
In the first step, select the intermediate element 45 as the "base". (The reference value can be selected arbitrarily, but choosing the intermediate value is easier to understand.)
The second step is to compare each element with the "base" in order to form two subsets, one is "less than 45" and the other is "greater than or equal to 45".
The third step is to repeat the first and second steps for the two subsets until there is only one element left in all subsets.
The following is a reference to the online information (here and here) to implement the above algorithm in Javascript language.
First, define a quickSort function whose parameters are an array.
var quickSort = function(arr) {};Then, check the number of elements in the array, and if it is less than or equal to 1, it will be returned.
var quickSort = function(arr) { if (arr.length <= 1) { return arr; }};Next, select "pivot" and separate it from the original array, and then define two empty arrays to store two subsets of one left and one right.
var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2) ; var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = [];};Then, start traversing the array, put elements smaller than the "base" into the subset on the left, and elements larger than the base into the subset on the right.
var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2) ; var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } }};Finally, repeat this process continuously using recursion to get the sorted array.
var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right));};When using it, just call quickSort().
The above is a detailed explanation of the Quicksort algorithm examples of the JavaScript algorithm series introduced by the editor. I hope it will be helpful to everyone. If you have any questions, please leave me a message and the editor will reply to everyone in time. Thank you very much for your support to Wulin.com website!