使用Java代码对范围在1到9之间的100万个整数进行排序

Question

假设有一百万个介于1到9之间的整数，请问您如何以有效的方式将它们进行排序？

Input: [1,2,5,4,7,8,9,6,5,4,2,3,6,5,8]  
Output: [1,2,2,3,4,4,5,5,5,6,6,7,8,8,9]

- sashikanta

---

使用计数排序。详情请参见维基百科的计数排序页面：http://en.wikipedia.org/wiki/Counting_sort - Iłya Bursov

使用Arrays.sort。 - khelwood

@khelwood 我怀疑这个练习不允许使用Arrays.sort。这是一个常见的面试问题。而且，Arrays.sort的时间复杂度为O(n log n)，而计数排序的时间复杂度为O(n)。 - Hunter McMillen

这是计数排序的Java实现：http://www.sanfoundry.com/java-program-implement-counting-sort/ - ROMANIA_engineer

Sashikanta，你已经有足够的信息来编写代码了。创建一个计数器数组来计算1、2...9的数量。遍历给定元素并计数。然后循环遍历计数器，填充第一个计数-1个为1，下一个计数-2个为2，以此类推。 - The Archetypal Paul

Answer 1

对于大数据输入，Java的Collections.sort()使用TimSort算法，它的时间复杂度为O(n log(n))。 如果你想让它运行得更快，比如线性时间，那么你应该使用基于非比较的排序算法。

由于你要排序的整数范围远小于待排序项的数量，这是使用计数排序的完美场景。

假设k=9（范围为1-9），N=1000000，那么你的运行时间将是O(k + N)。

- Bruno Cardoso

Answer 2

输入：[1,2,5,4,7,8,9,6,5,4,2,3,6,5,8]
输出：[1,2,2,3,4,4,5,5,5,6,6,7,8,8,9]

这可以在O（n）时间内使用O（k）空间解决。

由于给定范围为9，因此我们可以创建一个大小为9 + 1的数组，其中每个索引将存储输入数组中数字的出现次数。

TempArray = [0 1 2 1 2 3 2 1 2 1] Index 0 1 2 3 4 5 6 7 8 9

您只需要读取tempArray并将数据填充回输入即可。

索引1处的值为1，因此我们只会添加一个元素。

索引2处的值为2，因此我们会添加两次数字2。

索引3处的值为1，因此我们只会添加三次。

索引4处的值为2，因此我们只会将4添加两次。

通过这种方式，您可以覆盖原始数组。

T(O(n))
S(O(k))

如果有任何困惑，请告诉我。

以下是相应的C#代码：

int[] input = new int[15] { 1, 2, 5, 4, 7, 8, 9, 6, 5, 4, 2, 3, 6, 5, 8 };
  int k = 9;

  int[] temp = new int[k + 1];
  for (int index = 0; index < input.Length; index++)
  {
      temp[input[index]]++;
  }


  int i = 0; // used for input index
  for (int index = 0; index < temp.Length; index++)
  {
      while (temp[index]-- != 0)   // redusing count value after updating the index into input array
          input[i++] = index;
  }

  for (int index = 0; index < input.Length; index++)
  {
      Console.Write(" {0} ", input[index]);
  }

- AvtarSohi

Answer 3

创建10个数组（或者10个数组的数组），一个对应一个数字，遍历你的输入数组，并将每个数字添加到相应的数组中。最后，将所有数组合并在一起。

- Dima