python - 如何实现可用于负数的CountingSort？

我在Python中有一个计数排序算法的以下实现，但它不适用于包含负数的数组有人能帮我吗？

def counting(nlist):
    nlist = list(nlist)
    size = len(nlist)

    if size < 2:
        return nlist

    k = max(nlist)

    counter = [0] * ( k + 1 )

    for i in nlist:
        counter[i] += 1

    ndx = 0;
    for i in range( len( counter ) ):
        while 0 < counter[i]:
           nlist[ndx] = i
           ndx += 1
           counter[i] -= 1

   return nlist

最佳答案

一个简单的方法就是找到最小值并用该值偏移索引，这样最小值就存储在counter的数组索引0中然后在while循环中，重新添加最小值以获取原始值：

m = min(nlist)
k = max(nlist) - m

counter = [0] * ( k + 1 )

for i in nlist:
    counter[i-m] += 1

ndx = 0;
for i in range( len( counter ) ):
    while 0 < counter[i]:
       nlist[ndx] = i+m
       ndx += 1
       counter[i] -= 1

关于python - 如何实现可用于负数的CountingSort？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41324974/