Какая из лучших сортировочных методик для почти отсортированного списка и почему? Для списка многих элементов я обнаружил, что быстрый вид полезен. Но какой вид имеет лучшее время работы, когда он уже отсортирован?Лучшая техника сортировки для почти отсортированного списка
Вставка Сортировка имеет линейную производительность, когда список почти отсортирован.
Проверил: http://www.sorting-algorithms.com/nearly-sorted-initial-order
вставки помещает элемент в правильном положении, учитывая относительный порядок, следовательно, необходимо п - 1 итераций. Другие виды, такие как quick sort, снова пытаются отсортировать отсортированный сегмент снова, поскольку он не знает относительного упорядочения (т. Е. Если сегмент уже отсортирован).
Ваш вопрос слишком широк, однако если массив ввода уже отсортирован, сортировка вставки выполняет всего лишь как п-1 сравнение Thats сделать сортировку вставки более эффективным
вы можете найти этот документ полезным Best sorting algorithm for nearly sorted lists
поблагодарить u ..... :) –
Это теоретический вопрос CS, но он не является математически точным, поэтому на него нельзя легко ответить. Не могли бы вы точно определить, что вы подразумеваете под «почти сортировкой»? Например, это «почти отсортированный» список, в котором два элемента заменены, но все в порядке? Это тот, в котором 90% или более элементов не нужно перемещать, чтобы завершить сортировку списка? – Kevin
Прошу прощения за то, что я точно не объяснил вопрос. Я говорю о списке, который почти как 95% элементов не нужно перемещать для сортировки. @Kevin –