QuickSort 三路划分+混合实现
QuickSort Three Way Partition + Hybrid Implementation
我正在尝试使用混合快速排序实现三向分区快速排序。问题是我最后得到了一个无序列表。我已经单独测试了混合快速排序和插入排序,它们运行良好(测试大小:10、50、500、1000、5000)。我 运行 调试但仍然无法判断问题出在哪里。先感谢您。这是代码。
public <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list) {
int lo = 0;
int hi = list.size() - 1;
if (hi <= lo) return;
int lt = lo, i = lo+1, gt = hi;
while (i <= gt) {
if (comparator.compare(list.get(i), list.get(lo)) < 0) //did not use AbstractSorter greter in order to check all cases.
exch(list, lt++, i++);
else if(comparator.compare(list.get(i), list.get(lo)) > 0)
exch(list, i, gt--);
else
i++;
} // Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(comparator, list, lo, lt - 1);
sort(comparator, list, gt + 1, hi);
}
private <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int hi){
if(hi <= lo) return;
if(hi - lo <= 8){
InsertionSort sorter = new InsertionSort();
sorter.sort(comparator, list.subList(lo, hi + 1));
List<SorterListener> listeners = (ArrayList)sorter.getListeners();
for(SorterListener s: listeners)
getListeners().add(s);
return;
}
int i = partition(comparator, list, lo, hi);
sort(comparator, list, lo, i - 1);
sort(comparator, list, i + 1, hi);
}
编辑:
public <T> void exch(@NotNull List<T> list, int i, int j) {
final T aux = list.get(i);
list.add(i, list.get(j));
list.remove(i + 1);
list.add(j, aux);
list.remove(j + 1);
listeners.get(0).swap(i, j);
}
public <T> int partition(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int hi) {
int i = lo - 1;
int j = hi;
while(true) {
while( greater(list, hi, ++i, comparator)) //find item left to swap
if (i == hi) break;
while( greater(list, --j, hi, comparator)) //find item right to swap
if (j == lo) break;
if (i >= j) break; //check if pointers cross
exch(list, i, j); //swap
}
exch(list, i, hi); //swap with partitioning item
return i; //return index of item now known to be in place
}
如果我理解您在第一个 sort
方法(public 方法)中进行分区的意图,则 lt
指向您作为分区依据的元素。因此,在您的比较中,您应该将 i
处的元素与 lt
处的元素进行比较,而不是 lo
:
处的元素
if (comparator.compare(list.get(i), list.get(lt)) < 0) //did not use AbstractSorter greter in order to check all cases.
exch(list, lt++, i++);
else if(comparator.compare(list.get(i), list.get(lt)) > 0)
exch(list, i, gt--);
通过此更改,该方法似乎可以正常工作,至少在我 运行 的样本上是这样。
顺便说一句,你的评论对我有帮助,Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
你可以通过将其转化为断言来做得更好:
T v = list.get(lt);
for (int ix = lo; ix < lt; ix++) {
assert comparator.compare(list.get(ix), v) < 0 : "lt " + lt + ' ' + list;
}
for (int ix = lt; ix <= gt; ix++) {
assert comparator.compare(list.get(ix), v) == 0 : "lt " + lt + " gt " + gt + ' ' + list;
}
for (int ix = gt + 1; ix <= hi; ix++) {
assert comparator.compare(list.get(ix), v) > 0 : "gt " + gt + ' ' + list;
}
启用这些断言后,Java 将捕获错误并打印例如:
Exception in thread "main" java.lang.AssertionError: gt 2 [1, 0, 3, 6, 4, 8, 9, 5, 2, 7, 10]
在本例中 gt
指向元素 3
,但在列表的右侧还有一个 2
。
我正在尝试使用混合快速排序实现三向分区快速排序。问题是我最后得到了一个无序列表。我已经单独测试了混合快速排序和插入排序,它们运行良好(测试大小:10、50、500、1000、5000)。我 运行 调试但仍然无法判断问题出在哪里。先感谢您。这是代码。
public <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list) {
int lo = 0;
int hi = list.size() - 1;
if (hi <= lo) return;
int lt = lo, i = lo+1, gt = hi;
while (i <= gt) {
if (comparator.compare(list.get(i), list.get(lo)) < 0) //did not use AbstractSorter greter in order to check all cases.
exch(list, lt++, i++);
else if(comparator.compare(list.get(i), list.get(lo)) > 0)
exch(list, i, gt--);
else
i++;
} // Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(comparator, list, lo, lt - 1);
sort(comparator, list, gt + 1, hi);
}
private <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int hi){
if(hi <= lo) return;
if(hi - lo <= 8){
InsertionSort sorter = new InsertionSort();
sorter.sort(comparator, list.subList(lo, hi + 1));
List<SorterListener> listeners = (ArrayList)sorter.getListeners();
for(SorterListener s: listeners)
getListeners().add(s);
return;
}
int i = partition(comparator, list, lo, hi);
sort(comparator, list, lo, i - 1);
sort(comparator, list, i + 1, hi);
}
编辑:
public <T> void exch(@NotNull List<T> list, int i, int j) {
final T aux = list.get(i);
list.add(i, list.get(j));
list.remove(i + 1);
list.add(j, aux);
list.remove(j + 1);
listeners.get(0).swap(i, j);
}
public <T> int partition(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int hi) {
int i = lo - 1;
int j = hi;
while(true) {
while( greater(list, hi, ++i, comparator)) //find item left to swap
if (i == hi) break;
while( greater(list, --j, hi, comparator)) //find item right to swap
if (j == lo) break;
if (i >= j) break; //check if pointers cross
exch(list, i, j); //swap
}
exch(list, i, hi); //swap with partitioning item
return i; //return index of item now known to be in place
}
如果我理解您在第一个 sort
方法(public 方法)中进行分区的意图,则 lt
指向您作为分区依据的元素。因此,在您的比较中,您应该将 i
处的元素与 lt
处的元素进行比较,而不是 lo
:
if (comparator.compare(list.get(i), list.get(lt)) < 0) //did not use AbstractSorter greter in order to check all cases.
exch(list, lt++, i++);
else if(comparator.compare(list.get(i), list.get(lt)) > 0)
exch(list, i, gt--);
通过此更改,该方法似乎可以正常工作,至少在我 运行 的样本上是这样。
顺便说一句,你的评论对我有帮助,Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
你可以通过将其转化为断言来做得更好:
T v = list.get(lt);
for (int ix = lo; ix < lt; ix++) {
assert comparator.compare(list.get(ix), v) < 0 : "lt " + lt + ' ' + list;
}
for (int ix = lt; ix <= gt; ix++) {
assert comparator.compare(list.get(ix), v) == 0 : "lt " + lt + " gt " + gt + ' ' + list;
}
for (int ix = gt + 1; ix <= hi; ix++) {
assert comparator.compare(list.get(ix), v) > 0 : "gt " + gt + ' ' + list;
}
启用这些断言后,Java 将捕获错误并打印例如:
Exception in thread "main" java.lang.AssertionError: gt 2 [1, 0, 3, 6, 4, 8, 9, 5, 2, 7, 10]
在本例中 gt
指向元素 3
,但在列表的右侧还有一个 2
。