合并排序列表 java

Question

此代码的输出始终是输入的最后一位。找不到 reason.I 递归使用归并排序，结果是错误的。我想也许列表重叠了。

public class MergeSort {
    public static List<Integer> Sort(List<Integer> list) {
        if (list.size() <= 1) {
            return list;
        }
        List<Integer> aList = new ArrayList<Integer>();
        aList = list.subList(0, list.size() / 2);

        List<Integer> bList = new ArrayList<Integer>();
        bList = list.subList(list.size() / 2, list.size());

        Sort(aList);
        Sort(bList);

        merge(aList, bList, list);
        return list;
    }

    private static List<Integer> merge(List<Integer> alist,
        List<Integer> blist, List<Integer> list) {
        int alistIndex = 0, blistIndex = 0, listIndex = 0;
        while (alistIndex < alist.size() && blistIndex < blist.size()) {
            if (alist.get(alistIndex) < blist.get(blistIndex)) {
                list.set(listIndex, alist.get(alistIndex));
                alistIndex++;
            } else {
                list.set(listIndex, blist.get(blistIndex));
                blistIndex++;
            }
            listIndex++;
        }
        List<Integer> rest;
        if (alistIndex == alist.size()) {
            rest = blist.subList(blistIndex, blist.size());
            for(int c = blistIndex; c < rest.size(); c++){
                list.set(listIndex, blist.get(c));
                listIndex++;
            }
        } else {
            rest = alist.subList(alistIndex, alist.size());
            for(int c = alistIndex; c < rest.size(); c++){
                list.set(listIndex, alist.get(c));
                listIndex++;
            }
        }
        return list;
    }
}

测试输入为5、4、3、2、1。但是输出是 1, 1, 1, 1, 1。所以，这个合并方法肯定有问题

Answer 1

subList 方法从原始列表创建一个新列表，但仍保留对原始元素的引用，因此对第一个元素所做的任何更改都会影响第二个元素，反之亦然。在您的合并方法中，您正在覆盖原始列表，同时更改子列表中未通过 if 条件的更大元素。有关此事的更多信息，请参阅this post

Answer 2

您问题的快速解决方法是替换：

List<Integer> aList = new ArrayList<Integer>();
aList = list.subList(0, list.size() / 2);

List<Integer> bList = new ArrayList<Integer>();
bList = list.subList(list.size() / 2, list.size());

与：

List<Integer> aList = new ArrayList<Integer>(list.subList(0, list.size() / 2));
List<Integer> bList = new ArrayList<Integer>(list.subList(list.size() / 2, list.size()));

您为分区创建了新的 ArrayList，然后立即将引用更改为原始列表的视图。

列表的分区正在正确完成，但是，因为您使用的是视图而不是浅表副本，所以在合并期间您正在更改分区。

通常，如果您进行的排序会改变原始列表，您不会 return 从该方法中得到任何东西，例如：

public class MergeSort {
  public static void sort(List<Integer> list) {
    if (list.size() < 2) {
      return;
    }
    int mid = list.size()/2;
    List<Integer> left = new ArrayList<Integer>(list.subList(0, mid));
    List<Integer> right = new ArrayList<Integer>(mid, list.size()));

    sort(left);
    sort(right);
    merge(left, right, list);
  }

  private static void merge(
      List<Integer> left, List<Integer> right, List<Integer> list) {
    int leftIndex = 0;
    int rightIndex = 0;
    int listIndex = 0;

    while (leftIndex < left.size() && rightIndex < right.size()) {
      if (left.get(leftIndex) < right.get(rightIndex)) {
        list.set(listIndex++, left.get(leftIndex++));
      } else {
        list.set(listIndex++, right.get(rightIndex++));
      }
    }
    while (leftIndex < left.size()) {
      list.set(listIndex++, left.get(leftIndex++));
    }
    while (rightIndex < right.size()) {
      list.set(listIndex++, right.get(rightIndex++));
    }
  }
}

不改变原始列表的备选方案可以是：

public class MergeSort {
  public static List<Integer> sorted(List<Integer> list) {
    if (list.size() < 2) {
      return list;
    }
    int mid = list.size()/2;
    return merged(
        sorted(list.subList(0, mid)), 
        sorted(list.subList(mid, list.size())));
  }

  private static List<Integer> merged(List<Integer> left, List<Integer> right) {
    int leftIndex = 0;
    int rightIndex = 0;
    List<Integer> merged = new ArrayList<Integer>();

    while (leftIndex < left.size() && rightIndex < right.size()) {
      if (left.get(leftIndex) < right.get(rightIndex)) {
        merged.add(left.get(leftIndex++));
      } else {
        merged.add(right.get(rightIndex++));
      }
    }
    merged.addAll(left.subList(leftIndex, left.size()));
    merged.addAll(right.subList(rightIndex, right.size()));
    return merged;
  }
}

合并排序列表 java

merge sort list java

java

mergesort

list