我如何实现与负数合作的CountingSort

Question

我在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

Answer 1

一种简单的方法只是为了找到最小值并将您的索引偏移到该量，以便将最小值存储在counter的数组索引0中。然后在您的段循环中，添加最小值重新以获取原始值：

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

Answer 2

您可以在输入中查找最低值，并将其添加到索引中，在构建输出时将其转换回：

def counting(nlist):
    nlist = list(nlist)
    size = len(nlist)
    if size < 2:
        return nlist
    low = min(nlist)
    k = max(nlist) - low
    counter = [0] * ( k + 1 )
    for i in nlist:
        counter[i - low] += 1
    print(counter) # see what the counter list looks like. Remove in final version 
    ndx = 0;
    for i in range( len( counter ) ):
        while 0 < counter[i]:
            nlist[ndx] = i + low
            ndx += 1
            counter[i] -= 1
    return nlist