2015-01-21
404
Сортировка выбором имеет квадратичную сложность O(n2) и, как и предыдущий метод пузырька, эффективен лишь на небольших объемах данных.
Алгоритм находит номер минимального значения в текущем списке, меняет этот элемент со значением первой неотсортированной позиции (если минимальный элемент не находится на данной позиции), а затем сортирует хвост списка, исключив из рассмотрения уже отсортированные элементы:
// Сортировка выбором
void SelectionSort(ref int[] Array)
{
// Перебираем все элементы массива (кроме последнего)
// i - позиция первого неотсортированного элемента
for (int i = 0; i < Array.Length - 1; i++)
{
// Позиция минимального элемента справа от i
int min = i;
// Перебираем все элементы справа от i
for (int j = i + 1; j < Array.Length; j++)
// Меньше ли очередной элемент минимального?
if (Array[j] < Array[min])
min = j; // Да - теперь это новый минимальный элемент
// Минимальный элемент не на первом месте? Меняем местами!
if (min!= i)
{
int t = Array[i];
Array[i] = Array[min];
Array[min] = t;
}
}
}
Быстрая сортировка
Алгоритм быстрой сортировки является одним из самых быстрых алгоритмов сортировки: в лучшем случае он имеет логарифмическую сложность, в худшем – квадратичную. Алгоритм выполняется следующим образом:
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);
}
