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教程: