Ответ 1
Сверху моей головы...
Создайте "скользящее окно" размера 2d.
Запустите его на [0,2d). Сортировка элементов в окне; теперь элементы с 0 по d-1 гарантированы как правильные.
Сдвиньте окно вперед на d, так что теперь он [d, 3d). Отсортируйте эти элементы, гарантируя правильность элементов d-2d-1.
Сдвиньте вперед другой d, так что теперь его [2d, 4d]. Сортируйте их. И так далее.
Каждый вид O (d log d), и для достижения конца требуется n/d шагов, поэтому это O (n/d * d log d) = O (n log d). Если d постоянна, то O (n).
[править]
Вы хорошо отмечаете комментарий; Я не доказывал, что каждая итерация сохраняет свойство, что каждый элемент находится внутри d единиц его правильного положения.
Итак...
Лемма: если A - массив с тем свойством, что каждый элемент находится внутри d единиц его правильного положения, и вы сортируете любую непрерывную подпоследовательность внутри A для создания массива A ', то каждый элемент из A' находится внутри d единиц его надлежащего положения.
Доказательство. Так как это лемма о свойствах сортировки (не производительности), не имеет значения, какой алгоритм мы используем для сортировки. Поэтому используйте сортировку пузырьков. Найдите любые два элемента в подпоследовательности, которые вышли из строя, и замените их. Есть только три случая: оба элемента находятся перед их правильными позициями в массиве; оба находятся после их правильных позиций в массиве; или они находятся между их соответствующими позициями в массиве.
Например, предположим, что A [i] принадлежит в позиции я 'и A [j] принадлежит в позиции j', я < j, но A [i] > A [j]. Отсюда следует, что я ' > j' (потому что это то, где элементы "принадлежат", и A [i] > A [j]). Случай 1: предположим, что я 'и j' больше, чем я и j; то есть порядок переходит я < j < j ' я'. Но по условию я 'является только d единицами из i, поэтому весь этот диапазон составляет всего d единиц в ширину в лучшем случае. Таким образом, j также находится внутри d единиц я 'и я находится внутри d единиц j', поэтому, когда мы меняем A [i] на A [j], оба элемента все еще находятся в пределах d от того, где они принадлежат. Анализ для случая 2 и случая 3 аналогичен.
Таким образом, каждый шаг сортировки пузырьков - на любой подпоследовательности A - сохранит искомое свойство, из которого следует, что вся сортировка пузырьков сохранит искомое свойство, из которого следует, что любой вид сохранит желаемое свойство. Q.E.D.