Сортированный массив
| Сортированный массив | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Тип | Множество | |||||||||||||||||||||||
| Изобретенный | 1945 | |||||||||||||||||||||||
| Изобретён | Джон фон Нейман | |||||||||||||||||||||||
| ||||||||||||||||||||||||
— Сортированный массив это структура данных массива , в которой каждый элемент сортируется в числовом, алфавитном или каком-либо другом порядке и размещается по равноотстоящим адресам в памяти компьютера. Обычно он используется в информатике для реализации статических таблиц поиска для хранения нескольких значений одного и того же типа данных . Сортировка массива полезна для организации данных в упорядоченной форме и быстрого их восстановления.
Обзор
[ редактировать ]Сортированные массивы представляют собой наиболее компактную структуру данных с наилучшей локальностью ссылок для последовательно хранящихся данных. [ нужна ссылка ]
Элементы в отсортированном массиве находятся с помощью двоичного поиска за O(log n ); таким образом, отсортированные массивы подходят для случаев, когда необходимо иметь возможность быстро искать элементы, например, в виде набора или мультимножества структуры данных . Эта сложность поиска такая же, как и для самобалансирующихся двоичных деревьев поиска .
В некоторых структурах данных используется массив структур. В таких случаях одни и те же методы сортировки могут использоваться для сортировки структур по некоторому ключу в качестве элемента структуры; например, сортировка записей учащихся по номерам, именам или оценкам.
Если вы используете отсортированный динамический массив , то можно вставлять и удалять элементы. Вставка и удаление элементов в отсортированном массиве выполняется за O( n ) из-за необходимости сдвинуть все элементы, следующие за элементом, который нужно вставить или удалить; для сравнения: самобалансирующееся двоичное дерево поиска вставляет и удаляет в точке O(log n ). В случае, когда элементы удаляются или вставляются в конец, отсортированный динамический массив может сделать это за амортизированное время O(1), в то время как самобалансирующееся двоичное дерево поиска всегда работает за O(log n ).
Элементы в отсортированном массиве можно искать по их индексу ( произвольный доступ ) за время O(1), операция занимает время O(log n ) или O( n ) для более сложных структур данных.
История
[ редактировать ]Джон фон Нейман написал первую программу сортировки массивов ( сортировку слиянием ) в 1945 году, когда первый компьютер с хранимой программой . еще создавался [1] [2]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Дональд Кнут , Искусство компьютерного программирования , том. 3. Аддисон-Уэсли
- ^ Концепции операционной системы Питера Б. Галвина . WILEY-INDIA Pvt. ограничено. ISBN 978-81-265-2051-0 .