非常非常粗糙的排序

Question

假设我们有一个数组(int [] m).

我需要对它进行排序......结果必须是:

上半场的所有项目必须少于或等于下半场的任何项目.

怎么做？...

Answer 1

正如卡尔在评论中已经提到的那样,该任务等同于快速排序算法中的分离步骤,除了您必须首先找到样本中位数并将其用作枢轴元素.

计算中值可以用O(n)运算来计算,参与步骤也是线性的(O(n)),因此总体最坏情况性能仍然优于完全排序(O(n log(n)).

算法将如下所示(标准方法需要实现):

public int[] roughSort(int[] input) {
  int pivot = findMedian(input);
  int[] result = partition(input, pivot);
  return result;
}