algorithm - 将数组的元素分成 3 组

Question

我必须将数组的元素分成 3 组。这需要在不对数组进行排序的情况下完成。考虑这个例子

我们有 120 个未排序的值，因此最小的 40 个值需要在第一组中，接下来的 40 个值在第二组中，最大的 40 个值在第三组中

我正在考虑中位数方法的中位数，但无法将其应用于我的问题，请推荐一种算法。

Answer 1

您可以调用quickselect在您的阵列上执行两次以就地执行此操作，并且在平均情况下是线性时间。通过使用线性时间 median of medians algorithm 也可以将最坏情况下的运行时间改进为 O(n)为快速选择选择最佳枢轴。

对于 quickselect 的两次调用，都使用 k = n/3。在第一次调用时，对整个数组使用 quickselect，在第二次调用时，从 arr[k..n-1] 使用它(对于 0 -索引数组)。

维基百科对quickselect的解释:

Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for. This reduces the average complexity from O(n log n) (in quicksort) to O(n) (in quickselect).

As with quicksort, quickselect is generally implemented as an in-place algorithm, and beyond selecting the kth element, it also partially sorts the data. See selection algorithm for further discussion of the connection with sorting.

要将数组的元素分成 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

这一切的关键点是quickselect使用了一个叫做partition的子程序。分区将数组分为两部分，大于给定元素的部分和小于给定元素的部分。因此，它围绕该元素对数组进行部分排序，并返回其新的排序位置。因此，通过使用 quickselect，您实际上是围绕第 k 个元素对数组进行部分排序(请注意，这与实际排序整个数组不同)就地和平均情况下的线性时间。

快速选择的时间复杂度:

1. 最坏情况下的性能 O(n²)
2. 最佳情况下性能 O(n)
3. 平均案例表现 O(n)

quickselect 的运行时间几乎总是线性的而不是二次的，但这取决于这样一个事实，即对于大多数数组，简单地选择一个随机的轴心点几乎总是会产生线性运行时间。但是，如果您想提高快速选择的最坏情况下的性能，您可以选择使用 median of medians algorithm在每次调用以近似用于快速选择的最佳枢轴之前。这样做，您会将快速选择算法的最坏情况性能提高到 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()