1
Предположим, что сравнение элементов в массиве принимает O (n), возможно ли отсортировать массив в O (n), когда элементы первой половины массива меньше другой половины?Будет ли работать сортировка массива в O (n), когда половина массива меньше другой?
Я думаю, да, это упростит сортировку, потому что элементы arent смешиваются так сильно. Поэтому мы позаботимся о первом тайме, меньшем, просто сравниваем один элемент с другим и сортируем. Затем сделайте то же самое со второй половиной. Разве это не работает в O (n)?
Когда вы имеете в виду, что первая половина меньше, чем другая половина, вы имеете в виду, что все элементы меньше, чем во второй половине? Эти элементы уже отсортированы самостоятельно или просто распределены случайно? IOW: это так: {1, 2, 3, 4, 5, 400, 100, 200, 500, 300} или вот так: {5, 2, 1, 4, 3, 400, 100, 200, 500 , 300}? Если это похоже на второе, я бы предположил, что нет никакой пользы для сортировки. –
@blahfunk: Да, все элементы меньше, чем во второй половине. Элементы не сортируются сами по себе. Если бы они были тогда, все элементы были бы отсортированы от начала до конца, верно? : D – roblind
Вы могли бы _possibly_ оптимизировать его (но не обязательно), если бы знали, что он будет разбиваться по середине во время программирования. Но, скорее всего, это будет анти-оптимизация, чтобы попытаться что-то сделать во время выполнения. Итак, это похоже на XY Problem-ish. Это также зависит от таких факторов, как алгоритм сортировки, который вы используете, или если вы сортируете новый контейнер (который не является точно _sorting_, но может принести пользу). –