Я пытаюсь реализовать сортировку по американскому ведру. Wiki говорит: «Во-первых, нужно подсчитать количество объектов, которые упадут в каждую корзину, а во-вторых, чтобы поместить каждый объект в свое ведро».
На втором этапе при размещении объектов в соответствующих корзинах нужно ли мне использовать вспомогательный массив? Есть ли способ сделать это, заменив элементы массива за линейное время?
Предполагая, что вы имеете в виду http://en.wikipedia.org/wiki/American_flag_sort, тогда как в статье указывает вверху, вы можете запустить это на месте (хотя тогда это не стабильная сортировка). Основная идея состоит в том, чтобы иметь указатель на первый непрочитанный элемент, изначально равный 0, и временную переменную для хранения одного элемента.
В качестве первого шага вы смотрите на указатель и берете предмет, на который он указывает. Теперь вы можете использовать индексы, чтобы поставить его на место. Если его место не является той позицией, с которой вы изначально читали, вы собираетесь перезаписать другой предмет, поэтому вы меняете предмет, который вы взяли, на предмет, который вы бы перезаписали, и теперь вы держите другой временный предмет - и посмотрите вверх, чтобы увидеть куда он должен идти и продолжать.
В конце концов вы поместили что-то в то место, откуда читали, так что вы можете увеличивать указатель чтения, пропуская области, где вы уже написали отсортированные элементы, выбрать другой элемент и продолжать, пока все не будет отсортировано.
