我的Quicksort算法運行速度過慢

Question

我使用Quicksort算法對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位蘭特整數數組

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);

and in 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);