java - 非常非常粗糙的排序

Question

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

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

前半部分的所有项目必须小于或等于后半部分的任何项目。

怎么做呢？...

Answer 1

正如 Karl 在他的评论中提到的，该任务相当于 quicksort algorithm 中的一个分区步骤 异常(exception)您必须先找到样本中位数并将其用作主元。

计算 median可以用 O(n) 操作计算，分区步骤也是线性的 (O(n))，因此整体最坏情况下的性能仍然优于完全排序 (O(n log(n))。

算法将是这样的(需要实现标准方法):

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