具有QuickSelect风格的QuickSort算法

Question

我试图对最优算法进行编码，以选择列表中越大的ith元素。例如，如果数组= 4、3、5、7和我搜索第二个数组，则函数将返回4。

，我假设列表在这里只有不同的数字，

以下是问题所在：

该函数有时不返回任何内容。

下面是我的代码(我认为第一个函数工作得很好)。

from random import shuffle

def partition(array, leftend, rightend, pivot):
    """ I tested this one and it should work fine """
    i = leftend
    pivotindex = array.index(pivot)  # only works if all values in array unique
    array[pivotindex] = array[leftend]
    array[leftend] = pivot
    for j in range(leftend+1, rightend):
        if array[j] < pivot:
            temp = array[j]
            array[j] = array[i]
            array[i] = temp
            i += 1
    pivotindex = array.index(pivot)  # only works if all values in array unique
    leftendval = array[pivotindex]   # Take the value of the pivot
    array[pivotindex] = array[i]
    array[i] = leftendval
    return array

def RSelect(array, n, statistic_order):
    """ list * int * int
        statistic_order = the i th element i'm searching for """
    new_array = []                  # is used at the end of the function
    if n == 1:
        return array[0]
    array_temp = array              # Allows to have a shuffled list and
    shuffle(array_temp)
    pivot = array_temp[0]           # Allows to have a random pivot
    partition(array,0,n,pivot)
    j = array.index(pivot)


    if j == statistic_order:
        return pivot


    elif j > statistic_order:
        for k in range(0,j):
            new_array.append(array[k])
        RSelect(new_array,j,statistic_order)


    elif j < statistic_order:
        for k in range(j+1,n):
            new_array.append(array[k])
        RSelect(new_array,(n-j)-1,statistic_order-j)

Answer 1

有几件事是错的：

• 在每种情况下，您都需要返回递归方法的结果！
• 当j < statistic_order时，递归地处理数组的右侧，并且丢弃j+1数，而不是j。记住索引从python的0开始，而不是1！

我还更改了一些东西，比如无用的参数，或者可以用片编写的循环。

这是最后的代码，检查更改以确保您理解它。

RSelect：

def RSelect(array, statistic_order):
    """ list * int * int
    statistic_order = the i th element i'm searching for """
    n = len(array)
    if n == 1:
        return array[0]
    array_temp = array              # Allows to have a shuffled list and
    shuffle(array_temp)
    pivot = array_temp[0]           # Allows to have a random pivot
    array = partition(array,0,n,pivot)  # Changes here, does not impact the result, but for readability
    j = array.index(pivot)

    # print(array, j, statistic_order, end = '\t')
    if j == statistic_order:
        return pivot

    elif j > statistic_order:
        assert j > 0
        # print((array[0:j]), pivot)
        return RSelect(array[0:j],statistic_order)  # Changes here : return

    elif j < statistic_order:
        assert j+1 < n
        # print(pivot, (array[j+1:n]))
        return RSelect(array[j+1:n],statistic_order-j-1)  # Changes here : return, -j-1

主要：

if __name__ == "__main__":
    from sys import argv
    if len(argv) > 1:
       n = int(argv[1])
    arr = [2, 1, 3, 5, 4]
    print(RSelect(arr[:], n))

为此目的，它在O(n)中也存在另一种算法:参见这

编辑:更正和更正有关复杂性的打字

Answer 2

代码运行良好，但结果从0开始。例如，如果arr = 2, 3 ,5,6并且我要求RSelect(arr,4,2)，答案将是5，而不是3，我不知道为什么。

下面是更新的代码：

from random import shuffle

def partition(array, leftend, rightend, pivot):
    i = leftend
    pivotindex = array.index(pivot)  # only works if all values in array unique
    array[pivotindex] = array[leftend]
    array[leftend] = pivot
    for j in range(leftend+1, rightend):
        if array[j] < pivot:
            temp = array[j]
            array[j] = array[i]
            array[i] = temp
            i += 1
    pivotindex = array.index(pivot)  # only works if all values in array unique
    leftendval = array[pivotindex]   # Take the value of the pivot
    array[pivotindex] = array[i]
    array[i] = leftendval


def RSelect(array, n, statistic_order):
    """ list * int * int
        statistic_order = the i th element i'm searching for """
    if n == 1:
        return array[0]

    array_temp = array              # Allows to have a shuffled list
    shuffle(array_temp)
    pivot = array_temp[0]           # Allows to have a random pivot
    partition(array,0,n,pivot)
    j = array.index(pivot)


    if j == statistic_order:
        return pivot


    elif j > statistic_order:
        return RSelect(array[0:j],j,statistic_order)


    elif j < statistic_order:
        return RSelect(array[j+1:n],(n-j)-1,statistic_order-j-1)