Лабораторный практикум по информатике



бет67/83
Дата06.01.2022
өлшемі1.1 Mb.
#15674
түріПрактикум
1   ...   63   64   65   66   67   68   69   70   ...   83

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


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

  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);

}



    1. Достарыңызбен бөлісу:
1   ...   63   64   65   66   67   68   69   70   ...   83




©emirsaba.org 2022
әкімшілігінің қараңыз

    Басты бет