使用修改后的快速排序查找元素的秩

Question

我想找出一个元素的排名，排名的定义是k，也就是说在一个无序的列表中，排名就是列表中第k个最小的值。

比如说，给定一个列表：

[5,4,1,10,8,3,2]

当k是1时，值是1；

当k是3时，值是3；

当k是6时，值是8；

当k是7时，值是10。

我需要使用下面提供的一个修改过的快速排序分区函数。

def partition(a_list, first, last):

    pivot = a_list[last]
    i = first - 1
    for j in range(first, last):
        if a_list[j] <= pivot:
            i += 1
            a_list[i], a_list[j] = a_list[j], a_list[i]

    a_list[i + 1], a_list[last] = a_list[last], a_list[i + 1]

    return i + 1

我希望这个函数的运行时间是O(n)。我想通过递归的方式在列表中导航，调用分区函数，然后决定是继续查看右半部分还是左半部分，但我在得到预期结果时遇到了困难。这是我的选择方法。

def selection(a_list, first, last, k):
    intReturn = partition(a_list, first, last)
    print(a_list)
    print(intReturn)
    if intReturn == k:
        return a_list[intReturn - 1]
    else:
        if intReturn < k:
            return selection(a_list, first + intReturn, last, k) #- (first + intReturn))
        elif intReturn > k:
            return a_list[k]
            #return selection(a_list, first, last - intReturn, k)

选择函数应该这样调用：

print(selection([5,4,1,10,8,3,2], 0, 6, 1))
print(selection([5,4,1,10,8,3,2], 0, 6, 3))
print(selection([5,4,1,10,8,3,2], 0, 6, 6))
print(selection([5,4,1,10,8,3,2], 0, 6, 7))
print(selection([46, 50, 16, 88, 79, 77, 17, 2, 43, 13, 86, 12, 68, 33, 81, \
74, 19, 52, 98, 70, 61, 71, 93, 5, 55], 0, 24, 19))

所以，我该如何在预期的运行时间O(n)内递归查找一个特定排名的元素，而不需要对整个列表进行排序，同时又要限制在这种特定的分区方式下呢？

Answer 1

Python的食谱里至少有两个详细的例子，分别可以在这里和这里找到。

这是我自己的版本：

import random

def select(data, n):
    "Find the nth rank ordered element (the least value has rank 0)."
    data = list(data)
    if not 0 <= n < len(data):
        raise ValueError('not enough elements for the given rank')
    while True:
        pivot = random.choice(data)
        pcount = 0
        under, over = [], []
        uappend, oappend = under.append, over.append
        for elem in data:
            if elem < pivot:
                uappend(elem)
            elif elem > pivot:
                oappend(elem)
            else:
                pcount += 1
        if n < len(under):
            data = under
        elif n < len(under) + pcount:
            return pivot
        else:
            data = over
            n -= len(under) + pcount

根据你的要求，这里是同样代码的递归版本：

def select(data, n):
    "Find the nth rank ordered element (the least value has rank 0)."
    if not 0 <= n < len(data):
        raise ValueError('not enough elements for the given rank')
    pivot = random.choice(data)
    pcount = 0
    under, over = [], []
    uappend, oappend = under.append, over.append
    for elem in data:
        if elem < pivot:
            uappend(elem)
        elif elem > pivot:
            oappend(elem)
        else:
            pcount += 1
    if n < len(under):
        return select(under, n)
    elif n < len(under) + pcount:
        return pivot
    else:
        return select(over, n - len(under) - pcount)

Answer 2

试试这个？有一个观察可能会对你有帮助，那就是分区函数会返回基准元素的索引（从零开始计数）。

def selection(a_list, first, last, k):
    assert (k - 1 >= first)
    assert (k - 1 <= last)
    intReturn = partition(a_list, first, last)

    if intReturn + 1 == k:
         return a_list[intReturn]

    if intReturn + 1 < k:
        return selection(a_list, intReturn + 1, last, k)

    if intReturn + 1 > k:
        return selection(a_list, first, intReturn - 1, k)