Вот ваш оригинальный алгоритм с некоторыми исправлениями и стилистическими улучшениями:
public class MergeSort {
public static void main(String[]args) {
int[] nums = {12,9,4,99,120,1,3,10};
mergeSort(nums);
System.out.println(java.util.Arrays.toString(nums));
// "[1, 3, 4, 9, 10, 12, 99, 120]"
}
static void mergeSort(int[] arr) {
mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
}
static void mergeSort(int[] arr, int low, int high, int[] buff){
if (low >= high) {
return;
}
int mid = (low + high) >>> 1;
mergeSort(arr, low, mid, buff);
mergeSort(arr, mid+1, high, buff);
for (int left = low, right = mid + 1, i = low; i <= high; i++) {
if (right > high || left <= mid && arr[left] <= arr[right]) {
buff[i] = arr[left++];
} else {
buff[i] = arr[right++];
}
}
for (int i = low; i <= high; i++) {
arr[i] = buff[i];
}
}
}
В отличие от реализации Eyala, где роли src и dst меняются местами по уровням рекурсии, здесь мы всегда сортируем один и тот же объект массива arr, а объект массива buff равен всегда используется только как временный буфер для слияния (и, следовательно, после фазы слияния существует фаза копирования). Это все еще O(N log N), но более продвинутая реализация Eyal'а будет постоянным улучшением.
В цикле объединения
По существу, у вас есть индекс left для левого подмассива и индекс right для правого подмассива, и вы выбираете правый элемент из left или right для помещения в buff.
Допустимый диапазон элементов (включая границы):
left = low...mid для левого подмассива right = mid+1...high для правого подмассива
Чтобы оценить, какой элемент выбрать, рассмотрите условие, при котором выбран элемент left. Это происходит, когда:
- Больше нет элементов для выбора из правого подмассива (т. Е.
right > high)
- ИЛИ (условно) все еще есть элемент, который можно выбрать из левого подмассива (т. Е.
left <= mid) и (условно) этот элемент меньше или равен элементу из правый подмассив (т.е. arr[left] <= arr[right]).
Здесь важно использовать операторы условного и && ( JLS 15.23 ) и условного или || ( JLS 15.24 ) и заказать их условия соответственно. В противном случае вы получите ArrayIndexOutOfBoundsException.
Смежные вопросы
Нахождение среднего между двумя числами
Обычно можно увидеть следующее:
int mid = (low + high) / 2; // BROKEN! Can result in negative!
Проблема заключается в том, что в настоящее время массивы / списки и т. Д. Могут легко превышать 2 30 элементов, а приведенное выше может вызвать переполнение и привести к отрицательному числу.
Новая идиома, предложенная Джошем Блохом, такова:
int mid = (low + high) >>> 1; // WORKS PERFECTLY!
При этом используется беззнаковый оператор смещения вправо ( JLS 15.19 ); он корректно обрабатывает любые переполнения при добавлении.
Ссылки
Похожие вопросы
В объявлениях массива
Не создавайте привычку объявлять массивы так:
int x[];
Вместо этого вы должны поставить скобки с типом , а не с идентификатором :
int[] x;
Смежные вопросы