How to implement quick sort using js

Quick sort, which is also the most commonly used sorting algorithm in practice, is fast and efficient. Just like the name, quick sort is the best sorting algorithm.

1) Algorithm principle

The basic idea of ​​quick sorting: sorting through one pass Separate the records to be sorted into two independent parts. The keywords of one part of the record are smaller than the keywords of the other part. Then you can continue to sort the two parts of the records separately to achieve the ordering of the entire sequence.

2) Algorithm description

Quick sort uses the divide-and-conquer method to divide a string (list) into two Sub-lists. The specific algorithm is described as follows:

f35d6e602fd7d0f0edfa6f7d103c1b57 Pick an element from the sequence, called the "pivot";

2cc198a1d5eb0d3eb508d858c9f5cbdb 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 be placed on either side). After this partition exits, the base is in the middle of the sequence. This is called a partition operation;

5bdf4c78156c7953567bb5a0aef2fc53 Recursively sort the subarray of elements smaller than the base value and the subarray of elements greater than the base value.

3) JavaScript code implementation

##

function paritition(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 quickSort(arr, low, high) {
  if (low < high) {
    let pivot = paritition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
  }
  return arr;
}
  var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];    
  console.log(quickSort(arr,0,arr.length-1));

4) Algorithm analysis

Best case: T(n) = O(nlogn) Worst case: T (n) = O(n^2)
Average case: T(n) = O(nlogn)

Top ten algorithm list:

1. Use JavaScript to implement the top ten classic sorting algorithms-bubble sort

2.Use JavaScript to implement the top ten classic sorting algorithms-selection sort

3.Use JavaScript to implement the top ten Classic sorting algorithm--Insertion sort

The above is the detailed content of How to implement quick sort using js. For more information, please follow other related articles on the PHP Chinese website!