Сортировка — различия между версиями
Yurik (обсуждение | вклад) |
Yurik (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | <wikitex> | ||
''Сортировкой'' называется процесс упорядочивания множества объектов по какому-либо признаку. | ''Сортировкой'' называется процесс упорядочивания множества объектов по какому-либо признаку. | ||
| Строка 5: | Строка 6: | ||
== Классификация сортировок == | == Классификация сортировок == | ||
| − | Будем рассматиривать сортировки массива из | + | Будем рассматиривать сортировки массива из $n$ элементов множества $A$, |
| − | причем на | + | причем на $A$ должно быть выполнено [[Бинарное отношение|отношение эквивалентности]]. |
| − | + | === Время работы. === | |
| − | Эта классификация является самой важной. В основном временные оценки бывают | + | Эта классификация является самой важной. В основном временные оценки бывают $O(n)$, $O(n \log n)$ и $O(n^2)$. |
| + | * Квадратичные. Такие сортировки самые простые в понимании. | ||
| + | ** [[Сортировка пузырьком| Сортировка пузырьком (Bubble Sort)]] | ||
| + | ** [[Сортировка вставками| Сортировка вставками (Insertion Sort)]] | ||
| + | ** [[Сортировка выбором| Сортировка выбором (Selection Sort)]] | ||
| + | |||
| + | |||
| + | |||
| + | </wikitex> | ||
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Сортировки]] | [[Категория: Сортировки]] | ||
Версия 23:45, 11 июня 2012
<wikitex> Сортировкой называется процесс упорядочивания множества объектов по какому-либо признаку.
Обычно таким признаком служит лексикографический номер.
Классификация сортировок
Будем рассматиривать сортировки массива из $n$ элементов множества $A$, причем на $A$ должно быть выполнено отношение эквивалентности.
Время работы.
Эта классификация является самой важной. В основном временные оценки бывают $O(n)$, $O(n \log n)$ и $O(n^2)$.
- Квадратичные. Такие сортировки самые простые в понимании.
</wikitex>
