快速排序 - 数组列表 - 不起作用

Question

我无法在此排序算法中找到错误。当我将数组传递给排序方法时，例如 5,6,4,7,1，我得到与结果相同的数组。我一直在浏览代码，但我找不到哪里出了问题。忽略 SortThread 任务，这是一个将更新进度条的参数，但我现在不使用它。

class QuickSort extends Sort {
@Override
ArrayList<Integer> sort(ArrayList<Integer> array, SortThread task) {
    if (array.size() <= 1) {
        return array;
    }
    int middle = (int) Math.ceil((double) array.size() / 2);
    int pivot = array.get(middle);
    ArrayList<Integer> less = new ArrayList<>();
    ArrayList<Integer> greater = new ArrayList<>();
    for (int i = 0; i < array.size(); i++) {
        if (array.get(i) <= pivot) {
            if (i == middle) {
                continue;
            }
            less.add(array.get(i));
        } else {
            greater.add(array.get(i));
        }
    }
    return concatenate(sort(less, task), pivot, sort(greater, task));
}
private ArrayList<Integer> concatenate(ArrayList<Integer> less, int pivot, ArrayList<Integer> greater) {
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < less.size(); i++) {
        list.add(less.get(i));
    }
    list.add(pivot);
    for (int i = 0; i < greater.size(); i++) {
        list.add(greater.get(i));
    }
    return list;
}

}

Answer 1

其他人说得对，你可能正在打印原件，因为你的代码工作正常。

您可以尝试这样做，这将在原地对其进行排序，从而减少意外行为并提高效率。我所做的只是concatenate一个新的参数，这是它应该放置结果的地方。

顺便说一句：我建议你在比较之前拿出if (i == middle) { continue; }，这样也会稍微更有效率。

static class QuickSort {
  public static ArrayList<Integer> sort(ArrayList<Integer> array) {
    if (array.size() <= 1) {
      return array;
    }
    int middle = (int) Math.ceil((double) array.size() / 2);
    int pivot = array.get(middle);
    ArrayList<Integer> less = new ArrayList<>();
    ArrayList<Integer> greater = new ArrayList<>();
    for (int i = 0; i < array.size(); i++) {
      if (array.get(i) <= pivot) {
        if (i == middle) {
          continue;
        }
        less.add(array.get(i));
      } else {
        greater.add(array.get(i));
      }
    }
    return concatenate(sort(less), pivot, sort(greater), array);
  }
  private static ArrayList<Integer> concatenate(ArrayList<Integer> less, int pivot, ArrayList<Integer> greater, ArrayList<Integer> list) {
    list.clear();
    for (int i = 0; i < less.size(); i++) {
      list.add(less.get(i));
    }
    list.add(pivot);
    for (int i = 0; i < greater.size(); i++) {
      list.add(greater.get(i));
    }
    return list;
  }
} 

您可以进一步改进连接：

    list.clear();
    list.addAll(less);
    list.add(pivot);
    list.addAll(greater);

Answer 2

您没有进行任何实际排序。 你只是把所有东西放到更小的列表中，然后把它们放回一个更大的列表中。 你需要在那里做一些比较。

查看您的串联方法。 你只是把更少的列表放回更少的列表。 您需要将该值与透视表进行比较，以确定该值应位于何处。

编辑：我最初的想法是错误的。我测试了你的代码，它有效。

我猜你正在打印你传入的数组？ 请注意，您传递给排序函数的实际数组未排序。 只有那个回来了。

Answer 3

array.get（i） 返回一个 Integer，你需要提取包装的 int，否则你正在比较指针。