java - 我的快速排序算法运行速度太慢

Question

我正在使用快速排序算法对 32 位随机整数进行排序。当我对 10 或 100 或 1000 个元素进行排序时，算法运行很快，但当我选择 n=10.000 时，排序大约需要 15 分钟。我想将 n 增加到 10000000，但算法将永远持续下去。我找不到我的实现有什么问题。

这是我的主要功能

 public static void main(String[] args) {

    for(int i=0; i<100; i++){

    Random rand = new Random(new Date().getTime()); //different seed for each run

    createRandArray(rand);  
    long startTime= System.nanoTime();
    sort();
    long finishTime= System.nanoTime();
    }

这里是快速排序的实现

  public static void sort(){
        int left = 0;
        int right = my_array.length-1;
        quickSort(left, right);
    }

    private static void quickSort(int left,int right){

        if(left >= right)
            return;

        BigInteger pivot = my_array[right];
        int partition = partition(left, right, pivot);

        quickSort(0, partition-1);
        quickSort(partition+1, right);

    }

    private static int partition(int left,int right,BigInteger pivot){
        int leftCursor = left-1;
        int rightCursor = right;

        while(leftCursor < rightCursor){

                while(my_array[++leftCursor].compareTo(pivot)==-1);
                while(rightCursor > 0 && my_array[--rightCursor].compareTo(pivot)==1);

            if(leftCursor >= rightCursor){
                break;
            }
            else{
                swap(leftCursor, rightCursor);
            }
        }

        swap(leftCursor, right);
        return leftCursor;
    }

    public static void swap(int left,int right){

        BigInteger temp = my_array[left];
        my_array[left] = my_array[right];
        my_array[right] = temp;
    }

这就是我创建 32 位 rand 整数数组的方式

 public static void createRandArray(Random rand ){

        BigInteger big_int=new BigInteger("1"); //initialization

        for(int i=0; i<100 ; i++){
        big_int= new BigInteger(32, rand);
        my_array[i]= big_int;
    }
}

任何帮助将不胜感激。

Answer 1

您在几个地方错误地假设下限为零而不是 left，因此您做的工作比您需要的多:

在 quickSort(int left,int right) 中:

quickSort(0, partition-1);
到
quickSort(left, partition-1);

在 partition(int left,int right,BigInteger pivot) 中:

while(rightCursor > 0 && my_array[--rightCursor].compareTo(pivot)==1);
到
while(rightCursor > left && my_array[--rightCursor].compareTo(pivot)==1);