是否可以在列表中使用列表来实现快速排序？

我使用数组以静态方式在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

是否可以在列表中使用列表来实现快速排序？

回答

相关问题