Имея два отсортированных массива A и B, где в конце A достаточно места для B, напишите метод для объединения B в A и их сортировки.
После получения этого вопроса самая прямая идея — сравнить элементы в A и B и вставлять их в массивы по порядку, пока не будут пройдены все элементы в A и B. Но в этом есть недостаток: если позиция вставки элемента находится в начале массива A, исходный массив необходимо переместить назад. Это добавляет накладные расходы. Но мы можем использовать другой метод для вставки элементов в конец массива A. Таким образом, элементы не будут перемещаться! Код выглядит следующим образом:
Скопируйте код кода следующим образом: /*
* LastA: фактическое количество элементов в LastB: фактическое количество элементов в b mergeIndex — это фактический размер пространства нового массива
*/
public static void mergeOrder(int[] a, int[] b, intlastA, intlastB) {
int indexA = LastA - 1;
int indexB = последнийB - 1;
int mergeIndex = LastA + LastB - 1;
while (indexA >= 0 && indexB >= 0) {
если (а[индексA] > b[индексB]) {
а[индекс слияния] = а[индексА];
индекс слияния --;
индексА --;
} еще {
а[mergeIndex] = b[indexB];
индекс слияния --;
индексБ --;
}
}
в то время как (индексB >= 0) {
а[mergeIndex] = b[indexB];
индекс слияния --;
индексБ --;
}
}