利用js實現快速排序的方法

       快速排序，這也是實際中最常使用的排序演算法，速度快，效率高。就像名字一樣，快速排序是最優秀的一種排序演算法。

1）演算法原理

#     快速排序的基本想法：透過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

2）演算法描述

#     快速排序使用分治法將一串串（list）分成兩個子字串（sub-lists）。具體演算法說明如下：

    f35d6e602fd7d0f0edfa6f7d103c1b57 從數列中挑出一個元素，稱為"基準"（pivot）；

2cc198a1d5eb0d3eb508d858c9f5cbdb 重新排序序列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作；

    5bdf4c78156c7953567bb5a0aef2fc53 遞歸地（recursive）排序小於基準值元素的子數列和大於基準值元素的子數。

3）javascript程式碼實作

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）演算法分析

    最佳情況：T(n) = O(nlogn)
    最糟糕狀況：T (n) = O(n^2)
    平均情況：T(n) = O(nlogn)

十大演算法清單：

1.用JavaScript實作十大經典排序演算法--冒泡排序

2.用JavaScript實作十大經典排序演算法--選擇排序

3.用JavaScript實作十大經典排序演算法--插入排序

#

以上是利用js實現快速排序的方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！