Глубокий анализ алгоритма сортировки ведра и реализации кода JavaScript на node.js

1. Введение в сортировку ведра

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

Сортировка ведра выполняется в следующих 4 шагах:

(1) Установите фиксированное количество пустых ведер.

(2) Поместите данные в соответствующее ведро.

(3) Сортируйте данные в каждом непустых ведре.

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

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

2. Демонстрация алгоритма сортировки ведра

Например, в настоящее время существует набор данных [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]. Как сортировать его от маленького до большого?

Шаги операции:

(1) Установите количество ведер на 5 пустых ведер, найдите максимальное значение 110 и минимальное значение 7, а диапазон каждого ведра составляет 20,8 = (110-7+1)/5.

(2) Пройти исходные данные, поместите их в соответствующее ведро со связанной структурой списка. Число 7, значение индекса ведра составляет 0, формула расчета составляет пол ((7 7) / 20,8), число 36, значение индекса ковша составляет 1, этаж расчивания ((36 7) / 20,8).

(3) При вставке данных в ведро с одним и тем же индексом во второй раз определите размер существующих чисел и вновь вставленных чисел в ведро и вставьте их в порядке слева направо, от малого до большого. Например: когда вставлено ведро с индексом 2, при вставке 63, в ведре уже есть 4 числа 56, 59, 60 и 65, а затем число 63 вставлено слева от 65.

(4) Слияйте непустые ведра, слияние 0, 1, 2, 3 и 4 ведра в порядке слева направо.

(5) Получите структуру сортировки ведра

3. Реализация программы Nodejs

Нетрудно внедрить зрелые алгоритмы, такие как сортировка ведра. Согласно приведенным выше идеям, я написал простую программу для их реализации. Я чувствую, что самой проблемной частью является использование JavaScript для манипулирования связанным списком.

Фактический код заключается в следующем:

 'использовать строгий';//////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////// сортировка ([1,4,1,5,3,2,3,3,2,5,2,8,9,2,1], 5) * Сорт ([1,4,1,1,5,3,2,3,3,2,5,2,8,9,2,1], 5,0,5) */exports.sort = function (arr, count) {if. count = count || (счет> 1? СЧЕТ: 10); // Судья максимальные и минимальные значения var min = arr [0], max = arr [0]; для (var i = 1; i <arr.length; i ++) {min = min <arr [i]? Мин: arr [i]; max = max> arr [i]? Макс: arr [i]; } var delta = (max - min + 1) / count; // console.log (min+","+max+","+delta); // Инициализировать ковш вар ведра = []; // данные хранения в ведро для (var i = 0; i <arr.length; i ++) {var idx = math.floor ((arr [i] - min) /delta); // индекс ведра if (buckets [idx]) {// Непустые ковшки var bucket = buckets [idx]; var insert = false; // вставить флаг Stone L.Retraversal (ведра, функция (элемент, выполнен) {if (arr [i] <= item.v) {// меньше, вставьте l.Append (item, _val (arr [i])); insert = true; dod (); // exit Traversal}}); if (! Вставьте) {// больше, вставьте L.Append (bucket, _val (arr [i])); }} else {// пустое ведро var bucket = l.init (); L.Append (ведро, _val (arr [i])); ведра [idx] = ведро; // реализация списка ссылок}} var result = []; for (var i = 0, j = 0; i <count; i ++) {l.retraversal (buckets [i], function (item) {// console.log (i+":"+item.v); result [j ++] = item.v;}); } return result;} // Функция объекта хранения списка _val (v) {return {v: v}}

Запустите программу:

 var algo = require ('./ index.js'); var data = [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]; консоль. console.log (algo.bucketsort.sort (data, 10)); // 10 ведра

Выход:

 7, 22, 33, 36, 42, 42, 56, 67, 67, 77, 83, 84, 94, 101, 110 ][ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ][ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ][ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ][ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110].

Что нужно объяснить:

(1) сортировка в ведре может быть реализована во время процесса вставки, как описано в программе; Или он может быть вставлен без сортировки, а затем отсортирован во время процесса слияния, и можно вызвать быструю сортировку.

(2) Связанный список. В базовом API узла существует реализация связанного списка. Я не использовал его напрямую, но позвонил через пакет Linklist: https://github.com/nodejs/node-v0.x-archive/blob/master/lib/_linklist.js

4. Случай: Статистика сортировки ведра по оценкам вступительных экзаменов в колледже

