Я столкнулся со следующей проблемой:
Рассмотрим массив, состоящий из следующих элементов в несортированном порядке, но 60 как первый элемент:
60,80,15,95,7,12,35,90,55
Алгоритм быстрой сортировки применяется, выбрав первый элемент в качестве оси. Сколько всего возможных комбинаций целых чисел массива, сохраняя эффект первого прохода алгоритма разбиения?
Было дано решение
Мы записали отсортированный массив как: 7 12 15 35 55 60 80 90 95
Таким образом, как показано выше, у нас будет 5 элементов слева от 60 и 3 элемента справа от 60. Отсюда количество требуемых перестановок = нет перестановок левой части * правой части = 5 ! * 3! = 120 * 6 = 7200
Я чувствую, что разделение может дать ровно одно расположение после первого прохода:
55, 15, 7, 12, 35, 60, 80, 90, 95
, и неправильно делать факториал элементов по обе стороны от оси. Так что вопрос в некотором смысле некорректен. Я прав или я что-то здесь упускаю?
PS: я предполагаю стандартную быструю сортировку, например ту, которая приведена в CLRS.