Алгоритм для сортировки миллион чисел

@Bleva · Регистрация: 13.01.2020

Студворк — интернет-сервис помощи студентам

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

@Tavashi · 26.02.2021, 21:57

Quicksort.

@Euraks · 27.02.2021, 07:16

Посмотри CS50 на русском: Лекция #8 как раз эта тема..

@Catstail · 27.02.2021, 10:32

Зависят от того, какие числа... Можно и быстрее QuickSort

@Bleva · 27.02.2021, 12:40 **[ТС]**

Сообщение от Catstail

Зависят от того, какие числа... Можно и быстрее QuickSort

Любые инт числа

@Aviz__ · 27.02.2021, 13:43

Сообщение от Bleva

Любые инт числа

смысл твоего вопроса в чем? чем те не по душе стандартный метод sort(int arr) класса Arrays из пакета java.util?!

@Bleva · 27.02.2021, 14:27 **[ТС]**

Сообщение от Aviz__

смысл твоего вопроса в чем? чем те не по душе стандартный метод sort(int arr) класса Arrays из пакета java.util?!

Так мне надо самому реализовать. Вот в чем смысл. Про сорт та я и так знаю.

@Tavashi · 27.02.2021, 15:03

Если говорить про built-in методы, то Arrays.sort() будет деградировать на таком кол-ве элементов. Вместо него лучше использовать Arrays.parallelSort().

@Bleva · 27.02.2021, 15:27 **[ТС]**

Сообщение от Tavashi

Если говорить про built-in методы, то Arrays.sort() будет деградировать на таком кол-ве элементов. Вместо него лучше использовать Arrays.parallelSort().

Мне не buit-in методы нужны. Я делаю задание. Самому нужно реализовать.

@Aviz__ · 27.02.2021, 15:29

Сообщение от Tavashi

будет деградировать на таком кол-ве элементов

каком, количестве, ты о чем?! миллион интов это вообще не о чем.

Сообщение от Bleva

Так мне надо самому реализовать.

и в чем загвоздка? ты не можешь найти в гугле различные алгоритмы сортировки?!

@Tavashi · 27.02.2021, 15:37

Сообщение от Bleva

Самому нужно реализовать.

Если есть желание скрупулезно изучать эту тему, то можно начать, например, отсюда.

@Arsegg · 27.02.2021, 17:32

Сообщение от Bleva

Любые инт числа

Цифровая сортировка - твой выбор.
P. S. O(N).

@Tavashi · 02.03.2021, 01:25

Bleva,

O(N)

Radix sort: O(d*n);
Линейное время только в случае, если у вас ширина ключа (d) - константа. Иначе, скорость асимптотически может деградировать до O(n*log(n)), потому что d (кол-во цифр) вычисляется как O(log(k)), где k (макс. значение) <= n. Другими словами, для 10-й СИ чем больше цифр имеют числа и чем больше разница между числами с малым и большим кол-вом цифр, тем скорость медленнее.
Также, поразрядную сортировку нужно будет дорабатывать, если не исключены отрицательные числа. (Это минус относительно сортировок, основанных на сравнении)

@Aviz__ · 02.03.2021, 07:10

Сообщение от Bleva

Так мне надо самому реализовать.

вот Как лучше исследовать скорость сортировки массивов чел реализовал, проверяй.

@webnibbana · 02.03.2021, 14:13

Radix sort: O(d*n);

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20%	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

Алгоритм для сортировки миллион чисел

Решение

Решение

@Bleva 0 / 0 / 0 Регистрация: 13.01.2020 Сообщений: 81

	Алгоритм для сортировки миллион чисел 26.02.2021, 20:49. Показов 3337. Ответов 14 Метки java (Все метки) Какой алгоритм сортировки использовать для сортировки миллион чисел в массиве? Исходя конечно же из быстроты и памяти. 0

@Tavashi 1172 / 762 / 194 Регистрация: 21.05.2016 Сообщений: 1,858
	26.02.2021, 21:57
	Quicksort. 0

@Euraks 1 / 1 / 0 Регистрация: 01.11.2020 Сообщений: 10
	27.02.2021, 07:16
	Посмотри CS50 на русском: Лекция #8 как раз эта тема.. 0

@Catstail Супер-модератор 38197 / 21130 / 4309 Регистрация: 12.02.2012 Сообщений: 34,737 Записей в блоге: 14
	27.02.2021, 10:32
	Сообщение было отмечено Aviz__ как решение Решение Зависят от того, какие числа... Можно и быстрее QuickSort 0

@Tavashi 1172 / 762 / 194 Регистрация: 21.05.2016 Сообщений: 1,858
	27.02.2021, 15:03
	Если говорить про built-in методы, то `Arrays.sort()` будет деградировать на таком кол-ве элементов. Вместо него лучше использовать `Arrays.parallelSort()`. 0

@webnibbana 0 / 0 / 0 Регистрация: 02.03.2021 Сообщений: 2
	02.03.2021, 14:13
	Radix sort: O(d*n); 0