ВУЗ:
Составители:
Рубрика:
бинарного
поиска
необходимо,
чтобы
массив
был
упорядочен.
Следовательно,
если
исходный
набор
не
был
упорядочен,
сортировка
данных
должна
предшествовать
бинарному
поиску.
Алгоритмы
сортировки
разделяются
на
две
категории.
При
выполнении
внутренней
сортировки
(intemal
зоп)
предполагается,
что
все
данные
находятся
в
оперативной
памяти
компьютера.
Мы
будем
рассматривать
только
алгоритмы
внутренней
сортировки.
При
выполнении
внешней
сортировки
(extemal
воп)
данные
могут
храниться
на
вспомогательных
запоминающих
устройствах,
например
на
жестком
диске.
Упорядочивать
можно
целые
числа,
строки
символов
и
даже
объекты.
Легко
представить
себе
результаты
сортировки
набора
целых
чисел
или
строк.
Однако
для
набора
объектов
эта
операция
непривычна.
Если
каждый
объект
содержит
только
одну
переменную-член,
то
их
сортировка
ничем
не
отличается
от
сортировки
целых
чисел.
Однако
если
в
объектах
содержатся
несколько
данных-членов,
нужно
указать,
какая
переменная
определяет
порядок
следования
объектов.
Эта
переменная-член
называется
ключом
сортировки
(5011
key).
Например,
если
объекты
хранят
информацию
о
людях,
их
можно
упорядочить
по
имени,
возрасту
или
почтовому
индексу.
Независимо
от
выбора
ключа
сортировки
алгоритм
сортировки
упорядочивает
все
объекты
по
значению
этой
переменноЙ-члена.
Для
простоты
будем
предполагать,
что
сортировка
применяется
к
числам
или
символам.
Все рассматриваемые
алгоритмы
ориентируются
на
возрастающий
порядок.
Изменить
порядок
на
убывающий
довольно
просто.
В
каждом
примере
предполагается,
что
данные
хранятся
в
массиве.
Представьте
себе
данные,
которые
можно
проверять
все
сразу.
Для
их
упорядочения
можно
было
бы
выбрать
наибольший
элемент,
поставить
его
на
свое
место,
затем
найти
следующий
наибольший
элемент,
поставить
его
на
свое
место
и.
т
.д.
Карточным
игрокам
этот
процесс
напоминает
перетасовку
карт
в
определенном
порядке.
Этот
интуитивный
алгоритм
формализуется
с
помощью
сортировки
методом
выбора
(selection sort).
Чтобы
упорядочить
массив
в
возрастающем
порядке,
нужно
выбрать
наибольший
элемент.
Поскольку
наибольший
элемент
нужно
поставить
в
самый
конец
массива,
его
нужно
поменять
местами
с
последним
элементом,
даже
если
эти
элементы
идентичны.
Теперь,
игнорируя
последний
(наибольший)
элемент
массива,
выполним
поиск
наибольшего
элемента
в
оставшейся
части
массива
и
поменяем
его
местами
с
предпоследним
элементом
исходного
массива.
Этот
процесс
продолжается
до
тех
пор,
пока
не
будут
найдены
и
переставлены
n-l
элемент
из
п
элементов
массива.
Оставшийся
элемент,
стоящий
первым,
не
нарушает
порядок
и
поэтому
не
рассматривается.
На
рис.4
показан
пример
сортировки
методом
выбора.
Среди
пяти
целых
чисел
выбирается
наибольшее
-
число
37,
которое
меняется
местами
с
последним
элементом
массива
-
числом
13.
(Числа,
стоящие
на
правильных
местах,
выделены
полужирным
шрифтом.
Это
соглашение
16
Страницы
- « первая
- ‹ предыдущая
- …
- 15
- 16
- 17
- 18
- 19
- …
- следующая ›
- последняя »
