Так что, я думаю, это потому, что он просто сравнивает A [k] и A [k-1], и делает реализацию в одной развертке, но до сих пор неясно. Может кто-нибудь объяснить лучше. БлагодаряПочему сортировка вставки - лучший алгоритм для отсортированного или почти отсортированного массива?
Это link показывает графическое представление алгоритма сортировки с различными типами набора данных. Как вы можете видеть, при сортировке данных сложность алгоритма сводится к N. Это эквивалентно количеству элементов в качестве входных данных.
Предоставленная ссылка дает четкое представление о том, как ее эффективность.
Спасибо! что помогло много – Katrina
Приветствую вас, можете ли вы принять ответ и закрыть вопрос? –
Вы ответили на свой вопрос: для сортированного массива для сортировки вставки потребуется всего лишь O(n) проходов для завершения. Сравните это с алгоритмом сортировки и разделения, таким как сортировка слияния, которая принимает O(n*lgn). Для любого нетривиального значения n алгоритму деления и покоя потребуется много проходов O(n), даже если массив будет почти полностью отсортирован, тогда как для сортировки вставки может потребоваться лишь несколько.
Общая цель алгоритма сортировки заключается в минимизации количества сравнений. Алгоритмы сортировки имеют нижнюю границу и верхнюю границу числа сравнений (n log n наихудший вариант для сортировки слияния и кучи, n log n средний случай для быстрой сортировки). В наиболее общем случае вы бы пошли с алгоритмом, который, как оказалось, имеет лучшее среднее или лучшее худшее количество сравнений. Однако, когда вы знаете что-то о данных (например, массив уже отсортирован или почти отсортирован), вы можете использовать тот факт, что нижняя граница сортировки вставки намного ниже, чем сортировка «n log n».
Например, если у вас есть массив [1,2,3,4,5,6,7,9], и вам нужно вставить в него 8, вы можете либо вставить его в конец, либо отсортировать массив, используя ваниль n log n sort (что будет делать около 28 сравнений (примерно) для сортировки данных по [1,2,3,4,5,6,7,8,9]). Однако сортировка вставки позволяет вставить 8 в нужное положение только в 8 сравнениях.
Вставка сортировки - это более быстрый и улучшенный алгоритм сортировки, чем сортировка сортировки. При сортировке сортировки алгоритм выполняет все данные через каждый проход, будет ли он уже отсортирован или нет. Однако сортировка вставки работает по-разному, вместо того, чтобы повторять все данные после каждого прохождения, алгоритм проходит только те данные, которые ему нужны, до тех пор, пока отсортированный сегмент не будет отсортирован. Опять же есть две петли, которые требуются для сортировки вставки и, следовательно, две основные переменные, которые в этом случае называются «i» и «j». Переменные 'i' и 'j' начинаются с одного и того же индекса после каждого прохода первого цикла, второй цикл выполняется, только если переменная 'j' больше, чем индекс 0 AND arr [j] < arr [j - 1]. Другими словами, если «j» не достигло конца данных И значение индекса, в котором «j» находится, меньше, чем значение индекса слева от «j», наконец, «j» равно убавления. Пока эти два условия выполняются во втором цикле, он будет продолжать выполнение, это то, что устанавливает сортировку вставки, отличную от сортировки сортировки. Сортируется только данные, которые необходимо сортировать.
Это хороший ответ, но он совершенно неразборчив. Разделите текст на короткие абзацы и отформатируйте примеры кода, используя предоставленные инструменты. Тогда он, скорее всего, привлечет голоса; как минимум. –
хорошо уверен, но я сравнил его с другим algo и я возьму совет ур положительно. –
Анализ производительности на сортированном массиве против альтернатив. Это ответ. – Amit
Возможный дубликат [Какой алгоритм сортировки работает лучше всего в основном отсортированных данных?] (Http://stackoverflow.com/questions/220044/which-sort-algorithm-works-best-on-mostly-sorted-data) – Thilo