时间戳

首页 > 解决方案 > 排序 listarray 算法

java - 排序 listarray 算法

问题描述

编辑：

所以我实际上发现了问题..首先索引范围超出了范围，因为对于我的 while 循环，我没有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 值，如果当前元素的整数值大于下一个，我交换它们。

所以我想如果我只是迭代列表并将每个元素与其下一个元素进行比较，我最终可以对其进行排序，但由于某种原因，我遇到了一个错误，提示 index range out of bound for when charA2 == charB2。

标签： javaarraylistmergesort

解决方案

您的合并方法不假设lst1and的初始顺序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;
}

推荐阅读