java - 以 o(n) 或 o(1) 的时间复杂度对整数数组进行排序

Question

能够以 o(n) 或更小的时间复杂度对从 1 到 4 的整数数组进行排序(非常简单)的最佳算法是什么？

Answer 1

使用Radix Sort ，即 O(n)

 public void radixsort(int[] input) {
  final int RADIX = 10;
  // declare and initialize bucket[]
  List<Integer>[] bucket = new ArrayList[RADIX];
  for (int i = 0; i < bucket.length; i++) {
    bucket[i] = new ArrayList<Integer>();
  }

  // sort
  boolean maxLength = false;
  int tmp = -1, placement = 1;
  while (!maxLength) {
    maxLength = true;
    // split input between lists
    for (Integer i : input) {
      tmp = i / placement;
      bucket[tmp % RADIX].add(i);
      if (maxLength && tmp > 0) {
        maxLength = false;
      }
    }
    // empty lists into input array
    int a = 0;
    for (int b = 0; b < RADIX; b++) {
      for (Integer i : bucket[b]) {
        input[a++] = i;
      }
      bucket[b].clear();
    }
    // move to next digit
    placement *= RADIX;
  }
}

代码 Ref