Алгоритм Mergesort в Java

Question

Я пытался написать алгоритм слияния в Java:

static void merge(int[] sort, int l, int m, int r) {
    int[] cache_array = new int[r - l + 1];
    int l_cache = l;
    int _mid = m + 1;
    for (int i = 0; i < r - l + 1; i++) {
        if (l > m) {
            cache_array[i] = sort[_mid];
            _mid++;
        } else { if (_mid > r) {
            cache_array[i] = sort[l];
            l++;
        } else { if (sort[l] >= sort[_mid]) {
            cache_array[i] = sort[l];
            l++;
        } else { if (sort[_mid] > sort[l]) {
            cache_array[i] = sort[_mid];
            _mid++;
        }}}}
    }
    for (int i = 0; i < cache_array.length; i++) {
        sort[i + l_cache] = cache_array[i];
    }
}

static void mergeSort(int[] sort, int l, int r) {
    if (l < r) {
        int mid = (int)Math.floor((l + r - 1) / 2);
        mergeSort(sort, l, mid);
        mergeSort(sort, mid + 1, r);
        merge(sort, l, mid, r);
    }
}
    
public static void main(String[] args) {
    int[] a = { 2, 1, 4, 5, 73, 74, 7, 5, 64, 2 };
    mergeSort(a, 0, a.length - 1);
    for (int i : a) {
        System.out.println(i);
    }
}

Но он просто сортирует часть массива и заменяет остальную часть нулями. Я попытался изменить cache_array на LinkedList, но ничего не изменилось, и после попытки отладки я тоже ничего не смог найти. Буду признателен, если вы поможете мне и / или покажете другой алгоритм сортировки слиянием, который работает для Java. (Я использовал этот алгоритм, потому что он работал для Python, и поэтому я хотел использовать аналогичный код в Java)

Answer 1

Ошибка в вашем коде трудно обнаружить:

• l oop в вашей merge функции повторяется для i от 0 до r - l + 1 исключено, что приведет к будет правильным, если r и l оставались постоянными в течение l oop, но вы увеличиваете l каждый раз, когда копируете из левой части, уменьшая количество итераций. Как следствие, l oop завершается раньше, оставляя оставшиеся элементы в cache_array с их значением по умолчанию 0.

В коде есть несколько источников путаницы:

