是否可以在列表中使用列表來實現快速排序？

我使用數組以靜態方式在java中實現了quickSort算法。是否可以在列表中使用列表來實現快速排序？

public static <T extends Comparable<T>> void quickSort(T[] A){ 
    quickSort(A, 0, A.length-1); 
} 

private static <T extends Comparable<T>> void quickSort(T[] A, int p, int r){ 
    if(p < r){ 
     int q = partition(A, p, r); 
     quickSort(A, p, q); 
     quickSort(A, q+1, r); 
    } 
} 

private static <T extends Comparable<T>> int partition(T[] A, int p, int r){ 
    T x = A[p]; 
    int i = p; 
    int j = r; 
    while(true){ 
     while(A[j].compareTo(x) > 0 && j > p){ 
      j--; 
     } 
     while(A[i].compareTo(x) < 0 && i < r){ 
      i++; 
     } 
     if(i < j) 
      swap(A, i, j); 
     else 
      return j; 
    } 
}

有沒有一種方法來實現這個算法使用列表，保留「在本地」屬性。我認爲使用沒有索引的列表是一個問題，因爲在兩個不同的「while」之後，如果引用屬於另一個之前的節點，則需要知道。有誰知道避免這種麻煩的方法嗎？

來源

2015-01-09 johnny_kb

@khelwood它不，QuickSort僅用於對原始數組進行排序。其他人使用MergeSort（早期版本）/ TimSort（從Java 7開始）。 – 2015-01-09 20:33:41

使用List而不是數組來實現相同的算法沒有問題。您可以像使用數組一樣使用List：使用set和get方法。它也有便利的方法，如subList對於快速排序很有用。子列表是列表的視圖;不涉及複製。所以這消除了通過上限和下限的需要。

static void sort(List<Integer> list) { 
    if (!list.isEmpty()) { 
     int pivotValue = list.get(list.size() - 1); 
     int storeIndex = 0; 
     for (int i = 0; i < list.size() - 1; i++) { 
      if (list.get(i) < pivotValue) { 
       Collections.swap(list, i, storeIndex++); 
      } 
     } 
     Collections.swap(list, list.size() - 1, storeIndex); 
     sort(list.subList(0, storeIndex)); 
     sort(list.subList(storeIndex + 1, list.size())); 
    } 
}

您引用了使用不帶索引的列表的問題。當然，可以從列表中刪除add和remove對象而不使用索引。然而，很難看到如何在不使用索引的情況下實現快速排序。例如，拾取樞軸和交換元件都需要索引。

來源

2015-01-10 11:28:42 sprinter

是否可以在列表中使用列表來實現快速排序？

回答

相關問題