Одним из самых известных сценариев применения для сортировки ведра является подсчет результатов вступительного экзамена в колледже. Число кандидатов на вступительные экзамены национального колледжа за один год составляет 9 миллионов, а оценки являются стандартными, с минимум 200 и максимум 900. Значительного десятичного значения нет. Если эти 9 миллионов цифр отсортированы, что мы должны делать?

Анализ алгоритма:

(1) Если вы используете сортировку на основе сравнения, быстрая сортировка, средняя сложность времени-O (nlogn) = O (9000000*log9000000) = 144114616 = 144 миллиона сравнений.

(2) Если вы используете сортировку, сортировку и среднюю сложность на основе подсчетов, вы можете контролировать линейную сложность. При создании 700 ведра, одно ведро от 200 минут до 900 минут, O (n) = O (90000000), оно эквивалентно сканированию частей данных на 900 Вт один раз.

Мы запускаем программу для сравнения быстрой сортировки и сортировки ведра.

 // Создать 100 Вт деталей данных в [200,900] закрытый интервал данных var = algo.data.randomdata (1000*1000,200,900); var s1 = новая дата (). GetTime (); algo.quicksort.sort (data); // быстрая сортировка var s2 = новая дата (). ведра var s3 = new date (). gettime (); console.log ("QuickSort Time: %sms", s2-s1); console.log ("Время ведра: %sms", s3-s2);

Выход:

 QuickSort Время: 14768msbucket Время: 1089ms

Поэтому для случая вступительного экзамена в колледже сортировка ведра более подходит! Наше использование соответствующих алгоритмов в подходящих сценариях принесет улучшение производительности в программу за пределами оборудования.

5. Анализ затрат на сортировку ведра

НО...

Сортировка ведра использует взаимосвязь функций отображения, снижая почти всю сравнительную работу. Фактически, расчет значения F (k) сортировки ведра эквивалентен делению в быстром порядке и разделил большой объем данных на в основном упорядоченные блоки данных (ведра). Тогда вам нужно только провести расширенные сравнения и сортировку небольшого количества данных в ведре.

Сложность времени сортировки ведра N Ключевые слова делится на две части:

(1) Цикл для вычисления функции отображения ковша каждого ключевого слова, и эта сложность времени - O (n).

(2) Используйте расширенный алгоритм сортировки сравнения для сортировки всех данных в каждом ведре, со сложностью ∑o (ni*logni). где Ni-это сумма данных I-Th Bucket.

Очевидно, что часть (2) является определяющим фактором производительности сортировки ведра. Минимизация объема данных в ведре является единственным способом повышения эффективности (потому что наилучшая средняя сложность времени на основе сортировки сравнения может достичь только O (n*logn)). Поэтому нам нужно стараться изо всех сил, чтобы сделать следующие два момента:

(1) Функция отображения F (k) может равномерно распределять N к M -ведра, так что каждое ведро имеет объемы данных [N/M].

(2) Попробуйте увеличить количество бочек. В крайнем случае, каждое ведро может получить только одну данную, что полностью избегает операции сортировки данных в ведре. Конечно, это нелегко. Когда количество данных огромно, функция f (k) сделает количество коллекций ведра огромным, а космические отходы серьезными. Это компромисс между стоимостью времени и пространства.

Для отсортированных данных и ковшом, средняя сложность времени сортировки ведра каждого ведра [N/M]:

 O (n)+o (m*(n/m)*log (n/m)) = o (n+n*(logn-logm)) = o (n+n*logn-n*logm)

Когда n = m, то есть, когда есть только один данные на ведро под пределом. Лучшая эффективность сортировки ведра может достигать O (n).

6. Резюме

Средняя временная сложность сортировки ведра является линейной o (n+c), где c = n*(logn-logm). Если количество бочек М большее по сравнению с тем же N, тем выше его эффективность, а лучшая сложность времени достигает O (n). Конечно, пространственная сложность сортировки ведра - O (N+M). Если входные данные очень большие, а количество ведер очень большое, стоимость пространства, несомненно, дорого. Кроме того, сортировка ведра стабильна.

На самом деле, у меня есть еще одно ощущение: среди алгоритмов поиска лучшая сложность временного алгоритма поиска-O (Logn). Например, полуфинансы, сбалансированные бинарные деревья, красные и черные деревья и т. Д. Давайте посмотрим на: «Мысли и ведро сортируют хэш -столы ту же песню?