Как я могу реализовать CountingSort, который работает с отрицательными числами?

Question

У меня есть следующая реализация алгоритма Counting Sort в 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

Простой подход был бы просто найти минимальное значение и компенсировать ваши показатели на эту величину, так что минимальное значение хранится в индексе массива 0 из counter. Затем в цикле в то время, добавьте минимальное значение обратно, чтобы получить исходные значения:

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