[演算法] 快速排序法 (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),可看出是最快排序完成的。

您可在此處留言

avatar

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

  Subscribe  
Notify of