Python如何解决基准计数排序的最大值要求

Question

我一直在尝试对一些不同类型的问题进行基准测试，并解决了大部分问题，但事实证明，计数排序是很尴尬的。我在哪里给它一个最大值？

我尝试过几种不同的方法，但是

def counting_sort(arr，maxval)：

n = len(arr)
m = maxval + 1
count = [0] * m               
for a in arr:
    count[a] += 1             
i = 0
for a in range(m):           
    for c in range(count[a]): # - emit 'count[a]' copies of 'a'
        arr[i] = a
        i += 1
return arr

给出了错误TypeError: counting_sort()缺少一个必需的位置参数：'maxval‘

所以我想我应该尝试一种没有在一开始就调用最大值的方法

    arr = []
    for i in range(0, n, 1):
        arr.append(randint(0, 100))
    return arr

def counting_sort(arr):
    size = len(arr)
    output = [0] * size

    # Initialize count array
    count = [0] * 10

    # Store the count of each elements in count array
    for i in range(0, size):
        count[arr[i]] += 1

    # Store the cummulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Find the index of each element of the original array in count array
    # place the elements in output array
    i = size - 1
    while i >= 0:
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
        i -= 1

    # Copy the sorted elements into original array
    for i in range(0, size):
        arr[i] = output[i]

    return arr

num_runs = 10
elements = [100, 250, 500, 750, 1000, 1250, 2500, 3750, 5000]
def countrunTime():    

    stimes = []    
    for i in elements:
        arr = random_array(i)
        countresults = []
        for r in range(num_runs):

            start_time = time.time()

            counting_sort(arr)

            end_time = time.time()

            time_elapsed = end_time - start_time
            countresults.append(time_elapsed)
        s = round(mean(countresults),3)
        stimes.append(s)
    return stimes

Returns the error in counting_sort
    count[arr[i]] += 1
IndexError: list index out of range

Answer 1

如果不为参数提供默认值，则不能在不提供方法的情况下调用该方法。

def counting_sort(arr, maxval):
    pass

counting_sort([])  # Will fail
counting_sort([], 123)  # Will work

不过，我建议计算maxval。

def counting_sort(arr):
    maxval = max(array)
    # ...

对于第二个错误，您试图访问大于count数组长度的索引。我认为您将受益于从pythons使用collections.Counter。

from collections import Counter
counter = Counter()
for value in arr:
   counter[value] += 1
print(counter)

collections.Counter不需要对大小进行初始化，并且它为任何未更改的值报告0。

额外提示:您的许多代码将受益于Pythons理解(初学者指南)。相信我，他们真的值得我们努力学习。