Сортировка Слиянием vs Быстрая Сортировка - что лучше

@SunFox25 · Регистрация: 09.08.2018

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

Народ, помогите разобраться какой из методов сортировки лучше "Сортировка Слиянием" или "Быстрая Сортировка":
у быстрой худшее время O(n ^ 2), а у сортировки слиянием O(n log n);
среднее время одинаковое - O(n log n);
лучшее - у сортировки слиянием O(n log n), а у быстрой - O(n log n) (обычное разделение) или O(n) (разделение на 3 части);
Затраты пямяти опять же лучше у сортировки слиянием - O(n) вспомогательных, против O(n) вспомогательных + O(log n) вспомогательных у быстрой

Мне почему-то кажеться, что сортировка слиянием лучше, хотя я конечно не разбираюсь в том, что такое это большое "О" и что означает "n log n" (я не понял их перемножить надо (n и логарифм из n) или как?).

Если есть специалист - пожалуйста, разъясните, какой метод всё-таки эффективнее. А то у меня стоит для сортировки текстур сортировка слиянием, а сейчас наткнулся на быструю сортировку, и не знаю, что эффективней.

@Human_foot · 13.08.2018, 16:44

В гугле первые строки. Вот теория с графиками и таблицами сравнений
https://habr.com/post/188010/
https://ru.wikipedia.org/wiki/... _алгоритма
http://bigocheatsheet.com

@anapshy · 13.08.2018, 16:55

По мне так сортировка слиянием. В прочем если входных данных не много, то как-то и без разницы.

Добавлено через 1 минуту

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

"n log n" (я не понял их перемножить надо или как?).

Да.

@SunFox25 · 13.08.2018, 19:49 **[ТС]**

Спасибо большое. Оказалось что самая эффективная сортировка - "Поразрядная Сортировка". Но это наверное только для целых чисел, а мне надо для float. Есть ли какой-нибудь способ выполнить поразрядную сортировку для типов float/double?

@nonedark2008 · 13.08.2018, 20:32

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

Есть ли какой-нибудь способ выполнить поразрядную сортировку для типов float/double?

Если числа положительные, то втупую конвертируешь указатель на массив float в указатель на массив целых беззнаковых чисел того же размера. Отношение порядка при этом сохраняется. Если есть отрицательные числа, то чуть сложнее.

@SunFox25 · 14.08.2018, 03:49 **[ТС]**

Что-то я не уверен, что при таком способе получиться сортировать числа с плавающей запятой, можно пожалуйста доказательства. И как быть с отрицательными числами не могу понять, они очень нужны.

@nonedark2008 · 14.08.2018, 08:15

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

доказательства

Доказательство напрямую следует из стандарта IEEE-754, который практически везде используется для представления чисел с плавающей точкой. Можешь вручную расписать числа и убедиться.

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

И как быть с отрицательными числами не могу понять

Если в массиве будут отрицательные числа, то после сортировки он будет почти упорядочен. Необходимо будет немного переставить элементы.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@SunFox25 7 / 6 / 2 Регистрация: 09.08.2018 Сообщений: 27

	Сортировка Слиянием vs Быстрая Сортировка - что лучше 13.08.2018, 16:21. Показов 11962. Ответов 6 Метки алгоритм (Все метки) Народ, помогите разобраться какой из методов сортировки лучше "Сортировка Слиянием" или "Быстрая Сортировка": у быстрой худшее время O(n ^ 2), а у сортировки слиянием O(n log n); среднее время одинаковое - O(n log n); лучшее - у сортировки слиянием O(n log n), а у быстрой - O(n log n) (обычное разделение) или O(n) (разделение на 3 части); Затраты пямяти опять же лучше у сортировки слиянием - O(n) вспомогательных, против O(n) вспомогательных + O(log n) вспомогательных у быстрой Мне почему-то кажеться, что сортировка слиянием лучше, хотя я конечно не разбираюсь в том, что такое это большое "О" и что означает "n log n" (я не понял их перемножить надо (n и логарифм из n) или как?). Если есть специалист - пожалуйста, разъясните, какой метод всё-таки эффективнее. А то у меня стоит для сортировки текстур сортировка слиянием, а сейчас наткнулся на быструю сортировку, и не знаю, что эффективней. 0

@Human_foot 156 / 114 / 36 Регистрация: 27.06.2018 Сообщений: 257
	13.08.2018, 16:44
	Сообщение было отмечено SunFox25 как решение Решение В гугле первые строки. Вот теория с графиками и таблицами сравнений https://habr.com/post/188010/ https://ru.wikipedia.org/wiki/... _алгоритма http://bigocheatsheet.com 1

@SunFox25 7 / 6 / 2 Регистрация: 09.08.2018 Сообщений: 27
	13.08.2018, 19:49 [ТС]
	Спасибо большое. Оказалось что самая эффективная сортировка - "Поразрядная Сортировка". Но это наверное только для целых чисел, а мне надо для float. Есть ли какой-нибудь способ выполнить поразрядную сортировку для типов float/double? 0

@SunFox25 7 / 6 / 2 Регистрация: 09.08.2018 Сообщений: 27
	14.08.2018, 03:49 [ТС]
	Что-то я не уверен, что при таком способе получиться сортировать числа с плавающей запятой, можно пожалуйста доказательства. И как быть с отрицательными числами не могу понять, они очень нужны. 0

Сортировка Слиянием vs Быстрая Сортировка - что лучше

Решение