Использование сортировки по основанию для сортировки как отрицательных, так и положительных чисел

Я пытаюсь использовать сортировку по основанию, чтобы отсортировать список неупорядоченных целых чисел, как положительных, так и отрицательных. У меня есть возможность сортировать список положительных чисел, но я не понимаю, как использовать сортировку по основанию с отрицательными числами. Мне было интересно, может ли кто-нибудь помочь мне с кодированием и объяснением того, как сортировка по основанию работает с отрицательными числами. После некоторого поиска в Google я понимаю, что вы должны относиться к отрицательному знаку как к специальному символу, но я все еще в замешательстве. Ниже вы можете увидеть реализацию сортировки по основанию, которая у меня есть на данный момент, взятую с https://gist.github.com/rizkyabdilah/1740053.

def radix_sort(random_list):
len_random_list = len(random_list)
modulus = 10
div = 1
while True:
    # empty array, [[] for i in range(10)]
    new_list = [[], [], [], [], [], [], [], [], [], []]
    for value in random_list:
        least_digit = value % modulus
        least_digit /= div
        new_list[least_digit].append(value)
    modulus = modulus * 10
    div = div * 10

    if len(new_list[0]) == len_random_list:
        return new_list[0]

    random_list = []
    rd_list_append = random_list.append
    for x in new_list:
        for y in x:
            rd_list_append(y)

random_data = [13, 8, 1992, 31, 3, 1993, 1, 0, -1]
print radix_sort(random_data)

Спасибо за помощь!


python sorting algorithm negative-number radix-sort
person terrabl    schedule 14.02.2016    source источник
comment
Посмотрите здесь: stackoverflow.com/questions/15306665/   -  person Edgar Rokjān    schedule 14.02.2016
comment
да, это то, на что я посмотрел, чтобы выяснить о специальном символе, но я не знаю, как бы я это закодировал...   -  person terrabl    schedule 14.02.2016
comment
Как указано в ссылке выше, исходный список можно разбить на два списка: для отрицательных чисел и для положительных. Отсортируйте эти списки по отдельности, а затем соедините их вместе. Чтобы отсортировать отрицательные целые числа, просто сделайте их положительными, отсортируйте их с помощью сортировки по основанию, инвертируйте результат и снова сделайте их отрицательными.   -  person Edgar Rokjān    schedule 14.02.2016
comment
Как сказал Эдгар Рокян, в stackoverflow. com/questions/15306665/ Я разместил оптимальный ответ. Перейдите к битовому сдвигу и побитовому И. Используйте систему счисления 256 или 65536 вместо произвольных радиусов.   -  person ytoamn    schedule 07.07.2017

Ответы (1)


arrow_upward
1
arrow_downward

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

Это предполагает, что целые числа дополняются единицами или двумя.

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

person rcgldr    schedule 14.02.2016