Учитывая набор входных чисел из n целых чисел в диапазоне [0..n^3-1], предоставим алгоритм линейной временной сортировки.Сортировка по линейному времени?
Это обзор для моего теста в четверг, и я не знаю, как подойти к этой проблеме.
Также взгляните на соответствующие сорта: pigeonhole sort или counting sort, а также radix sort, как упомянуто Pukku.
Не думаете ли вы, что n^3-1 слишком велик, чтобы использовать сортировку подсчета? если n = 100, у вас будет 100^3 пространства для сортировки. Ему нужно изменить базу целых чисел и использовать сортировку Radix. – unj2
С номером n d-цифр, находящимся в [0, n^3 - 1], число цифр d равно 3log (n), и алгоритм будет работать в O (dn) => O (nlog (n)). Сорт Radix не является линейным решением. Кроме того, голубь не подходит ни потому, что количество элементов не является «примерно одинаковым» числа возможных ключей. – Gevorg
Посмотрите на radix sort.
Просто предостережение, сортировка radix является линейной, если у вас есть фиксированная максимальная длина для ваших ключей ... так как у вас есть диапазон целых чисел, то да, она может быть линейной, но это не всегда так. –
Это также называется «сортировка ковша». – GoatRider
С номером n d-цифр, находящимся в [0, n^3 - 1], тогда число цифр d равно 3log (n), и алгоритм будет работать в O (dn) => O (nlog (n)). Сорт Radix не является линейным решением. – Gevorg
Набор ограниченного диапазона чисел может быть представлен растровым изображением бит RANGE. В этом случае растровое изображение 500 МБ, поэтому для чего угодно, кроме огромных списков, вам будет лучше с Radix Sort. Когда вы столкнетесь с номером k, установите битмап [k] = 1. Одиночный обход через список, O (N).
Обратите внимание, что n может не равняться 2. – Reunanen
Это действительно просто, если п = 2 и номера являются уникальными:
Сложность => O (2n)
В противном случае используйте Radix Сортировка:
Сложность => O (кп) (надеюсь)
В вопросе говорится n^31, а не 2^31. Далее вы предполагаете, что число не появляется более одного раза. –
Я предполагаю, что n = 2. Я думаю, что это опечатка. В конце концов, мы обычно не используем другие базы, кроме 2. Вы правы, я (возможно, неправильно), если числа не повторяются! – Ash
danbruc, я не знаю вашего фона, но мой ответ очень важен и хорошо сбалансирован (если можно так выразиться). – Ash
wikipedia показывает довольно много различных алгоритмов сортировки и их сложности. вы можете проверить их
Когда люди говорят «алгоритм сортировки», они часто ссылаются на «алгоритм сортировки сравнения», который представляет собой любой алгоритм, который зависит только от возможности спросить », эта вещь больше или меньше, чем эта ». Поэтому, если вы ограничены вопросом об этом вопросе о данных, вы никогда не получите больше, чем n * log (n) (это результат выполнения log (n) поиска n факториальных возможных порядков набора данных) ,
Если вы можете избежать ограничений «сортировки сортировки» и задать более сложный вопрос о части данных, например «что такое базовый 10 оснований этих данных», тогда вы можете найти любое количество линейных алгоритмов временной сортировки, они просто занимают больше памяти.
Это коммивояжное пространство. Сортировка сравнения занимает мало или вообще не работает и работает в N * log (n) времени. (например) выполняется в O (n) времени AND O (log (radix)).
Вы можете сделать на месте сортировку радикса – aaronman
@aaronman вы можете ссылаться на линейный алгоритм сортировки пространственного пространства по времени? –
Уверен, имейте в виду, когда я говорю о постоянном пространстве, это относится к размеру диапазона, хранилище не является постоянным в отношении размера сортировки (32 бит на 64 бит). ссылку ([radix] (https://github.com/aaronjosephs/radix/blob/master/radix.cpp)) для моей собственной реализации, код грязный, но он называется 'msd16_radix', он использует подсчет для сделайте вид на месте, также он вызывает std :: sort, потому что он быстрее для небольших массивов, поэтому моя реализация не является строго inplace (если std :: sort использует память), но ясно, что она может быть достигнута на месте. – aaronman
так алго возможно:
M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];
Это одна возможно алго для линейной сложности, но она имеет сложность O (K * N) по барану (N - элементы, номер массива, K - Len элемента)
Думайте цифры как трехзначные числа, где каждая цифра находится в диапазоне от 0 до n-1. Сортируйте эти числа с помощью сортировки radix. Для каждой цифры есть вызов для подсчета сортировки, который принимает время Theta (n + n), так что общее время работы соответствует Theta (n).
Не могли бы вы еще раз проверить вопрос? N vs n? [0..n^31] vs [0..2^31] vs [0..2^32-1]? –
@ danbruc - Хорошая точка. Кроме того, в редакции 1 говорится [0..n^3-1] - почему это [0..n^31] сейчас? –
Я понятия не имею, почему это изменилось. Я не помню, когда-либо обновлялся. –