сценарии сортировки сортировки и подсчета сортировки

Question

Это меня немного смущает. Мне хотелось бы знать сценарии, где в сортировке ведра следует использовать по подсчету сортировки (или наоборот).

Answer 1

Эти две страницы предоставляют некоторую информацию обоим типам.

• Counting sort
• Bucket sort

О счетной рода:

Поскольку подсчет вид использует ключевые значения, как индексы в массиве, то не сравнение сортировки, и нижняя граница Ω (n log n) для сравнения Сортировка к нему не применяется , 1 Сортировка ковша может использоваться для многих из теми же задачами, что и сортировка сортировки, с аналогичным анализом времени; Однако, по сравнению с подсчетом сортировки, для сортировки в bucket требуются связанные списки, динамические массивы или большое количество предварительно распределенной памяти для хранения наборов элементов в каждом ведре, тогда как подсчет сортировки вместо этого хранит одно число (количество элементов) на ведро. [4]

О ковшового рода:

ковша рода можно рассматривать как обобщение подсчета рода; фактически, , если каждый ковш имеет размер 1, тогда сортировка ковша дегенерирует до подсчета . Величина переменной размера ведра сортировки ведра позволяет использовать память O (n) вместо памяти O (M), где M - количество различных значений ; в обмене, он отказывается от поведения счетного типа O (n + M) наихудшего случая .