JavaScript中的快速排序詳解

這篇文章講述了JavaScript中的快速排序，大家對JavaScript中的快速排序不了解的話或者對JavaScript中的快速排序感興趣的話那麼我們就一起來看看本篇文章吧， 好了廢話少說進入正題吧

快速排序又是一種分而治之思想在排序演算法上的典型應用。基本上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。

快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高! 它是處理大數據最快的排序演算法之一了。雖然Worst Case的時間複雜度達到了O(n²)，但是人家就是優秀，在大多數情況下都比平均時間複雜度為O(n log n) 的排序演算法表現要更好，可是這是為什麼呢，我也不知道。 。 。還好我的強迫症又犯了，查了N多資料終於在《演算法藝術與資訊學競賽》上找到了滿意的答案：

快速排序的最壞運作情況是O(n²) ，比如說順序數列的快排。但它的平攤期望時間是O(n log n) ，且O(n log n)記號中隱含的常數因子很小，比複雜度穩定等於O(n log n)的歸併排序要小得多。所以，對絕大多數順序性較弱的隨機數列而言，快速排序總是優於歸併排序。

快速排序動圖示範

快速排序JavaScript程式碼實作：

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

以上就是這篇文章的所有內容，大家要是還不太了解的話，可以自己多實現兩邊就很容易掌握了哦！

相關推薦：

Js冒泡排序與快速排序實詳解

#

以上是JavaScript中的快速排序詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！