Цитата(Michael_Rybak @ 13.12.2006 18:05)
Есть т.н. ковшовая, или поразрядная сортировка...
Потом то же самое, но уже по второй с конца цифре (десятки), потом - с третьей и так до 10^8.
Думаю, что наверняка это будет долго.
Цитата(Michael_Rybak @ 13.12.2006 18:05)
А вот тут уже моя твоя
Что такое битовая сортировка?
Это когда сортируем неповторяющиеся числа. Мы можем однозначно сопоставить значеням этих чисел порядковые номера битов в битовом массиве, т.е. число 5432167 будет означать, что 5432167-й бит установлен в единицу. В итоге максимальный размер битового массива в байтах = максимальное значение числа / 8 бит. Потом проходим битовый массив с первого по последний и последовательно записываем номера битов установленных в единицу в сортируемый массив чисел. Допустим значения чисел не превышают 10^7, то размер битового массива в байтах (10^7)/8=1 250 000, что сопоставимо с размером массива хранения самих чисел (в нашей задаче 1 000 000 чисел * 4байта= 4Мб). Конечно если чисел немного, то данный алгоритм не эффективен с точки зрения потребляемой памяти, а если совсем мало - то и медленнее всех других алгоритмов, ибо размер битового массива никак не зависит от количества сортируемых чисел.
Цитата(Caranthir @ 13.12.2006 22:32)
...8942629
8961911
8985513
8948864...
Не стесняйся - программу в студию
Никогда не жадничай. Свои проблемы с любовью дари людям!