Лабораторный практикум по информатике
жүктеу/скачать 1,1 Mb.
|
Быстрая сортировкаАлгоритм быстрой сортировки является одним из самых быстрых алгоритмов сортировки: в лучшем случае он имеет логарифмическую сложность, в худшем – квадратичную. Алгоритм выполняется следую- щим образом: Выбирается некоторый элемент, который называется опорным. Реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все эле- менты, больше опорного, – справа от него. Рекурсивно упорядочиваем массивы, лежащие слева и справа от опорного элемента. // Быстрая сортировка 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); }
жүктеу/скачать 1,1 Mb. Достарыңызбен бөлісу:
|