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初学者手册

JavaScript算法：Quicksort

更多js教程：