Detailed explanation of quick sort in JavaScript

This article talks about quick sorting in JavaScript. If you don’t know about quick sorting in JavaScript or are interested in quick sorting in JavaScript, then let’s take a look at this article. Well, let’s cut the nonsense and get to the point

Quick sort is another typical application of the divide-and-conquer idea in sorting algorithms. In essence, quick sort should be regarded as a recursivedivide and conquer method based on bubble sort.

The name of quick sort is simple and crude, because as soon as you hear this name, you will know the meaning of its existence, which is fast and efficient! It is one of the fastest sorting algorithms for processing big data. . Although the time complexity of Worst Case has reached O(n²), it is excellent and in most cases performs better than the sorting algorithm with an average time complexity of O(n log n). But why is this? ,I don't know either. . . Fortunately, my obsessive-compulsive disorder recurred. After checking a lot of information, I finally found a satisfactory answer on the "Algorithm Art and Informatics Competition":

The worst operating situation of quick sort is O(n²) , such as quick sorting of sequential numbers. But its amortized expected time is O(n log n), and the constant factor implicit in the O(n log n) notation is very small, which is much smaller than the merge sort whose complexity is stable and equal to O(n log n). Therefore, for most random number sequences with weak order, quick sort is always better than merge sort.

Quick sort animation demonstration

Quick sort JavaScript code implementation:

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;}

The above is all the content of this article, if you If you don’t know much about it yet, you can easily master it if you can implement both sides yourself!

Related recommendations:

Js bubble sort and quick sort detailed explanation

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