快速选择
在计算机科学中，快速选择（）是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的，因而也被称为霍尔选择算法。 同样地，它在实际应用是一种高效的算法，具有很好的平均时间复杂度，然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。 快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。不同的…
标签：#选择算法
共 3 篇文章
顺序统计树
在计算机科学，顺序统计树（）是二叉搜索树的变种。除了插入、查询和删除，这种数据结构还支持以下两种操作： Select(i) — 在树中查询第i小的元素 Rank(x) – 查找元素x的排名 这两种操作的平均时间复杂度是O(\log n)。当所用数据结构是平衡二叉树时，这是最坏复杂度。 算法实现 对于树中的每个节点，需要额外维护以这个节点为根的子树大小（该节点下点的个数）。 size[x] = size[left[x]] + size[r…
选择算法
在计算机科学中，选择算法是一种在列表或数组中找到第k个最小数字的算法；这样的数字被称为第k个顺序统计量。该算法寻找的对象主要有三种：最小、最大和中位数。已知存在O(n)（最坏情况下为线性时间）的选择算法，还有对于结构化数据可能有次线性的表现的算法；在极端的情况下，对于已排序数据是O(1)。选择是一些更复杂问题的子问题，如最近邻和最短路径问题。 许多选择算法是由排序算法推广而来，反之，一些排序算法可由反复应用选择算法推导出来。 最简单的选…