订购一个列表阵列算法

Question

EDIT.我其实已经知道问题所在了......一开始索引范围是出界的，因为我的while-loop没有设置，所以我没有设置。

其实我已经知道问题所在了... 一开始索引范围是越界的，因为我的while-loop没有设置好。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中得到两个字符串listarrays，我需要在不使用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-value，如果当前元素的整数值大于下一个元素，我就把它们交换。

所以我想，如果我只是对列表进行迭代，并将每个元素与它的下一个元素进行比较，我最终可以对它进行排序，但由于某些原因，我遇到了一个错误，说索引范围超出了约束，当 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 andlst2are known to be sorted, you can use a much more efficient method to merge these into合并, probably covered in your course onmergesort`。

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;
}