Алгоритм слияния в C: как это работает? [закрытый]
4 ответа
Код
В этом коде используется так называемый оператор постинкремента и тернарный / условный оператор (более подробную информацию см. В приложении).
Более подробная версия может выглядеть примерно так:
if (in1[i1] < in2[i2]) {
out[i] = in1[i1];
i++;
i1++;
} else {
out[i] = in2[i2];
i++;
i2++;
}
Алгоритм
Если элементы в in1 и in2 находятся в отсортированном порядке, то фрагмент служит основная часть алгоритма слияния для объединения двух отсортированных входных буферов в один отсортированный выходной буфер.
Перед сравнением необходимо убедиться, что против i1 и i2 входят в границу для in1 и in2 соответственно. ] in1 [i1] in2 [i2] .Тогда in1 [i1] - следующий доступный наименьший элемент в in1 , и аналогично in2 [i2] - следующий доступный наименьший элемент в in2 .
Без ограничения общности предположим, что in1 [i1] in1 меньше, чем следующий наименьший элемент из in2 , и с in1 [i1 ++] в правой части присваивания, мы выбираем следующее наименьшее значение из in1 и продвигаем его указатель к следующему доступному значению (если есть). С помощью out [i ++] в левой части присваивания мы присваиваем полученное значение слоту в выходном буфере и перемещаем его указатель на следующий доступный слот (если есть).
Псевдокод более высокого уровня общего алгоритма слияния, использующий абстрактную структуру данных, подобную Queue , вместо массивов с соответствующими индексами указателей (для ясности!), Может выглядеть примерно так:
procedure MERGE(Queue in1, in2) : Queue
// given sorted queues in1, in2, return a merged sorted queue
INIT out IS Empty-Queue
WHILE in1.notEmpty() AND in2.notEmpty()
IF in1.peek() < in2.peek()
out.enqueue(in1.dequeue())
ELSE
out.enqueue(in2.dequeue())
// at this point, at least one of the queue is empty
// dump in1 to out in case it's not empty
WHILE in1.notEmpty()
out.enqueue(in1.dequeue())
// dump in2 to out in case it's not empty
WHILE in2.notEmpty()
out.enqueue(in2.dequeue())
RETURN out
См. Также
Приложение A: Тернарный / условный оператор
По сути, такое выражение, как это:
condition ? trueExpr : falseExpr
сначала вычисляет условие , и если оно истина , оно вычисляет trueExpr , значение которого становится значением всего выражения.Если вместо условие равно false , оператор вместо этого вычисляет falseExpr , значение которого становится значением всего выражения.
Связанные вопросы
- Как работает тернарный оператор?
- В троичную или нет?
- Какой стиль кодирования вы используете для тернарного оператора?
Приложение B: оператор пост-инкремента
В выражении, таком как i ++ , используется то, что называется оператором пост-инкремента. Оператор увеличивает i , но значением этого выражения является значение i перед приращением. Напротив, значение выражения предварительного приращения (например, ++ i ) является значением i после приращения.
Есть также пре-декремент (например, - i ) и постдекремент (например, i - ).
Связанные вопросы
О ловушках вроде i = i ++; (большинство из них - Java, но применимо и к другим языкам):
У вас уже есть отличный ответ, объясняющий синтаксис, но пока никто не сказал вам, что на самом деле делает код.
Если у вас есть два входных массива, in1 и in2, и индекс в каждом, то эта строка кода находит наименьший элемент из двух текущих элементов и помещает его в выходной массив. Затем он перемещает индекс этого входного массива, а также индекс в выходной массив.
Если два входа представляют собой отсортированные массивы, и если эта строка выполняется в цикле, она выполняет слияние двух входов за время O (n). Эта операция используется повторно при выполнении сортировки слиянием .
Как вы видели, это еще одна вещь, которая сбивает с толку новых (или плохо знакомых с языком) разработчиков. Людям с C особенно нравится сводить все в одну строку. Он выглядит элегантно. Как в C, так и в C ++ есть определенные идиомы или обороты, которые мы легко узнаем. Когда вы сталкиваетесь с одним из них, нет ничего плохого в том, чтобы записать (на бумаге или в рабочем файле) его длинную версию (как в ответе @polygenelubricants), чтобы затем у вас была возможность выработать общее значение из него (как в ответе @Mark Byers). Но оставьте это коротким, как только вы это поймете.