Algorithmic ideas for implementing quick sort in JavaScript

This article mainly introduces the algorithmic ideas about JavaScript to implement quick sorting. It has certain reference value. Now I share it with you. Friends in need can refer to it.

At present, the most common sorting algorithm is probably There are seven or eight types, among which "Quicksort" is the most widely used and faster. It was proposed by Turing Award winner C. A. R. Hoare in 1960.

The idea of ​​"Quick Sort" is very simple. The entire sorting process only requires three steps:

(1) In the data set, select an element as the "pivot" (pivot).

　(2) All elements smaller than "baseline" are moved to the left of "baseline"; all elements larger than "baseline" are moved to the right of "baseline".

　(3) For the two subsets on the left and right of the "baseline", repeat the first and second steps until all subsets have only one element left.

For example, there is now a data set {85 , 24, 63, 45, 17, 31, 96, 50}, how to sort them?

The first step is to select the middle element 45 as the "baseline". (The base value can be arbitrary Choose, but choosing the middle value is easier to understand.)

The second step is to compare each element with the "baseline" in order to form two subsets, one "less than 45", and the other "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. So far.

Follow the previous steps and define a quickSort function:

var quickSort = function(arr) { //参数是一个数组
　　if (arr.length <= 1) { return arr; } //检查数组的元素个数，如果小于等于1，就返回。
　　var pivotIndex = Math.floor(arr.length / 2); //选择"基准"（pivot），并将其与原数组分离，再定义两个空数组，用来存放一左一右的两个子集。
　　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));
};

Realize the above animation:

Algorithm idea:

1. Select an element from the sequence, called the "pivot";

2. Reorder the array so that all elements smaller than the base value are placed in front of the base, and all elements larger than the base value are placed behind the base (the same number can go to either side). After the partition exits, the base is in the array The middle position. This is called a partition operation;

3. recursively sorts the subarray of elements smaller than the base value and the subarray of elements greater than the base value;

Implementation code:

function quickSort(arr, left, right) { 
　　var len = arr.length,
　　partitionIndex,
　　left = typeof left != 'number' ? 0 : left,
　　right = typeof right != 'number' ? len - 1 : right;
 
 
　　if (left < right) {
　　partitionIndex = partition(arr, left, right);
　　quickSort(arr, left, partitionIndex-1);
　　quickSort(arr, partitionIndex+1, right);
　　}
　　return arr;
}
function partition(arr, left ,right) { // 分区操作
　　var pivot = left,                // 设定基准值（pivot）
　　　　index = pivot + 1;
　　for (var i = index; i <= right; i++) {
　　　　if (arr[i] < arr[pivot]) {
　　　　　　swap(arr, i, index);
　　　　　　index++;
　　　　}
　　}
　　swap(arr, pivot, index - 1);
　　 return index-1;
}
 
function swap(arr, i, j) {
　　var temp = arr[i];
　　arr[i] = arr[j];
　　arr[j] = temp;
}
function partition2(arr, low, high) {
　　let pivot = arr[low];
　　while (low < high) {
　　　　while (low < high && arr[high] > pivot) {
　　　　--high;
　　　　}
　　　　arr[low] = arr[high];
　　　　while (low < high && arr[low] <= pivot) {
　　　　++low;
　　　　}
　　　　arr[high] = arr[low];
　　}
　　arr[low] = pivot;
　　return low;
}
 
function quickSort2(arr, low, high) {
　　if (low < high) {
　　let pivot = partition2(arr, low, high);
　　quickSort2(arr, low, pivot - 1);
　　quickSort2(arr, pivot + 1, high);
　　}
　　return arr;
}

The above is the entire content of this article. I hope it will be helpful to everyone’s study. For more related content, please pay attention to the PHP Chinese website!

Related recommendations:

How to randomly sort js arrays

js moves any element to a specified position

The above is the detailed content of Algorithmic ideas for implementing quick sort in JavaScript. For more information, please follow other related articles on the PHP Chinese website!