快速排序法（Quick-sort）

一樣是大腦懂，但程式碼抽象QQ。

概念

先選定一個數字當基準點，接著把剩下的數列分組，比基準點「小的放左邊」，「大的放右邊」。

接著利用「遞迴」的概念，把好分組的數列再重複一次剛剛的步驟，直到剩下「空元素或一個元素為止」

流程圖：

實作

function quickSort(arr) {
  // 停止點，當 arr 長度為 1 或沒有元素了
  if (arr.length <= 1) {
    return arr
  }

  // 基準點 index
  const pivotIndex = Math.floor(arr.length / 2)
  // 基準點 number
  const pivotNumber = arr.splice(pivotIndex, 1)[0]
  // 比基準點小的數列
  let samllerNumbers = []
  // 比基準點大的數列
  let biggerNumbers = []

  // 把小的放到 samll，大的放到 bigger
  for (let i=0; i<arr.length; i++) {
    if (arr[i] < pivotNumber) {
      samllerNumbers.push(arr[i])
    } else {
      biggerNumbers.push(arr[i])
    }
  }
  // 把小的跟大的都丟到 quickSort 遞迴，最後要跟 pivot 結合起來
  return quickSort(samllerNumbers).concat([pivotNumber], quickSort(biggerNumbers))

}
const numbers = [5, 44, 23, 3, 42, 4, 2]
console.log(quickSort(numbers))

詳細流程：

// 拆解流程
pivotNumber: 3
samllerNumbers: [ 2 ]
biggerNumbers: [ 5, 44, 23, 42, 4 ]

pivotNumber: 23
samllerNumbers: [ 5, 4 ]
biggerNumbers: [ 44, 42 ]

pivotNumber: 4
samllerNumbers: []
biggerNumbers: [ 5 ]

pivotNumber: 42
samllerNumbers: []
biggerNumbers: [ 44 ]

// 接下來要 return 回去
pivotNumber: 42
return [].concat([ 42 ], [ 44 ]) => [ 42, 44 ] => [ 42, 44 ]

pivotNumber: 4
return [ ].concat([ 4 ], [ 5 ]) => [ 4, 5 ]

pivotNumber: 23
return [ 4, 5 ].concat([ 23 ], [ 42, 44 ]) => [ 4, 5, 23, 42, 44 ]

pivotNumber: 3
return [ 2 ].concat([ 3 ], [ 4, 5, 23, 42, 44 ]) => [ 2, 3, 4, 5, 23, 42, 44 ]

result：[2,  3,  4, 5, 23, 42, 44]

或者參考下面的圖：

結語

上面的做法其實不是最好的寫法，但優點是可讀性比較好。

等未來比較理解一點後可以參考：這篇

第二種作法

遞迴的部分看不太懂是怎麼遞迴的，所以先暫時放在這裡：

// 換位置
function swap(array, i, j) {
  let temp = array[i]
  array[i] = array[j]
  array[j] = temp
}
/*
  array = 數列
  start = 搜索起點
  end = 搜索終點
*/
function divide(array, start, end) {
  // pivot = 最後一個數字
  const pivot = array[end-1]
  // 指標初始值（起點的前一個位置）
  let index = start - 1

  // 遍歷數列
  for (let i=start; i<end-1; i++) {
    // 數字比 pivot 小
    if (array[i] < pivot) {
      // 先把 index 往右移
      index++
      // 在把數字放到 index 的位置
      swap(array, i, index)
    }
  }


  /*
    更新 pivot 的位置
    end-1: pivot 原本的位置
    index+1: pivot 該放到的位置
  */
  swap(array, index+1, end-1)
  

  // 回傳最後 pivot 的位置
  return index+1
}
function quickSort(array, start, end) {
  // 設定搜尋終點初始值
  end = end || array.length
  if (start < end-1) {
    // 最後 pivot 的位置
    const lastPivotPosition = divide(array, start, end)
    // 遞迴左半邊的數列（比 pivot 小的）
    quickSort(array, start, lastPivotPosition)
    // 遞迴右半邊的數列（比 pivot 大的）
    quickSort(array, lastPivotPosition+1, end)
  }
  return array
}
const numbers = [15, 12, 3, 2, 7]
quickSort(numbers, 0, numbers.length)
console.log(numbers)