Вариация алгоритма сортировки отсчетов?

Question

Я понимаю, что это не стандартная сортировка, как указано в CLRS, но чего не хватает моей упрощенной версии по сравнению со стандартной сортировкой?Я понимаю, что мои сортирует только положительные целые числа, но это должно быть довольно легко настроить (используя карты).

def count_sort(array):
    maximum = max(array)
    minimum = min(0, min(array))
    count_array = [0]*(maximum-minimum+1)

    for val in array:
        count_array[val] += 1

    sorted_array = []
    for i in range(minimum, maximum+1):
        if count_array[i] > 0:
            for j in range(0, count_array[i]):
                sorted_array.append(i)

    return sorted_array

array = [3,2,-1,1,5,0,10,18,25,25]
print array
print count_sort(array)

Редактировать: Причина, по которой я думал, что это не стандартсортировка по счету была вызвана тем, что алгоритм, описанный в лекции MIT OpenCourseware, казался немного более сложным (http://youtu.be/0VqawRl3Xzs?t=34m54s).

Answer 1

Вы делаете что-то странное с вашими мин и макс.Попробуйте это:

def count_sort(array):
    maximum = max(array)
    minimum = min(array)
    count_array = [0]*(maximum-minimum+1)

    for val in array:
        count_array[val-minimum] += 1

    sorted_array = []
    for i in range(minimum, maximum+1):
        if count_array[i-minimum] > 0:
            for j in range(0, count_array[i-minimum]):
                sorted_array.append(i)

    print sorted_array

array = [3,2,-1,1,5,0,10,18,25,25]
print array
count_sort(array)

Answer 2

Я не вижу проблем с тем, как вы сортируете счет, в любом случае вам приходят на ум некоторые предложения, которые могут вас заинтересовать.

Например, строка:

minimum = min(0, min(array))

можно заменить на:

minimum = min(0, *array)

Если вы запускаете свой код в python-2.x, используйте xrange() вместо range()так что вы можете изменить:

for i in range(minimum, maximum+1):

с помощью:

for i in xrange(minimum, maximum+1):

Для последнего цикла, который вам вообще не нужен range(), проверьте вопрос pythonicспособ сделать что-то N раз , чтобы вы могли изменить:

for j in range(0, count_array[i]):
    sorted_array.append(i)

с помощью:

for _ in itertools.repeat(None, count_array[i]):
    sorted_array.append(i)

Answer 3

Вы имеете в виду http://en.wikipedia.org/wiki/Counting_sort?

Если да, это почти похоже на ваш код. Но у него есть одно улучшение: «Здесь сохраняется относительный порядок элементов с одинаковыми ключами, то есть это стабильная сортировка». Так что если вы сортируете значения словаря по словарю, то значения значений останутся прежними, если у них одинаковые ключи.