Быстрая сортировка

 Быстрая сортировка

Алгоритм быстрой сортировки является одним из самых быстрых алгоритмов сортировки: в лучшем случае он имеет логарифмическую сложность, в худшем – квадратичную. Алгоритм выполняется следую- щим образом:

1.            Выбирается некоторый элемент, который называется опорным.

2.            Реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного – справа от него.

3.            Рекурсивно упорядочиваем массивы, лежащие слева и справа от опорного элемента.

// Быстрая сортировка

void QuickSort(ref int[] Array, int Left, int Right)

{

// i и j – индексы границ разделяемого массива int i = Left;

int j = Right;

// x – индекс опорного элемента int x = Array[(Left + Right) / 2]; do

{

// Ищем элемент слева, который больше опорного while (Array[i] < x)

++i;

// Ищем элемент справа, который меньше опорного while (Array[j] > x)

--j;

// Если индексы не поменялись местами,

// то обмениваем элементы if (i <= j)

{

int t = Array[i]; Array[i] = Array[j]; Array[j] = t;

i++; j--;

}

} while (i <= j);

// Рекурсивно выполняем быструю сортировку

// для массивов слева и справа if (Left < j)

QuickSort(ref Array, Left, j); if (i < Right)

QuickSort(ref Array, i, Right);

}