/

JavaScript演算法：快速排序

JavaScript演算法：快速排序

快速排序是比選擇排序更有效率的搜尋演算法，它利用了遞迴的概念。

遞迴表示我們在同一函式中呼叫了該函式本身。這是一種非常有用的技巧，在某些情況下很適用，而這正是其中之一。

我說“在大多數情況下”，是因為正如我們將看到的，最壞的情況下，泡沫排序所需要的時間可能與選擇排序相同：O(n^2)。但在最佳情況下，它的運行時間會是O(n log n)，落在O(n)和O(n^2)之間。

它是如何運作的呢？給定一個數組，我們選擇一個項目作為主軸。然後將比主軸小的項目和比主軸大的項目分開。

接著我們對組成比主軸小和比主軸大的項目的兩個數組進行相同的操作。

通過代碼來看會更容易理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const quickSort = (originalList) => {
  const list = [...originalList]

  if (list.length < 2) {
    return list
  }

  const pivot = list[0]

  const smaller = list.filter((item) => item < pivot)
  const bigger = list.filter((item) => item > pivot)

  return [...quickSort(smaller), pivot, ...quickSort(bigger)]
}

在這個例子中，我選擇將主軸設置為數組中的第一個項目，但也可以選擇中間的項目，例如：

1
const pivot = list[Math.floor(list.length / 2)]

注意我們首先複製了數組，所以調用quickSort()不會修改原始數組，它只會返回一個新的排序過的數組：

1
2
3
4
5
6
7
const a = [1, 6, 3, 4, 5, 1, 0, 4, 8]

console.log(quickSort(a))
//[0, 1, 1, 3, 4, 4, 5, 6, 8]

console.log(a)
//[1, 6, 3, 4, 5, 1, 0, 4, 8]

tags: [“javascript”, “algorithms”, “sorting”, “quicksort”]