Основные идеи
Radixsort разработан на основе сортировки ведра, и обе сортировки являются расширенными реализациями распределения сортировки. Основная идея DistributiveSort: процесс сортировки не требует сравнения ключевых слов, но реализует сортировку через процессы «распределения» и «сбора». Их временная сложность может достичь линейного порядка: o (n).
Сортировка кардинальности - это стабильный алгоритм сортировки, но имеет определенные ограничения:
1. Ключевые слова могут быть разложены.
2. Количество записанных ключевых слов меньше, и лучше, если они плотные. 3. Если это число, лучше всего быть без подписи, в противном случае соответствующая сложность отображения будет увеличена. Вы можете сначала сортировать их отдельно.
Давайте посмотрим на сортировку ведра (Radixsort).
Сортировка ведра также называется сортировкой коробки (Binsort). Основная идея состоит в том, чтобы настроить несколько ведер, отсканировать записи, которые будут отсортировать r [0], r [1],…, r [n-1], загрузить все записи с ключевыми словами в определенном диапазоне в ведро KTH (выделено), а затем подключите головы и хвосты каждого неготного ведра в последовательности (собирать) в соответствии с номером последовательности.
Например, для сортировки перетасованных 52 игровых карт по очкам A <2 <… <J <Q <K, 13 -дюймовые ведра »необходимо установить. При сортировке каждая карта помещается в соответствующее ведро по точкам, а затем ведра подключены последовательно, чтобы получить колоду карт, расположенных в постепенном порядке точек.
В сортировке ведра количество ведер зависит от диапазона значений ключевого слова. Следовательно, сортировка ведра требует, чтобы тип ключевого слова был конечным, в противном случае могут потребоваться неограниченное количество ведер.
Вообще говоря, непредсказуемо, сколько записей с одинаковыми ключевыми словами хранятся в каждом ведре, поэтому тип ведра должен быть спроектирован как связанный список.
Чтобы обеспечить стабильную сортировку, соединения во время процесса упаковки и сбора должны выполняться в соответствии с принципом первого в первую очередь.
Для сортировки ведра время процесса распределения составляет O (n); Время процесса сбора составляет O (M) (связанный список используется для хранения ввода для отсортированных записей) или O (M+N). Следовательно, время для сортировки ведра - O (M+N). Если порядок величины количества ведер M составляет O (n), время сортировки ведра является линейным, то есть O (n).
В большинстве случаев сложность основных алгоритмов сортировки, упомянутых выше, является O (N2), а некоторые алгоритмы сортировки - O (NLOGN). Но сортировка ствола может достичь временной сложности O (n). Тем не менее, недостатки сортировки ведра: во -первых, сложность пространства относительно высока, а дополнительные накладные расходы требуются. Сортировка имеет два массива пространственных накладных расходов, один хранит массив для сортировки, а другой-так называемое ведро. Например, значение, которое нужно отсортировать, составляет от 0 до М-1, тогда требуется ведра M, и этот массив ведра требует как минимум M-пространство. Во -вторых, элементы, которые необходимо сортировать, должны быть в пределах определенного диапазона и т. Д.
Сортировка кардинальности - это улучшение сортировки ведра, что делает «сортировку ведра» подходящей для больших наборов значений элементов, а не для повышения производительности.
Давайте воспользуемся примером воспроизведения карт для иллюстрации. Карта состоит из двух ключевых слов: костюм (Peach <Heart <Mei <square) + стоимость лица (A <2 <3 <4 <... <K). Если размер карты определяется сначала костюмом, а карты одного и того же костюма определяются по номеру. У нас есть два алгоритма для решения этой проблемы.
То есть, если костюмы разные, независимо от того, какова стоимость лица, карта с более низким цветом костюма меньше, чем цвет костюма с более высоким цветом костюма. Только в том же цвете костюма зависимость размера определяется размером значения лица. Это упорядочение нескольких кодов ключей.
Чтобы получить результаты сортировки, мы обсуждаем два метода сортировки.
Метод 1: Сначала сортируют костюмы и цвета и разделите их на 4 группы, а именно группу цветов сливы, квадратную группу, группу красного сердца и группу черного сердца. Затем сортируйте каждую группу по значению лица и, наконец, соедините 4 группы вместе.
Метод 2: Во -первых, дайте 13 групп номеров (№ 2, 3, ..., а) Согласно 13 значениям лица, поместите карты в соответствующие группы по номеру в порядке в соответствии с значениями лица и разделите их на 13 свай. Затем дайте 4 группы нумерации (цветы сливы, квадраты, красные сердца, черные сердца), выберите карты в группе 2 и поместите их в соответствующую группу цвета, а затем выберите карты в группе 3 и поместите их в соответствующую группу цвета, ... таким образом, все 4 цветовых групп упорядочены в соответствии с номинальной стоимостью, а затем подключают 4 цветовые группы в последовательности.
Сортировка кода с несколькими ключами сортируется по порядку из основного кода ключа до кода второго ключа или со второй клавиши до основного кода ключа, и делится на два метода:
Наиболее значимый приоритет бита (наиболее согласованнодигитфирст), называемый методом MSD:
1) Сначала сортируйте и группируйте их по K1, разделите последовательность на несколько последующих. В записях одной и той же группы последовательностей ключевые коды K1 равны.
2) Затем сортируйте каждую группу по подгруппам с помощью K2. После этого продолжайте сортировать следующие коды ключей таким образом, пока каждая подгруппа не будет отсортирована по самым вторичным кодом ключа KD.
3) Затем подключите группы, чтобы получить упорядоченную последовательность. Метод, введенный в сортировочных картах по костюмам и значениям лица, является методом MSD.
Наименее значительный метод дигитфирста, называемый методом LSD:
1) Начните сортировать из KD, затем сортируйте KD-1, повторяя по очереди, пока она не будет разделена на наименьшую последующую последовательность в соответствии с K1.
2) Наконец, подключите каждую под последовательность, чтобы получить упорядоченную последовательность. Второй метод, введенный в картах сортировки по костюм и номинальной стоимости, - это метод LSD.
Единственное ключевое слово числового типа или типа символа можно рассматривать как многоизольное слово, состоящее из нескольких цифр или нескольких символов. В настоящее время для его сортировки может использоваться метод «распределения-коллаж». Этот процесс называется методом сортировки кардинальности, где количество возможных значений для каждого числа или символа называется кардинальностью. Например, основание костюмов игровых карт составляет 4, а база номинальной стоимости составляет 13. При сортировке игровых карт вы можете сначала организовать их по стилю или по номинальной стоимости. При сортировке в соответствии с цветами сначала разделите его на 4 стека (распределения) в порядке красного, черного, квадратного и цветов, затем сложите их вместе (собирайте) в этом порядке, а затем разделите их на 13 стеков (распределения) в порядке номинальной стоимости, а затем сложите их вместе (собирайте) в этом порядке. Таким образом, вторичное распределение и коллекция могут упорядочить игровые карты.
Во время процесса «Коллекция распределения» необходимо обеспечить стабильность сортировки.
Идея сортировки кардинальности состоит в том, чтобы скинуть каждую группу ключевых слов в данных, которые будут сортироваться в последовательности. Например, следующая последовательность будет отсортирована:
135, 242, 192, 93, 345, 11, 24, 19
Мы разделяем одно, десять и сотни цифр каждого значения на три ключевых слова, например:
135-> K1 (однозначные цифры) = 5, K2 (десять цифр) = 3, K3 (сто цифр) = 1.
Затем начните с самого низкого одного бита (начиная с последнего ключевого слова), все ключевые слова K1 всех данных выделяются в ковше (потому что каждое число составляет 0-9, поэтому размер ведра составляет 10), а затем вывод данных в ковше в последовательности, чтобы получить следующую последовательность.
(11), (242, 192), (93), (24), (135, 345), (19).
Затем вышеуказанная последовательность выделяется для K2, а выходная последовательность:
(11, 19), (24), (135), (242, 345), (192, 93).
Наконец, для распределения ведра K3 выходная последовательность:
(011, 019, 024, 093), (135, 192), (242), (345) (см. Второе ключевое слово, чтобы сортировать самое высокое ключевое слово, игнорировать десять и однозначные цифры и выделить их в соответствии с цифрами на сотнях цифр)
Сортировка завершена.
Реализация Java
public void radixsort () {int max = array [0]; for (int i = 0; i <array.length; i ++) {// Найти максимальное значение в массиве if (array [i]> max) {max = array [i]; }} int keysnum = 0; // Количество ключевых слов мы используем однозначные цифры, десять цифр и сотни ... в качестве ключевых слов, поэтому количество ключевых слов - максимальная цифра, в то время как (max> 0) {max /= 10; клавиша ++; } List <arraylist <Integer >> buckets = new ArrayList <arraylist <Integer >> (); for (int i = 0; i <10; i ++) {// Возможное число для каждой цифры составляет 0 ~ 9, поэтому установите 10 ведра. // ведро состоит из ArrayList <Integer>} для (int i = 0; i <keysnum; i ++) {// Начните с самого последнего ключевого слова, присваивайте его в соответствии с ключевыми словами, в свою очередь для (int j = 0; j <array.length; j ++) {// Сканировать все элементы и назначить элементы на соответствующее количество. Элемент, такой как 258. Теперь вам нужно взять число на десяти цифр, 258%100 = 58,58/10 = 5 int key = массив [j]%(int) math.pow (10, i+1)/(int) math.pow (10, i); buckets.get (key) .add (массив [j]); // Поместите этот элемент в ведро с ключом ключа} // после распределения, скопируйте элементы в ведре обратно в массив int counter = 0; // счетчик элементов для (int j = 0; j <10; j ++) {arraylist <Integer> bucket = buckets.get (j); // ведро с ключевым словом j while (bucket.size ()> 0) {array [counter ++] = bucket.remove (0); // Скопировать первый элемент в ведре в массив и удалить}} System.out.print ("Thread"+(i+1)+"Cheel Sort:"); отображать(); }}Результаты печати следующие:
Анализ алгоритма
На первый взгляд, эффективность выполнения сортировки кардинальности кажется хорошей, и невероятно, что все, что вам нужно сделать, это скопировать исходные элементы данных из массива в связанный список, а затем скопировать их обратно. Если есть 10 элементов данных, есть 20 репликаций, повторяя процесс для каждого бита. Предполагая, что 5-значные числа отсортированы, требуется 20*5 = 100 копий. Если есть 100 элементов данных, то есть 200*5 = 1000 экземпляров. Количество копий пропорционально количеству элементов данных, то есть O (n). Это самый эффективный алгоритм сортировки, который мы видели.
К сожалению, чем больше элементов данных необходимы более длинные ключевые слова. Если элементы данных увеличиваются в 10 раз, ключевое слово должно быть добавлено одним (еще один раунд сортировки). Количество копий и количество элементов данных пропорциональны длине ключевого слова, и можно считать, что длина ключевого слова - это логарифм N. Таким образом, в большинстве случаев эффективность выполнения кардинальной сортировки обращена на O (n*logn), что почти такая же, как быстро сортировка.
Суммировать
Выше приведено все содержание этой статьи о введении в сортировку кардинальности и реализации языка Java. Я надеюсь, что это будет полезно для всех. Заинтересованные друзья могут продолжать ссылаться на другие связанные темы на этом сайте. Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это.