0

我无法在此排序算法中找到错误。当我将一个数组传递给排序方法时，比如 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;
}

}

4

3 回答 3

1

其他人认为您可能正在打印原件，因为您的代码工作正常。

你可以试试这个，它会在原地对其进行排序，从而减少意外行为并且稍微提高效率。我所做的只是concatenate采用一个新参数，它应该放置它的结果。

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

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);
于 2012-12-07T16:34:40.670 回答
0

您没有进行任何实际排序。您只是将所有内容放入较小的列表中，然后将它们放回较大的列表中。你需要在那里进行一些比较。

看看你的连接方法。您只是将较少的列表放回较少的列表中。您需要将该值与枢轴进行比较以确定该值应该去哪里。

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

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

于 2012-12-07T16:03:27.197 回答
-1

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

于 2012-12-07T16:03:40.760 回答