11.11 Резюме¶
1. Ключевые выводы¶
- Сортировка пузырьком выполняет сортировку за счет обмена соседних элементов. Если добавить флаг для досрочного выхода, лучшую временную сложность пузырьковой сортировки можно оптимизировать до \(O(n)\) .
- Сортировка вставками на каждом раунде вставляет элемент из неотсортированного диапазона в правильную позицию внутри отсортированного диапазона. Хотя ее временная сложность равна \(O(n^2)\) , она очень популярна для задач сортировки небольших массивов, поскольку число элементарных операций у нее сравнительно невелико.
- Быстрая сортировка основана на операции разделения с опорным элементом. При неудачном выборе опорного элемента на каждом раунде ее временная сложность может деградировать до \(O(n^2)\) . Использование медианы трех элементов или случайного опорного элемента уменьшает вероятность этой деградации. Если всегда рекурсивно обрабатывать более короткий поддиапазон первым, можно эффективно уменьшить глубину рекурсии и оптимизировать пространственную сложность до \(O(\log n)\) .
- Сортировка слиянием включает этапы разделения и слияния и служит типичным проявлением стратегии "разделяй и властвуй". Для сортировки массива ей требуется вспомогательный массив, поэтому пространственная сложность равна \(O(n)\) ; однако при сортировке связного списка пространственную сложность можно оптимизировать до \(O(1)\) .
- Блочная сортировка включает три этапа: распределение данных по блокам, сортировку внутри блоков и объединение результатов. Она тоже отражает стратегию "разделяй и властвуй" и подходит для очень больших объемов данных. Ключ к эффективности блочной сортировки - равномерное распределение данных.
- Сортировка подсчетом является частным случаем блочной сортировки; она реализует сортировку через подсчет числа вхождений данных. Сортировка подсчетом подходит для случаев, когда объем данных велик, но диапазон значений ограничен, и при этом данные можно преобразовать в положительные целые числа.
- Поразрядная сортировка выполняет сортировку данных путем последовательной сортировки по каждому разряду и требует, чтобы данные можно было представить в виде чисел фиксированной разрядности.
- В общем случае нам хотелось бы найти алгоритм сортировки, который одновременно обладал бы высокой эффективностью, стабильностью, свойством выполнения на месте и адаптивностью. Но, как и в других разделах алгоритмов и структур данных, не существует одного алгоритма сортировки, способного удовлетворить всем этим требованиям одновременно. На практике приходится выбирать подходящий алгоритм в зависимости от свойств данных.
- На рисунке 11-19 сравниваются эффективность, стабильность, выполнение на месте и адаптивность основных алгоритмов сортировки.
Рисунок 11-19 Сравнение алгоритмов сортировки
2. Вопросы и ответы¶
В: В каких случаях стабильность алгоритма сортировки является обязательной?
В реальных задачах нам может понадобиться сортировать объекты по некоторому атрибуту. Например, у студентов есть два атрибута: имя и рост. Мы хотим выполнить многоуровневую сортировку: сначала отсортировать по имени и получить (A, 180) (B, 185) (C, 170) (D, 170) , а затем отсортировать по росту. Если используемый алгоритм сортировки нестабилен, то мы можем получить (D, 170) (C, 170) (A, 180) (B, 185) .
Нетрудно увидеть, что в этом случае студенты D и C поменялись местами, порядок по имени разрушился, а именно этого мы и не хотим.
В: Можно ли поменять местами порядок "поиска справа налево" и "поиска слева направо" в разделении с опорным элементом?
Нет. Если в качестве опорного элемента выбирается самый левый элемент, необходимо сначала выполнять "поиск справа налево", а уже затем - "поиск слева направо". Этот вывод кажется немного неочевидным, поэтому разберем его подробнее.
Последний шаг partition() - это обмен nums[left] и nums[i] . После обмена все элементы слева от опорного должны быть <= опорного, а значит, перед этим обменом должно выполняться условие nums[left] >= nums[i]. Если сначала выполнять "поиск слева направо", то в случае, когда не удается найти элемент больше опорного, цикл завершится в состоянии i == j , и при этом может оказаться, что nums[j] == nums[i] > nums[left]. Иными словами, на последнем шаге обмена элемент, больший опорного, будет помещен в начало массива, из-за чего разделение завершится неверно.
Например, для массива [0, 0, 0, 0, 1] , если сначала выполнять "поиск слева направо", после разделения получится [1, 0, 0, 0, 0] , а это неправильный результат.
Если же выбрать nums[right] в качестве опорного элемента, то ситуация станет противоположной, и тогда сначала нужно выполнять "поиск слева направо".
В: Почему при оптимизации глубины рекурсии в быстрой сортировке выбор короткого массива гарантирует, что глубина рекурсии не превысит \(\log n\) ?
Глубина рекурсии - это число текущих рекурсивных вызовов, которые еще не завершились. На каждом раунде разделения исходный массив разбивается на два подмассива. После оптимизации глубины рекурсии длина подмассива, в который мы продолжаем рекурсивный спуск, не превышает половины длины исходного массива. Если рассматривать худший случай, когда длина каждый раз становится ровно вдвое меньше, итоговая глубина рекурсии и будет равна \(\log n\) .
В исходной версии быстрой сортировки может происходить последовательный рекурсивный вызов для более длинных массивов; в худшем случае это будут длины \(n\) , \(n - 1\) , \(\dots\) , \(2\) , \(1\) , а глубина рекурсии окажется равной \(n\) . Оптимизация глубины рекурсии как раз и позволяет избежать такого сценария.
В: Если все элементы массива равны, будет ли временная сложность быстрой сортировки равна \(O(n^2)\) ? Как справиться с таким вырождением?
Да. Для этого случая можно рассмотреть разделение массива на три части: элементы меньше опорного, равные опорному и большие опорного. Рекурсию нужно продолжать только для частей меньше и больше опорного. При таком подходе массив, целиком состоящий из одинаковых элементов, будет отсортирован всего за один раунд разделения.
В: Почему худшая временная сложность блочной сортировки равна \(O(n^2)\) ?
В худшем случае все элементы попадут в один и тот же блок. Если затем сортировать этот блок алгоритмом со сложностью \(O(n^2)\) , то общая временная сложность тоже станет \(O(n^2)\) .