java - 为什么java中的Arrays.sort()方法不使用计数排序技术？

Question

我发现Java的Arrays.sort()方法比我的简单排序方法(基于计数排序)慢得多。

我编写了一个程序来比较我的简单排序技术与 Java 的 Arrays.sort() 方法的运行时间。我注意到我的实现运行得更快(与系统方法相比，它需要 1/3 的时间)。

下面是我的实现。

我跟踪辅助数组中的所有元素，并在返回之前将所有元素复制回主数组。

static void mySort(int[] num2, int n)
{
    double startTime, endTime;

    startTime = System.currentTimeMillis(); 
    int[] sortedData = new int[n];

    for (int i = 0; i < n; i++)
       sortedData[num2[i]]++;

    int index = 0;
    for (int i = 0; i < n; i++)
       if (sortedData[i] > 0)
       {
          for (int j = 0; j < sortedData[i]; j++)
          {
             num2[index++] = i;
          }
       }

     endTime = System.currentTimeMillis(); 

     System.out.println("Time taken for my sort: " 
           + (endTime - startTime) +  " ms");
 }


 static void systemSort(int[] num)
 {
     double startTime, endTime;

     startTime = System.currentTimeMillis(); 
     Arrays.sort(num);
     endTime = System.currentTimeMillis(); 

     System.out.println("Time taken for System sort: " + 
                     (endTime - startTime) + " ms");
 }


 public static void main(String[] args)
 {

  int size = 50000000;
  int[] origArray = new int[size];
  int[] origArray2 = new int[size];

  Random rn = new Random();

  System.out.println("Taking " + size + " inputs randomly...");
  for (int i = 0; i < size; i++)
  {
     origArray[i] = rn.nextInt(size);
     origArray2[i] = origArray[i];
  }
  System.out.println("Done!");

  System.out.println("\n\nFrom System sort:  ");
  systemSort(origArray);

  System.out.println("\n\nFrom my sort:  ");

  mySort(origArray2, size);
}

这是输出:

随机获取 5000000 个输入...

系统排序花费的时间:652.0 ms

我的排序花费的时间:160.0 ms

随机获取 50000000 个输入...

系统排序花费的时间:5737.0 ms

我的排序花费的时间:2176.0 ms

如果我们可以用内存成本购买大量的执行时间(考虑到内存现在越来越便宜)，那么我们为什么不利用它呢？

有什么想法吗？ 谢谢。

Answer 1

因为您需要大小为(int)或 4 giga 的数组，所以这里只需 <50 M。而且长期以来这确实是不可能的。尝试一些更聪明的方法，例如至少对高位字节进行计数排序(短)，然后对于每个相等的高位字节范围对低位字节进行计数排序...