Автор: oleg_alexeev (11.05.2007 в 13:43)
Я написал не вполне верно. Там a[i] сохраняется во временную переменную, и иногда делается обмен с ней. Но суть в том, что исходный массив разбивается на два и все элементы первого меньше чем некое среднее значение, а все элементы второго больше него.
Когда при выборе среднего значения мы попадаем на наименьшее или наибольшее - то просто время работы увеличивается. В самом худшем случае (когда всегда выбираем минимум или максимум) оно будет пропорционально n^2, где n - число элементов в массиве.