java - 100,000,000个元素的数组快排需要5个小时正常吗？

Question

在Java中实现以最后一个数组为轴心的基本算法，100,000,000个元素的随机数数组排序需要5个小时是否正常？

我的系统规范:Mac OS X 狮子 10.7.2 (2011)英特尔酷睿 i5 2.3 GHz8GB内存

更新 2:自从 Narendra 能够运行快速排序以来，我认为我在其他方法中做错了。这是我尝试运行的完整代码。

import java.util.Random;

public class QuickSort {
public static int comparisons = 0;

public static void main(String[] args) {
    int size = 100000000;
    int[] smallSampleArray = createArrayOfSize(size);

    System.out.println("Starting QS1...");
    long startTime = System.currentTimeMillis();
    quickSort(smallSampleArray,0,size-1);
    System.out.println(  "Finished QS1 in " + (System.currentTimeMillis() - startTime)+ " seconds");
    System.out.println("Number of comparisons for QS1: " + comparisons);

}

public static int[] createArrayOfSize(int arraySize) {
    int[] anArray = new int[arraySize];
    Random random = new Random();

    for(int x=0; x < anArray.length; x++ ) {
        anArray[x] = random.nextInt(1000) + 1;;
    }
    return anArray;
}


public static void quickSort( int anArray[], int position, int pivot) {

    if( position < pivot ) {
        int q = partition(anArray, position, pivot);

        quickSort(anArray, position, q-1);
        quickSort(anArray, q+1, pivot);

    }

}

public static int partition(int anArray[], int position, int pivot ) {
    int x = anArray[pivot];
    int i = position - 1; 

    for(int j = position; j < (pivot-1); j++ ) {
        comparisons++;
        if(anArray[j] <= x) {
             i = i + 1;
             int temp =  anArray[i];
             anArray[i] = anArray[j];
             anArray[j] = temp;
        }

    }
    int temp = anArray[i+1];
    anArray[i+1] = anArray[pivot];
    anArray[pivot] = temp;



        return i+1;
    }

}

Answer 1

我已将现在不相关的旧答案移至末尾。

编辑x2

啊哈!我想我已经找到你糟糕表现的原因了。您告诉我们您使用的是随机数据。那是真实的。但您没有告诉我们的是，您使用的可能随机值范围如此之小。

对我来说，如果您更改此行，您的代码将非常高效:

anArray[x] = random.nextInt(1000) + 1;

为此:

anArray[x] = random.nextInt();    

这与预期相反，对吗？对较小范围的值进行排序应该更便宜，因为我们需要做的交换应该更少，对吧？那么为什么会发生这种情况？发生这种情况是因为您有太多具有相同值的元素(平均为 10 万)。那么为什么这会导致如此糟糕的表现呢？好吧，假设您在每个点都选择了一个完美 的枢轴值:正好是一半。这是它的样子:

1000 - Pivot: 500
 - 500+ - Pivot: 750
   - 750+ - Pivot: 875
   - 750- - Pivot: 625
 - 500- - Pivot: 250

等等。 但是(这是关键部分)您最终会进行分区操作，其中每个值都等于分区值。换句话说，将有一个大(10 万大)数字 block ，您将尝试对其进行递归排序。那将如何发生？它将递归10 万次，只删除每个级别的单个主元值。换句话说，它会将所有内容 划分到左侧或将所有内容划分到右侧。

扩展上面的分解，它看起来有点像这样(为了简单起见，我使用了 8——2 的幂——请原谅糟糕的图形表示)

Depth Min  Max  Pvt NumElements

0     0     7    4   100 000 000
1     0     3    2    50 000 000    
2     0     1    1    25 000 000
3     0     0    0    12 500 000 < at this point, you're
4     0     0    0    12 499 999 < no longer dividing and
5     0     0    0    12 499 998 < conquering effectively.
3     1     1    1    12 500 000
4     1     1    1    12 499 999
5     1     1    1    12 499 998
2     2     3    3    25 000 000
3     ...    
3     ...    
1     4     7    6    50 000 000    
2     4     5    5    25 000 000
3     ...
3     ...    
2     6     7    7    25 000 000
3     ...
3     ... 

如果你想解决这个问题，你需要优化你的代码来减少它的影响。更多关于这方面的信息(我希望)...

...并继续。解决问题的一种简单方法是在每一步检查数组是否已排序。

public static void quickSort(int anArray[], int position, int pivot) {

    if (isSorted(anArray, position, pivot + 1)) {
        return;
    }

    //...
}


private static boolean isSorted(int[] a, int start, int end) {
    for (int i = start+1; i < end; i++) {
        if (a[i] < a[i-1]) {
            return false;
        }
    }
    return true;
}

加上那个，你就不会不必要地递归，你应该是金色的。事实上，与在整数的所有 32 位上随机取值相比，您可以获得更好的性能。

---

旧答案(仅供后代使用)

我觉得你的分区逻辑很可疑。让我们提取并忽略交换逻辑。这是您拥有的:

    int i = position - 1; 

    for(int j = position; j < pivot; j++ ) {

        if(anArray[j] <= x) {
             i = i + 1;
             swap(anArray, i, j);
        } 

    }

我完全看不出这是如何工作的。例如，如果第一个值小于枢轴值，它会与自身交换吗？

我想你想要这样的东西(只是一个粗略的草图):

for ( int i = 0, j = pivot - 1; i < j; i++ ) {

   if ( anArray[i] > pivotValue ) {
      //i now represents the earliest index that is greater than the pivotValue,
      //so find the latest index that is less than the pivotValue
      while ( anArray[j] > pivotValue ) {
         //if j reaches i then that means that *all* 
         //indexes before i/j are less than pivot and all after are greater
         //and so we should break out here
         j--;
      }

      swap(anArray, i, j);
   }
} 

//swap pivot into correct position
swap(anArray, pivot, j+1);

编辑

我想我现在理解了原始的分区逻辑(我把 if block 混淆为查看大于主元的元素)。如果它提供更好的性能，我会留下我的答案，但我怀疑它会产生重大影响。