Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 3.8. Быстрая сортировка. Рекурсивный вариант 
void QuickSort(int left, int right) 
{ 
int i = left; int j = right; 
int x = arr[(left + right) / 2]; // 
средний 
элемент 
do 
{ 
while (arr[i] < x)
// 
поиск элемента больше среднего 
i++; 
while (arr[j] > x)
// 
поиск элемента меньше среднего 
j--; 
if (i <= j) // 
обмен элементов местами 
{
int tmp = arr[i]; arr[i] = arr[j];
arr[j] = tmp; 
i++; j--; 
} 
} 
while (i<=j);
if (leftQuickSort(left,j); 
//
обработка левого подмассива 
if (iQuickSort(i,right);
// 
обработка правого подмассива 
} 
12 / 23

---

59 
Алгоритм быстрой сортировки имеет минимальную сложность порядка 
N×logN и максимальную сложность порядка N
2
, но такая сложность встреча-
ется достаточно редко. 
Сейчас покажем, как можно представить алгоритм быстрой сортировки 
в виде нерекурсивной функции. При этом рекурсия представляется как ите-
рация, но необходимы дополнительные переменные и действия для хранения 
информации: отложенных вызовов. Рекурсия использует стек в скрытом от 
программиста виде, но при нерекурсивном представлении функции стек при-
ходится использовать явно. 
Один этап быстрой сортировки разбивает исходный массив на два под-
массива. Границы правого подмассива запоминаются в стеке, и происходит 
сортировка левого подмассива. Затем из стека выбираются границы, находя-
щиеся в вершине, и обрабатывается подмассив, определяемый этими грани-
цами. В процессе его обработки в стек может быть записана новая пара гра-
ниц и т. д. При начальных установках в стек заносятся границы исходного 
массива. Сортировка заканчивается, когда стек становится пустым.
Поскольку в стеке нужно хранить левую и правую границы, тип эле-
мента стека должен быть следующим: 
structur TInf 
{ 
int l,r; 
} 
Так же, как и в задаче с Ханойскими башнями, будем использовать эк-
земпляр класса MyStack. Функция QuickStack, реализующая нерекурсив-
ный вариант быстрой сортировки, представлена в листинге 3.9.