QuickSort：這個實現有什麼問題

你能解釋一下java中這個快速排序算法實現有什麼問題嗎？QuickSort：這個實現有什麼問題

static ArrayList<Integer> quickSort(ArrayList<Integer> array){ 

    if (array.size() <=1){ 
     ArrayList<Integer> a = new ArrayList<Integer>(); 

     return a; 
    } 

    int pivotIndex = array.size()/2; 

    int pivot = array.get(pivotIndex); 
    ArrayList<Integer> left= new ArrayList<Integer>(); 
    ArrayList<Integer> right = new ArrayList<Integer>(); 

    for (int i = 0; i < array.size(); i++) { 
     if (i!=pivotIndex){ 
     if (array.get(i) > pivot) 
      right.add(array.get(i)); 
     else 
      left.add(array.get(i)); 
     } 

    } 
    ArrayList<Integer> l = new ArrayList<Integer>(); 
    l.addAll(quickSort(left)); 
    l.add(pivot); 
    l.addAll(quickSort(right)); 

    return l; 

}

來源

2012-11-17 user847988

請問一些具體的問題。您在執行過程中遇到的任何問題？任何錯誤，你得到的例外？張貼在這裏。 –

代碼運行時沒有異常或錯誤，但它不排序數據！ – user847988

一個明顯的錯誤是大小爲一數組不正確處理。這是正確的，因爲這是遞歸的基本情況之一。

來源

2012-11-17 17:26:55 NPE

你對基本案例的建議是什麼？ – user847988

代替

if (array.size() <=1) { 
    ArrayList<Integer> a = new ArrayList<Integer>(); 

    return a; 
}

使用

if (array.size() <=1){ 
    return array 
}

來源

2012-11-17 17:40:06 Subin

的主要問題與此算法 - 你在每次調用函數創建新的ArrayList。通過這種方式，您可以取消QuickSort的最佳功能 - 在沒有任何額外內存的情況下進行排序。嘗試僅與第一個陣列一起工作。

來源

2012-11-17 17:49:10 d3rzKy

QuickSort：這個實現有什麼問題

回答

相關問題