Строки Java Mergesort - PullRequest
Новая
       12

Строки Java Mergesort

0 голосов
/ 10 декабря 2011

Я пытаюсь создать метод, который позволит мне сортировать массив строк в Java с помощью mergesort. Я просмотрел несколько примеров кода и создал свой собственный алгоритм, но, похоже, он не работает, и у меня возникли некоторые трудности с поиском проблемы. Код выглядит следующим образом: 

/*
 * Sorting methods, implemented using mergesort to sort the array of names
 * alphabetically
 */
public String[] sort(String[] array) {
    // check if the number of elements < 2
    if (array.length > 1) {

        // divide into two smaller arrays
        // determine length of two smaller arrays
        int arrLen1 = array.length;
        int arrLen2 = array.length - arrLen1;

        // populate smaller arrays with elements from initial array
        String[] array1 = new String[arrLen1];
        String[] array2 = new String[arrLen2];

        for (int i = 0; i < arrLen1; i++) {
            array[i] = array1[i];
        }

        for (int i = arrLen1; i < array.length; i++) {
            array[i] = array2[i];
        }

        // now that we have the two halves, we can recursively call sort() on each to sort them
        array1 = sort(array1);
        array2 = sort(array2);

        // three counters are needed to keep track of where we are in the arrays, one for pos in final array, and one for each of the two halves
        // i => pos in main array
        // j => pos in array1
        // k => pos in array2
        int i = 0, j = 0, k = 0;

        while (array1.length != j && array2.length != k) {
            if (array1[i].compareTo(array2[i]) < 0) {
                // copy current element of array1 to final array as it preceeds array2's current element
                array[i] = array1[j];

                // increment the final array so we dont overwrite the value we just inserted
                i++;
                // increment array1 which we took the element from so we dont compare it again
                j++;
            }
            // If the element in array2 preceeds the element in array1

            else {
                // copy current element of array1 to final array as it preceeds array1's current element
                array[i] = array2[j];
                // increment the final array so we dont overwrite the value we just inserted
                i++;
                // increment array2 which we took the element from so we dont compare it again
                k++;
            }
        }

        // at this point one of the sub arrays have been exhausted, and no more elements to compare
        while (array1.length != j) {
            array[i] = array1[j];
            i++;
            j++;
        }

        while (array2.length != k) {
            array[i] = array2[k];
            i++;
            k++;

        }
    }

    return array;
}

1 Ответ

0 голосов
/ 10 декабря 2011

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

Таким образом, как написан ваш код, array1 всегда равна массиву, а затем вы снова вызываете sort для array1, что означает, что вы просто постоянно идете по кругу.

...