算法导论之js实现--快速选择
更新日期:
快速选择(Quick-Select)的javascript实现。
快速选择
问题
- 输入:n个数的一个序列
<a1, a2, ..., an>
- 输出:找到第k个最小数字的元素
快速选择
快速选择(Quickselect)是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。
快速选择的总体思路与快速排序一致,选择一个元素作为基准来对元素进行分区,将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是,快速选择并不递归访问双边,而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度,从O(n log n)
至O(n)
,不过最坏情况仍然是O(n2)
。
与快速排序一样,快速选择一般是以原地算法的方式实现,除了选出第k小的元素,数据也得到了部分地排序。
思路
- 从数列中挑出一个元素,称为”基准”(pivot)。
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。
- 判断第k个最小元素位于左侧还是右侧,然后对该侧进行递归。
js基本思路实现
1 | // 交换数组值 |
码生艰难,写文不易,给我家猪囤点猫粮了喵~
查看Github有更多内容噢:https://github.com/godbasin
更欢迎来被删的前端游乐场边撸猫边学前端噢
如果你想要关注日常生活中的我,欢迎关注“牧羊的猪”公众号噢