Блог

Быстрая сортировка-это алгоритм сортировки O(nlog(n)). Означает ли это, что он всегда будет быстрее, чем сортировка вставки, которая является алгоритмом O(n2)? почему/почему нет?

В крайних случаях как быстрая сортировка, так и сортировка по вставке могут фактически иметь одинаковую производительность O(n) . Для вставки вида коллекции, которая уже отсортирована, вставка нового элемента потребует не более O(n) сравнений, а также потребует только O(1) вставки. Наихудшее поведение быстрой сортировки происходит, когда разбиение всегда приводит к одному элементу, за которым следует остальная часть коллекции. Если это будет продолжаться до самого конца дерева, то в этом наихудшем случае также может произойти быстрая сортировка O(n) .

Однако в общем случае мы ожидаем, что быстрая сортировка будет выполняться как O(n*lgn) , а сортировка вставки будет выполняться как O(n^2) .

В зависимости от системы, для небольших массивов от 16 до 96 элементов сортировка вставки может быть быстрее. Visual Studio переключается с быстрой сортировки или сортировки слиянием на сортировку вставки для