Почему худший случай для вставки сортировки n^2? Может ли это быть с бинарным поиском? Минимизируйте поиск местоположения в журнале (n), а затем используйте функцию низкого уровня, например memmove, чтобы минимизировать свопы?Вставка сортировка наихудшего случая
Не может ли это быть с бинарным поиском?
Вам нужно будет отсортировать массив первым использовать бинарный поиск, в качестве двоичного поиска можно только в отсортированном массиве
Редактировать Даже если первая часть массива сортируется. Дело в том, что вы находите позицию для вставки в шаги logn. Тогда вам действительно нужно вставить туда значение. Для этого вам нужно будет переместить все элементы вправо, требуя n шагов в худшем случае.
Вставка сортировки создает сортированная часть массива, по одному элементу за раз. Измененная сортировка вставки может использовать двоичный поиск (а не линейное сканирование), чтобы найти точку вставки для нового элемента, и это то, что предлагает @Taztingo. –
Причина, по которой сортировка вставки является O (n^2), заключается в том, что в худшем случае вам нужно переместить 'n' items' n' раз. Использование 'memmove' для перемещения элементов не изменяет сложность времени. – user3386109
Я голосую, чтобы закрыть этот вопрос как не относящийся к теме, потому что это лучше подходит для [\ [программистов se \]] (http://programmers.stackexchange.com) – sjsam
Если вы внесете какие-либо изменения в свой вопрос , это уже не сортировка вставки. –