时间戳

首页 > 解决方案 > 具有 QuickSort 风格的 QuickSelect 算法

python - 具有 QuickSort 风格的 QuickSelect 算法

问题描述

我正在尝试编写最佳算法来选择列表中较大的第 i 个元素。例如，如果 array = [4,3,5,7] 并且我搜索第二个，该函数将返回 4。

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

这是问题所在：

该函数有时会返回 None。

这是我的代码（我认为第一个函数运行良好）。

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)

标签： pythonalgorithmquickselect

解决方案

代码工作正常，但结果仍然从 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)

推荐阅读