В чем разница между сортировкой ведра и сортировкой? - PullRequest
Новая
       22

В чем разница между сортировкой ведра и сортировкой?

43 голосов
/ 16 декабря 2010

Сортировка ведра и сортировка по основанию - близкие родственники; сортировка ведра идет от MSD к LSD, тогда как сортировка по основанию может идти в обоих «направлениях» (LSD или MSD). Как работают оба алгоритма, и, в частности, чем они отличаются?

Ответы [ 2 ]

40 голосов
/ 06 января 2011

Начальный проход как RadixSort, так и BucketSort абсолютно одинаков. Элементы помещаются в buckets (или bins) инкрементальных диапазонов (например, 0-10, 11-20, ... 90-100), в зависимости от количества цифр в наибольшем числе.

Однако на следующем проходе BucketSort упорядочивает эти «сегменты» и добавляет их в один массив. Тем не менее, RadixSort добавляет сегменты без дальнейшей сортировки и «повторно упаковывает» их на основе второй цифры (десятая) чисел. Следовательно, BucketSort более эффективен для «плотных» массивов, тогда как RadixSort может хорошо обрабатывать разреженные (не совсем разреженные, но разнесенные) массивы.

20 голосов
/ 16 мая 2015

Bucket Sort и Radix Sort похожи на родственные алгоритмы сортировки, потому что они не являются сортировками сравнения и общая идея схожа.Кроме того, они оба немного абстрактны в реализации.

Radix Sort :

  • Radix означает основание (двоичное, восьмеричное, десятичное и т. Д.).Следовательно, эта сортировка для чисел (также используется для строк).Это работает, когда каждый элемент E подобен e k ... e 2 e 1 e 0 , где e i находится в некотором диапазоне.(обычно 0 к основанию, например, 0-9 в десятичном виде или 0-255 в ASCII-символах)

  • Затем он использует k проходов стабильного алгоритма субсортировки (имеетбыть стабильным , иначе Radix sort не будет работать) для сортировки чисел.Этот алгоритм субсортировки обычно является сортировкой «Подсчет» или «Сортировка по сегментам», но это не может быть сама сортировка по Radix .

  • Вы можете начать с наиболее значимой цифры или наименее значимойЦифра, потому что тасует каждое число в каждом проходе (от k до 0 или от 0 до k)

  • Это стабильный алгоритм сортировки.

Сортировка сегментов:

  • Разделяет массив на меньшие группы или сегменты и сортирует ихиндивидуально с использованием алгоритма субсортировки или рекурсивного вызова самого себя, а затем объединяет результат .Например, сортировка игроков путем добавления в ведра их команды, а затем сортировка их по номерам майки или что-то вроде сортировки чисел в диапазоне от 1-30 до 3 сегментов 1-10, 11-20, 21-30.

  • Шаг объединения тривиален (в отличие от сортировки слиянием).просто скопируйте элементы каждого сегмента обратно в исходный массив или объедините заголовок каждого блока с хвостом предыдущего блока (в случае связанных списков)

  • Радикс / основание может быть aвведите / instance группы / группы во время сортировки чисел.Следовательно, вы могли бы представить себе основание MSD как модифицированный экземпляр сортировки сегментов

  • Сортировка сегментов не на месте , но стабильный алгоритм сортировки.Однако некоторые варианты сортировки сегментов могут быть нестабильными (если вы используете нестабильный алгоритм подсортировки)

...