Как правильно и без проблем упорядочить стопку неупорядоченных записей наблюдений?
Сначала сравните, какая запись раньше, затем переместите всю запись и посмотрите своими глазами, как устроены данные.
Общие алгоритмы и численные вычисления
После того, как была сделана серия фотографий, карта записи была зашифрована. Каждая карта имеет номер и идентификационную букву. Если вы хотите отсортировать их от меньшего к большему, вы не сможете потерять две карты с одинаковым номером.
Угадай сначала
Значение сортировки обеих записей наблюдений равно 2. Следует ли удалить одну из них при сортировке?
Показать ответ и объяснение
Нет, обе записи должны быть сохранены. — Идентичные значения не означают идентичные записи; сортировка только меняет порядок и не отвечает за дедупликацию.
Тогда соедините опыт и науку
Давайте сначала разложим записи
Буквы на каждой карточке фиксируют личность, а цифры служат основой для сортировки. Одно и то же число может появляться несколько раз, и запись нельзя удалить.
Входные данные представляют собой набор записей, а не просто разные числа.
Выполняйте только одно конкретное действие за раз
Ход движения, сравниваемые или обмениваемые карты выделяются оранжевым цветом. Программа просматривает значения только на этапе сравнения и перемещает полные записи на этапе обмена.
Сравнить → решить, стоит ли обменивать
Если изменить подход, результат будет тот же
В оригинальной книге предусмотрен попарный обмен, сначала нахождение наименьшего, а также быстрая сортировка разделов. Разные шаги могут получать одно и то же возрастающее значение, но записи с одинаковым значением могут не сохранять первоначальный порядок.
SIMPLE / BETTER / QUICKSORT
По мере увеличения данных количество шагов становится более важным.
Количество сравнений первых двух методов увеличивается с увеличением N²; быстрая сортировка обычно составляет N log N, но не гарантируется, что она будет самой быстрой для каждого входного сигнала. В этом примере счетчик — это фактическое измерение, а не количество секунд работы машины.
Следует различать количество сравнений, обменов и фактические затраты времени.
Развёрнутые вычисления
排序后：key₁ ≤ key₂ ≤ … ≤ keyₙ 排序前后：每条Записывать的身份与内容保持完整
Это класс правил алгоритма, и не существует астрономической формулы, которую можно было бы получить путем замены. Сравнение определяет порядок, и обмен должен переместить всю запись; одно и то же значение ключа не означает, что запись можно удалить.
попробуй
Используйте один и тот же набор карточек для сравнения трех методов; перетащите прогресс на 100%, проверьте, что числа расположены в порядке возрастания и что записи A-H все еще присутствуют.
Нет необходимости запоминать символы
- N
- Количество записей, экран для этого урока - 8
- Сравнивать
- Просмотр порядка двух значений; быстрая сортировка также сравнивается с базовым значением
- обмен
- Поменяйте местами две полные записи
- базовая стоимость
- Быстрая сортировка используется для разделения значений с обеих сторон.
- стабильность
- Сохраняют ли записи с одинаковым значением сортировки исходный относительный порядок
Алгоритм, точность и область применения
Оригинал книги, глава 6, печатные страницы 55–58, таблица 6.А. Реализованы три алгоритма: SIMPLE SORT сравнивает и обменивает пары попарно в соответствии с передней и задней позициями, BETTER сначала находит оставшееся минимальное значение, а затем осуществляет обмен, а QUICKSORT использует разделение по двойному указателю и явный стек на основе значения среднего элемента. В этом уроке опускаются детали исходного BASIC, оптимизирующего порядок стека в соответствии с длиной интервала, и сохраняются результаты разделения и фактические трассировки сравнения/обмена; он не утверждает, что худшим случаем быстрой сортировки является N log N. Номера демонстрационных карточек не имеют реальных единиц измерения даты, буквы только обозначают личность. Проценты прогресса соответствуют дискретным шагам алгоритма и показывают истинное количество шагов. Сравнения и обмены учитываются отдельно, за исключением беговых секунд; порядок записей с одинаковым значением не может быть стабильным. Введение в сортировку строк ASCII в конце главы объясняется в тексте, а взаимодействие реализует только числовую сортировку. Локальный AA+ не нашел специального модуля для сортировки, и результаты были проверены с использованием независимой собственной числовой сортировки и инвариантов пошаговой перестановки.
мое понимание, проверка
При сравнении двух записей необходимо ли немедленно обмениваться данными?
неопределенный — Сравнение и обмен — разные действия, и обмен ими происходит только при выполнении условий алгоритма.
Если числа после сортировки совпадают, значит ли это, что порядок записей с одинаковым значением тоже должен быть одинаковым?
неопределенный — Сохранение последовательности записей с одинаковым значением требует стабильности; три реализации в этом уроке не обеспечивают стабильных гарантий сортировки.
Можно ли напрямую использовать количество секунд, измеренное на исходном компьютере, как время, затраченное сегодняшней веб-страницей?
Не мочь — Аппаратное обеспечение, языки и реализации различаются; в этом уроке сравнивается количество воспроизводимых операций и количество секунд без повторного использования старой машины.
Сортировка сначала гарантирует, что записи полны и находятся в правильном порядке, а затем сравнивает эксплуатационные затраты; записи с одинаковыми значениями нельзя выбрасывать как повторяющийся мусор.
Jean Meeus · Astronomical Algorithms, 2nd ed. · Нет. 6 глава
Общие алгоритмы и численные вычисления · Все интерактивные курсы