Вход
Войти

Галерея диаграмм связей алгоритм сортировки структуры данных

алгоритм сортировки структуры данных

Алгоритмы сортировки часто рассматриваются в структурах данных, включая сортировку вставкой, сортировку Хилла, пузырьковую сортировку и почти все алгоритмы сортировки. Сортировка — это процесс перестановки элементов в таблице так, чтобы элементы в таблице соответствовали порядку возрастания или убывания ключевых слов. .

Отредактировано в 2023-09-18 01:41:47

WSysQn6v

Недавние работы Смотреть другие работы>>

алгоритм сортировки структуры данных

WSysQn6v

Недавние работы Смотреть другие работы>>

Рекомендовано вам
Структура

Интеллект-карта структуры данных и алгоритма
- 2
WSysQn6v
Алгоритм поиска структуры данных
- 2
WSysQn6v
Структуры данных и алгоритмы
- 1
WSysQn6v
Реализация структуры данных и анализ алгоритмов
- 2
WSysQn6v
структура данных
- 1
WSysQn6v
Структуры данных – стеки и очереди
- 2
WSysQn6v
Карта структуры данных
- 2
WSysQn6v
Структура данных – линейная таблица
- 2
WSysQn6v
Структура данных 2 (обновление
- 1
WSysQn6v
Общие основы работы с компьютером
- 1
ArteVeloce

Сортировать

Основные понятия сортировки

Сортировать

Переставьте элементы в таблице так, чтобы элементы в таблице удовлетворяли процессу увеличения или уменьшения по ключевому слову.

стабильность алгоритма

Если в алгоритме сортировки есть два элемента Ri и Rj, соответствующие им ключевые слова keyi=keyj, и Ri находится перед Rj перед сортировкой, если после сортировки Ri все еще находится перед Rj, этот алгоритм стабилен. В противном случае оно нестабильно.

Стабильность не может служить показателем качества алгоритма.

сортировка вставкой

сортировка прямой вставкой

Разделите последовательность на две части, упорядоченную и неупорядоченную, и каждый раз вставляйте соответствующие биты в упорядоченную часть.

принцип

Статус сортируемого списка L [1···n] в определенный момент в ходе определенного процесса сортировки

1. Найдите позицию k вставки L(i) в L[1···i-1]

2. Переместить все элементы в L[k···i-1] на одну позицию назад.

3) Скопируйте L(i) в L(k)

производительность

Пространственная сложность O(1)

Лучшая временная сложность — O(n)

Наихудшая временная сложность O(n^2)

Средняя временная сложность O(n^2)

Стабилизировать

Быть применимым

список последовательностей, связанный список

сортировка половинной вставкой

Сортировка прямой вставкой с использованием двоичного поиска

Количество сравнений элементов

производительность

Пространственная сложность O(1)

лучшая временная сложность

Наихудшая временная сложность O(n^2)

Средняя временная сложность O(n^2)

Стабилизировать

Быть применимым

Таблица последовательности

Сортировка холмов

Таблица сортировки разделена на несколько подтаблиц, каждая подтаблица непосредственно вставляется в сортировку, и, наконец, выполняется вся сортировка вставкой.

производительность

Пространственная сложность O(1)

Временная сложность O(n^1,3)

Оценивать

Наихудшая временная сложность O(n^2)

нестабильный

Быть применимым

Таблица последовательности

сортировка местами

Пузырьковая сортировка

Начиная с начала, сравните каждую пару соседних элементов и переместите их назад, если они больше. После сравнения самый большой элемент окажется в конце. Повторите описанный выше процесс, не лучше, чем самый большой, и продолжайте повторять, чтобы получить последовательность.

производительность

Пространственная сложность O(1)

лучшая временная сложность

Когда последовательность упорядочена, количество сравнений равно n-1, количество ходов равно 0, а временная сложность равна O(n).

Наихудшая временная сложность O(n^2)

Когда последовательность обратная

Средняя временная сложность O(n^2)

Стабилизировать

Быть применимым

список последовательностей, связанный список

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

1. Сначала возьмите число из последовательности в качестве базового числа. 2. Процесс разделения: поместите все числа, большие, чем это число, справа от него, а все числа, меньшие или равные ему, поместите слева. 3． Повторяйте второй шаг для левого и правого интервалов, пока в каждом интервале не останется только одно число.

В худшем случае каждый раз выбранное среднее число оказывается самым большим или наименьшим элементом в текущей последовательности. Быстрая сортировка таблицы данных длины n требует n делений, что увеличивает временную сложность всего алгоритма сортировки O(n^2)

производительность

космос

Наихудшая пространственная сложность O(n)

средняя космическая сложность

время

лучшая временная сложность

Худшая временная сложность

О(п^2)

средняя временная сложность

нестабильный

Быть применимым

Таблица последовательности

сортировка выбором

Простая сортировка выбором

Каждый раз выбирается наименьшая и обменивается с указанной позицией.

Количество сравнений n(n-1)/2 Временная сложность O(n^2)

производительность

Пространственная сложность O(1)

Лучшая временная сложность — O(n^2).

Наихудшая временная сложность O(n^2)

Средняя временная сложность O(n^2)

нестабильный

Быть применимым

список последовательностей, связанный список

Сортировка кучей

куча

Последовательность из n ключевых слов L[1 ... n] называется кучей тогда и только тогда, когда последовательность удовлетворяет:

небольшая корневая кучка

дагендуй

Сортировать

Сначала создайте столбец, который нужно отсортировать как кучу, выберите самый большой (или наименьший) элемент в куче, который является верхним элементом кучи, и выведите его. После вывода верхнего элемента кучи нижний элемент кучи отправляется на вершину кучи, а свойства кучи уничтожаются. Верхний элемент кучи корректируется вниз, чтобы снова сформировать кучу, и верхний элемент кучи выводится повторно.

Построить кучу

1. Построить двоичное дерево в порядке последовательности.

{5, 2, 6, 0, 3, 9, 1, 7, 4, 8}

2. Найдите ⌊n/2⌋ и настройте дерево, используя его в качестве корневого узла.

3. Найдите узел перед предыдущим, продолжайте настройку и повторите. В процессе корректировки убедитесь, что скорректированная куча по-прежнему соответствует правилам.

вставлять

Добавьте узел к последнему узлу и отрегулируйте его снизу вверх.

удалить

Удалить можно только корневой узел

Замените последний узел корневым узлом и отрегулируйте его сверху вниз.

Сортировка слиянием

двусторонняя сортировка слиянием

Таблица, подлежащая сортировке, содержит n записей, которые можно рассматривать как n упорядоченных подтаблиц. Каждая подтаблица имеет длину 1, а затем они сортируются попарно. Получите ⌈n/2⌉ упорядоченные списки длиной 2 или 1, а затем объедините их в две лунки. Повторяйте это, пока они не объединятся в упорядоченный список длины n. Обратите внимание на разницу между рекурсивным и нерекурсивным слиянием.

производительность

Пространственная сложность O (n)

лучшая временная сложность

Худшая временная сложность

средняя временная сложность

Стабилизировать

Быть применимым

Таблица последовательности

Поразрядная сортировка

Поразрядная сортировка предполагает сначала сортировку по нижнему порядку, затем сборку по высшему порядку, а затем сбор и т. д. до самого высокого порядка;