本文摘自PHP中文网,作者青灯夜游,侵删。
介绍
排序是指以特定顺序(数字或字母)排列线性表的元素。排序通常与搜索一起配合使用。
有许多排序算法,而迄今为止最快的算法之一是快速排序(Quicksort)。
快速排序用分治策略对给定的列表元素进行排序。这意味着算法将问题分解为子问题,直到子问题变得足够简单可以直接解决为止。
从算法上讲,这可以用递归或循环实现。但是对于这个问题,用递归法更为自然。
了解快速排序背后的逻辑
先看一下快速排序的工作原理:
- 在数组中选择一个元素,这个元素被称为基准(Pivot)。通常把数组中的第一个或最后一个元素作为基准。
- 然后,重新排列数组的元素,以使基准左侧的有元素都小于基准,而右侧的所有元素都大于基准。这一步称为分区。如果一个元素等于基准,那么在哪一侧都无关紧要。
- 针对基准的左侧和右侧分别重复这一过程,直到对数组完成排序。
接下来通过一个例子理解这些步骤。假设有一个含有未排序元素 [7, -2, 4, 1, 6, 5, 0, -4, 2]
的数组。选择最后一个元素作为基准。数组的分解步骤如下图所示:
在算法的步骤1中被选为基准的元素带颜色。分区后,基准元素始终处于数组中的正确位置。
黑色粗体边框的数组表示该特定递归分支结束时的样子,最后得到的数组只包含一个元素。
最后可以看到该算法的结果排序。
用 JavaScript 实现快速排序
这一算法的主干是“分区”步骤。无论用递归还是循环的方法,这个步骤都是一样的。
正是因为这个特点,首先编写为数组分区的代码 partition()
:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
代码以最后一个元素为基准,用变量 pivotIndex
来跟踪“中间”位置,这个位置左侧的所有元素都比 pivotValue
小,而右侧的元素都比 pivotValue
大。
最后一步把基准(最后一个元素)与 pivotIndex
交换。
递归实现
在实现了 partition()
函数之后,我们必须递归地解决这个问题,并应用分区逻辑以完成其余步骤:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
在这个函数中首先对数组进行分区,之后对左右两个子数组进行分区。只要这个函数收到一个不为空或有多个元素的数组,则将重复该过程。
空数组和仅包含一个元素的数组被视为已排序。
最后用下面的例子进行测试:
1 2 3 4 |
|
输出:
1 |
|
循环实现
快速排序的递归方法更加直观。但是用循环实现快速排序是一个相对常见的面试题。
与大多数的递归到循环的转换方案一样,最先想到的是用栈来模拟递归调用。这样做可以重用一些我们熟悉的递归逻辑,并在循环中使用。
我们需要一种跟踪剩下的未排序子数组的方法。一种方法是简单地把“成对”的元素保留在堆栈中,用来表示给定未排序子数组的 start
和 end
。
相关阅读 >>
javascript如何实现“全选”和"全不选"功能?(代码示例)
更多相关阅读请进入《前端》频道 >>
Vue.js 设计与实现 基于Vue.js 3 深入解析Vue.js 设计细节
本书对 Vue.js 3 技术细节的分析非常可靠,对于需要深入理解 Vue.js 3 的用户会有很大的帮助。——尤雨溪,Vue.js作者