[演算法] 快速排序法 (Quicksort)

解決問題的方法：各個擊破法，即稱為 Divide-and-Conquer，是一種知名度很高的遞迴技術；而當中最重要的一個就是快速排序法(Quicksort)，演算速度比 選擇排序法(Selection Sort) 快很多，快速排序法是目前最快的排序演算法之一。

 實作原理

基本情況：當一個陣列是空陣列或只有一個元素的陣列，則不需要排序，直接回傳即可，例：[]、[5]。

一般情況：當陣列的元素大於等於2的時候，就要進行排序。而排序的規則如下：

• 以該陣列的第一個元素為基準值
• 由所有小於等於基準值的數字組成的子陣列
• 由所有大於基準值的數字組成的子陣列

最後將上述三點所形成的各陣列合併起來，並搭配遞迴演算法的原理回傳即可。

Node.js code

轉換成 JS 程式碼的話，如下：

var quick_sort = function(arr){
  if (arr.length < 2)
    return arr
  else
    var middle_value = arr[0]
    var left_arr = []
    var right_arr = []
    arr.forEach(function(value, index) {
      if(index >= 1){
        if(value <= middle_value){
          left_arr.push(value)
        }else{
          right_arr.push(value)
        }
      }
    });
    return ((quick_sort(left_arr)).concat([middle_value])).concat(quick_sort(right_arr))
}

實際比較

以下影片的中間，就是 快速排序法(quicksort)，可看出是最快排序完成的。