JavaScript算法:Quicksort

快速排序是比以下方法更有效的搜索算法選擇排序大多數情況下,並且利用了遞歸。

遞歸意味著我們從同一個函數中調用一個函數。有時,這是一種非常有用的做法,這是其中一種情況。

我說“在大多數情況下”是因為,正如我們將看到的,在最壞的情況下,冒泡排序可能需要選擇排序的時間:O(n^2)。但在最佳情況下,它將以O(n log n),介於兩者之間O(n)O(n^2)

它是如何工作的?給定一個數組,我們選擇一個項目,稱為。然後,我們得到所有小於樞軸的項目,以及大於樞軸的項目。

然後,我們在組成越來越小的項目的2數組上運行相同的操作。

看代碼比描述代碼要容易得多:

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)] }

在這種情況下,我選擇了數據透視表作為數組中的第一項,但也可以將其作為中間的項,例如:

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

注意我們如何首先複製數組,因此調用quickSort()不會修改原始數組,它只會返回一個新的排序數組:

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]

免費下載我的JavaScript初學者手冊


更多js教程: