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

Исходная упорядоченность массива. В исходном массиве могут 
встречаться упорядоченные участки. В предельном случае массив может ока-
заться уже упорядоченным. Одни алгоритмы не учитывают исходной упоря-
доченности и требуют одного и того же времени для сортировки любого 
множества данного объема, другие выполняются тем быстрее, чем лучше 
упорядоченность на входе. Говорят, что сортировка демонстрирует естест-
венное поведение, если число сравнений и число пересылок имеют наимень-
шие значения из возможных, в случае упорядоченного массива и возрастают 
с ростом неупорядоченности, и неестественное поведение в противном слу-
чае.
Временные характеристики операций. При определении алгоритма 
время выполнения обычно считается пропорциональным числу сравнений 
ключей. Ясно, однако, что сравнение числовых ключей выполняется быстрее, 
чем строковых; операции пересылки выполняются тем быстрее, чем меньше 
объем записи, и т.п. В зависимости от структуры сортируемых элементов 
может быть выбран алгоритм, обеспечивающий минимизацию числа тех или 
иных операций. 
Метод сортировки называется устойчивым, если относительный поря-
док элементов с одинаковыми ключами не меняется при сортировке. Устой-
чивость сортировки часто бывает желательна, если элементы уже упорядоче-
ны по одному ключу, а сортировка ведется по другому ключу. 
Методы сортировки массива можно разбить на три основных класса в 
зависимости от лежащего в их основе приема: 
− сортировка выбором; 
− сортировка включениями; 
− сортировка обменом. 
В дальнейшем изложении предполагается, что результатом сортировки 
является массив, элементы которого упорядочены по возрастанию ключа. 
При этом ключом элемента считается значение самого элемента. 
2.2.1. С
ОРТИРОВКА ПРОСТЫМ ВЫБОРОМ
 
Это простой и наиболее очевидный способ сортировки. Соответствую-
щий алгоритм можно описать следующим образом. 
1.
Среди элементов массива выбирается элемент с наименьшим 
значением ключа. 
2.
Выбранный элемент меняется местами с первым элементом 
массива. 
После этого массив можно рассматривать как состоящий из двух час-
тей: левой – уже отсортированной, и правой – неотсортированной. Повтор-
ное применение шагов 1 и 2, но уже к неотсортированной части массива при-
19 / 23

---

20 
ведет к ее уменьшению на один элемент и, соответственно, к увеличению на 
один элемент отсортированной части массива. Очевидно, что сортировка все-
го массива требует чтобы действия 1 и 2 были выполнены N – 1 раз. 
Функция, реализующая алгоритм сортировки простым выбором, пред-
ставлена в листинге 2.4. Эта функция имеет только один параметр – сорти-
руемый массив.