将数组的元素分为3组

Question

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

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

我正在考虑中位数方法的中位数但不能将其应用于我的问题,请提出一个算法.

Answer 1

您可以在阵列上调用两次quickselect来就地执行此操作,并在平均情况下执行线性时间.通过使用中位数算法的线性时间中位数来选择最佳的快速选择枢轴,最坏情况运行时也可以改进为O(n).

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

维基百科对quickselect的解释:

Quickselect使用与快速排序相同的整体方法,选择一个元素作为数据透视表,并根据数据透视表将数据分成两部分,因此小于或大于数据透视表.但是,不要像在快速排序中那样递归到双方,而是快速选择仅向一侧递归 - 与正在搜索的元素的一侧.这将平均复杂度从O(n log n)(在快速排序中)降低到O(n)(在quickselect中).

与quicksort一样,quickselect通常作为就地算法实现,除了选择第k个元素之外,它还对数据进行部分排序.有关与排序的连接的进一步讨论,请参阅选择算法.

要将数组的元素分成3组,请使用以下用Python编写的算法结合quickselect:

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使用一个称为分区的子程序.分区将数组排列成两部分,一部分大于给定元素,另一部分小于给定元素.因此,它会对此元素周围的数组进行部分排序,并返回其新的排序位置.因此,通过使用quickselect,您实际上对kth元素周围的数组进行了部分排序(请注意,这与实际排序整个数组不同)就地和平均情况下的线性时间.

快速选择的时间复杂度:

1. 最差情况表现O(n ²)
2. 最佳案例表现O(n)
3. 平均案例表现O(n)

quickselect的运行时间几乎总是线性的而不是二次的,但这取决于对于大多数数组而言,简单地选择随机轴点几乎总会产生线性运行时.但是,如果要改善快速选择的最坏情况性能,可以选择在每次调用之前使用中位数算法算法来近似用于快速选择的最佳枢轴.这样,您可以将quickselect算法的最差情况性能提高到O(n).这个开销可能不是必需的,但如果你正在处理大型随机整数列表,它可以防止算法的一些异常二次运行时间.

这是Python中的一个完整示例,它实现了quickselect并将其两次应用于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()