我必须将数组的元素分成 3 组。这需要在不对数组进行排序的情况下完成。考虑示例
我们有 120 个未排序的值，因此最小的
40 个值需要在第一组中，接下来的 40 个值需要在第二组中，最大的 40 个值需要在第三组中我在想中位数方法的中位数，但无法将其应用于我的问题，请建议一种算法。
您可以在数组上调用快速选择两次，以就地和平均情况下线性时间执行此操作。通过使用中位数的线性时间中位数算法为快速选择选择最佳枢轴，也可以将最坏情况运行时间提高到 O（n）。
对于快速选择的两个调用，请使用 k = n/3。在第一次调用时，对整个阵列使用快速选择，在第二次调用时，从 arr[k..n-1]（对于 0 索引数组）。
维基百科对快速选择的解释：
快速选择使用与快速排序相同的整体方法，选择一个 元素作为透视，并根据 枢轴，相应地小于或大于枢轴。然而 而不是像快速排序那样递归到两侧，快速选择 仅递归到一侧 – 具有元素的一侧 搜索。这降低了平均复杂度从 O（n log n） （在 快速排序）到 O（n）（在快速选择中）。
与快速排序一样，快速选择通常作为就地实现 算法，除了选择第 k 个元素之外，它还部分 对数据进行排序。有关 与排序的连接。
要将数组的元素分为 3 组，请使用以下用 Python 编写的算法和快速选择：
k = n / 3
# First group smallest elements in array
quickselect(L, 0, n - 1, k) # Call quickselect on your entire array
# Then group middle elements in array
quickselect(L, k, n - 1, k) # Call quickselect on subarray
# Largest elements in array are already grouped so
# there is no need to call quickselect again
所有这一切的关键点是快速选择使用称为分区的子例程。分区将数组排列成两部分，大于给定元素的部分和小于给定元素的部分。因此，它围绕此元素对数组进行部分排序，并返回其新的排序位置。因此，通过使用快速选择，您实际上可以就地和平均情况下线性时间围绕第 k 个元素对数组进行部分排序（请注意，这与实际对整个数组进行排序不同）。
快速选择的时间复杂度：
- 最坏情况性能 O（n2）
- 最佳情况性能 O（n）
- 平均案例表现 O（n）
而不是二次的，但这取决于这样一个事实，即对于大多数数组，简单地选择一个随机枢轴点几乎总是会产生线性运行时。但是，如果要提高快速选择的最坏情况性能，可以选择在每次调用之前使用中位数算法来近似用于快速选择的最佳枢轴。这样，您将快速选择算法的最坏情况性能提高到 O（n）。这种开销可能不是必需的，但如果您正在处理大型随机整数列表，它可以防止算法的一些异常二次运行时。
下面是 Python 中一个完整的示例，它实现了快速选择并将其应用于 120 个整数的反向排序列表两次，并打印出三个结果子列表。
from random import randint
def partition(L, left, right, pivotIndex):
'''partition L so it's ordered around L[pivotIndex]
also return its new sorted position in array'''
pivotValue = L[pivotIndex]
L[pivotIndex], L[right] = L[right], L[pivotIndex]
storeIndex = left
for i in xrange(left, right):
if L[i] < pivotValue:
L[storeIndex], L[i] = L[i], L[storeIndex]
storeIndex = storeIndex + 1
L[right], L[storeIndex] = L[storeIndex], L[right]
return storeIndex
def quickselect(L, left, right, k):
'''retrieve kth smallest element of L[left..right] inclusive
additionally partition L so that it's ordered around kth
smallest element'''
if left == right:
return L[left]
# Randomly choose pivot and partition around it
pivotIndex = randint(left, right)
pivotNewIndex = partition(L, left, right, pivotIndex)
pivotDist = pivotNewIndex - left + 1
if pivotDist == k:
return L[pivotNewIndex]
elif k < pivotDist:
return quickselect(L, left, pivotNewIndex - 1, k)
else:
return quickselect(L, pivotNewIndex + 1, right, k - pivotDist)
def main():
# Setup array of 120 elements [120..1]
n = 120
L = range(n, 0, -1)
k = n / 3
# First group smallest elements in array
quickselect(L, 0, n - 1, k) # Call quickselect on your entire array
# Then group middle elements in array
quickselect(L, k, n - 1, k) # Call quickselect on subarray
# Largest elements in array are already grouped so
# there is no need to call quickselect again
print L[:k], 'n'
print L[k:k*2], 'n'
print L[k*2:]
if __name__ == '__main__':
main()
我会看看订单统计。统计样本的第 k 阶统计量等于其第 k 个最小值。计算列表中第 k 个最小（或最大）元素的问题称为选择问题，由选择算法解决。
以中位数的方式思考是正确的。但是，您可能希望从数组中查找第 20 个和第 40 个最小元素，而不是查找中位数。就像找到中位数一样，使用选择算法只需线性时间即可找到两者。最后，您遍历数组并根据这两个元素对元素进行分区，这也是线性时间。
附言。如果这是您在算法课上的练习，这可能有助于您:)
分配与输入数组大小相同的数组扫描输入数组一次，并跟踪数组的最小值和最大值。同时将第二个数组的所有值设置为 1。计算delta = (max - min) / 3 .再次扫描阵列，如果数字> min+delta and < max-delta，则将第二个数组设置为 2 ;否则if >= max-delta，将其设置为 3;结果，您将拥有一个数组，该数组告诉数字在哪个组中。我假设所有数字都彼此不同。复杂度：O(2n)