Заказ алгоритма listarray

Question

РЕДАКТИРОВАТЬ:

Итак, я действительно понял проблему .. сначала диапазон индекса был вне границ, потому что для моего while-l oop я не устанавливал counter = 0 в том случае, если charB2 > charA2. Однако по какой-то причине использование ++counter в моем индексе бесконечно зацикливает программу. Поэтому я сделал небольшое исправление:

Извините, если это с самого начала показалось ненужным, однако после публикации моего вопроса я получил много разных отзывов, которые заставили меня попробовать альтернативы, о которых я бы не подумал иначе .

    int c = 1;

    while (charA2 == charB2) {

        charA = a.charAt(c);
        charB = b.charAt(c);
        c++;

        charA2 = charA;
        charB2 = charB;
        if (charA2 > charB2) {
            merged.set(j, b);
            merged.set(j + 1, a);
        }

Итак, мне даны два массива списков строк в java, и мне нужно написать метод без использования Collections.sort, чтобы объединить два списка и отсортировать их.

public static ArrayList<String> merged(ArrayList<String> lst1, ArrayList<String> lst2) {

    int size = lst1.size() + lst2.size();
    ArrayList<String> merged = new ArrayList<String>(size);

    merged.addAll(lst1);
    merged.addAll(lst2);

    int counter = 0;
    for (int i = 0; i < merged.size(); i++) {
        for (int j = 0; j < merged.size() - 1; j++) {
            String a = merged.get(j);
            String b = merged.get(j + 1);

            Character charA = a.charAt(counter);
            Character charB = b.charAt(counter);

            int charA2 = charA;
            int charB2 = charB;

            if (charA2 > charB2) {
                merged.set(j, b);
                merged.set(j + 1, a);
            } else
            if (charA2 == charB2) {
                while (charA2 == charB2) {
                    charA = a.charAt(++counter);
                    charB = b.charAt(++counter);

                    charA2 = charA;
                    charB2 = charB;
                    if (charA2 > charB2) {
                        merged.set(j, b);
                        merged.set(j + 1, a);
                        counter = 0;
                    } else {
                        counter=0;
                    }
                }
            }
        }
    }
    return merged;
 }

Мой метод в основном преобразовывал строку с тем же индексом в символ, который затем я могу преобразовать в int-значение, и если целочисленное значение для текущего элемента больше, чем для следующего, я меняю местами их.

Итак, я решил, что если я просто переберу список и сравню каждый элемент со следующим элементом, я смогу в конечном итоге отсортировать его, но по какой-то причине я столкнулся с ошибкой, в которой говорится, что диапазон индекса выходит за пределы, когда charA2 == charB2.

Answer 1

Ваш метод слияния не делает никаких предположений о начальном порядке lst1 и lst2: вы добавляете все элементы из обоих списков в массив merged в начале и пытаетесь выполнить сортировку вставкой в ​​полученном массиве.

Вы можете упростить свой код, если можете использовать метод compareTo для строк:

public static ArrayList<String> merged(ArrayList<String> lst1, ArrayList<String> lst2) {

    int size = lst1.size() + lst2.size();
    ArrayList<String> merged = new ArrayList<String>(size);

    merged.addAll(lst1);
    merged.addAll(lst2);

    for (int i = size; i-- > 0;) {
        bool swapped = false;
        for (int j = 0; j < i; j++) {
            String a = merged.get(j);
            String b = merged.get(j + 1);
            if (a.compareTo(b) > 0) {
                merged.set(j, b);
                merged.set(j + 1, a);
                swapped = true;
            }
        }
        if (!swapped)
            break;
    }
    return merged;
}

Если вы используете списки lst1 and lst2 are known to be sorted, you can use a much more efficient method to merge these into merged , probably covered in your course on mergesort`:

public static ArrayList<String> merged(ArrayList<String> lst1, ArrayList<String> lst2) {
    // assuming lst1 and lst2 are already sorted
    int size1 = lst1.size();
    int size2 = lst2.size();
    ArrayList<String> merged = new ArrayList<String>(size1 + size2);

    int i = 0, j = 0, k = 0;
    while (i < size1 && j < size2) {
        String a = lst1.get(i);
        String b = lst2.get(j);
        if (a.compareTo(b) <= 0) {
            merged.set(k++, a);
            i++;
        } else {
            merged.set(k++, b);
            j++;
        }
    }
    while (i < size1) {
        merged.set(k++, lst1.get(i++));
    }
    while (j < size2) {
        merged.set(k++, lst2.get(j++));
    }
    return merged;
}