• соглашение о включении r в срез сбивает с толку: требуется +1 / -1 корректировка для вычисления длины среза и среднего индекса.
• с использованием Math.floor() - бесполезно: целочисленная арифметика c использует целочисленное деление в java.
• увеличение аргументов l и m сбивает с толку, поскольку они теряют свой смысл при изменении значения. Используйте другие переменные индекса для итерации по массивам.
• добавление { между ключевыми словами else и if вводит ненужные уровни отступа.
• последнее условие противоположно предыдущий: вы должны просто опустить его. Обратите внимание, что если бы элементы массива были значениями с плавающей запятой, оба условия могли бы быть ложными для значений NaN, а некоторые элементы cache_array остались бы нетронутыми. Это последнее условие может вызвать ошибки в этом случае.

Вот измененная версия:

// merge adjacent slices of the `sort` array.
// left slice has elements from `l` included to `m` excluded
// right slice has elements from `m` included to `r` excluded
static void merge(int[] sort, int l, int m, int r) {
    int len = r - l;
    int[] cache_array = new int[len];
    for (int i = 0, ll = l, mm = m; i < len; i++) {
        if (ll >= m) {
            cache_array[i] = sort[mm];
            mm++;
        } else
        if (mm >= r) {
            cache_array[i] = sort[ll];
            ll++;
        } else
        if (sort[ll] >= sort[mm]) {
            cache_array[i] = sort[ll];
            ll++;
        } else {
            cache_array[i] = sort[mm];
            mm++;
        }
    }
    for (int i = 0; i < len; i++) {
        sort[l + i] = cache_array[i];
    }
}

static void mergeSort(int[] sort, int l, int r) {
    if (r - l > 1) {
        int mid = l + (r - l) / 2;
        mergeSort(sort, l, mid);
        mergeSort(sort, mid, r);
        merge(sort, l, mid, r);
    }
}
    
public static void main(String[] args) {
    int[] a = { 2, 1, 4, 5, 73, 74, 7, 5, 64, 2 };
    mergeSort(a, 0, a.length);
    for (int i : a) {
        System.out.println(i);
    }
}

Answer 2

Я обычно реализую это так:

/// <summary>
/// Mergesort
/// best-case: O(n* log(n))
/// average-case: O(n* log(n))
/// worst-case: O(n* log(n))
/// </summary>
/// <returns>The sorted array.</returns>
/// <param name="array">array.</param>
public static int[] MergeSort(int[] array) {
        //  Exit condition for recursion
        if (array.length <= 1) return array;
        //  Middle index of list to sort
        int m = array.length / 2;
        //  Define left and right sub-listså
        int[] left_array = new int[m];
        int[] right_array = new int[array.length - m];
        //  Initialize left list
        for (int i = 0; i < m; i++) left_array[i] = array[i];
        //  Initialize right list
        for (int i = m, x = 0; i < array.length; i++, x++) right_array[x] = array[i];
        //  Recursively sort left half of the list
        left_array = MergeSort(left_array);
        //  Recursively sort right half of the list
        right_array = MergeSort(right_array);
        //  Merge sorted sub-lists
        return Merge(left_array, right_array);
}
/// <summary>
/// Merge the specified left_array and right_array.
/// </summary>
/// <returns>The merge.</returns>
/// <param name="left_array">Left array.</param>
/// <param name="right_array">Right array.</param>
public static int[] Merge(int[] left_array, int[] right_array) {
        int[] m = new int[left_array.length + right_array.length];
        int index_l = 0;
        int nl, nr;
        nl = left_array.length - 1;
        nr = right_array.length - 1;
        for (int i = 0; i <= nl + nr + 1; i++) {
                if (index_l > nl) {
                        m[i] = (right_array[i - index_l]);
                        continue;
                }
                if (index_l < i - nr) {
                        m[i] = (left_array[index_l]);
                        index_l++;
                        continue;
                }
                if (left_array[index_l] <= (right_array[i - index_l])) {
                        m[i] = (left_array[index_l]);
                        index_l++;
                } else {
                        m[i] = (right_array[i - index_l]);
                }
        }
        return m;
}

Несколько месяцев go Я написал все стандартные алгоритмы сортировки, и это то, что я получил. Немного неточно, но просто чтобы увидеть, как работает эта реализация. Остальные алгоритмы здесь.

Чтобы достичь порядка убывания, я думаю, вам просто нужно поменять местами операторы сравнения.

Контрольный показатель

Answer 3

Вот как я пишу алгоритм сортировки слиянием.

public static int[] mergeSort(int[] sort) {
    if(sort.length > 1) {
        int mid = sort.length / 2;
        int[] left = Arrays.copyOf(sort, mid);
        int[] right = Arrays.copyOfRange(sort, mid, sort.length);

        // sort the left and right arrays
        mergeSort(left);
        mergeSort(right);

        // Merge the arrays
        merge(sort, left, right);
    }
}

private static void merge(int[] sort, int[] leftArray, int[] rightArray) {
    // These values are just to keep track of our position in each of the 3 
    // arrays
    int l = 0; // left array
    int r = 0; // right array
    int o = 0; // the actual array being sorted

    while(l < leftArray.length && r < rightArray.length) {
        if(leftArray[l] < righArray[r]) {
            sort[o++] = leftArray[l++];
        }
        else {
            sort[o++] = leftArray[r++];
        }
    }

    // Now that we are out of the while loop we know that either the 
    // left or right array has all of its values in sort, so we just 
    // need to put the rest of the values in the array that doesn't have
    // all of its elements in sort with the following code.

    while(l < leftArray.length) {
        sort[o++] = leftArray[l++];
    }

    while(r < rightArray.length) {
        sort[o++] = rightArray[r++];
    }
}