我已經實作了一個 QuickSort 演算法以及一個時間復雜度控制元件。它適用于較小的 N，但一旦我接近較大的 N，StackOverflow 是不可避免的。我認為將樞軸元素作為最后一個元素可能是導致這種情況的原因。
我的第一個想法是簡單地始終使用中間元素作為樞軸元素來避免這種情況，但由于測驗程式拋出“未排序的例外”，因此這不是一個有效的解決方案。
我有什么想法可以解決這個問題嗎？
public class QuickSorter implements IntSorter{
int partition (int a[], int lo, int hi) {
int pivot = a[hi]; // pivot element
int i = (lo - 1);
for (int j = lo; j <= hi - 1; j ) {
if (a[j] < pivot) {
i ;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
int temp = a[i 1];
a[i 1] = a[hi];
a[hi] = temp;
return (i 1);
}
@Override
public void sort(int[] a) {
int lo = 0;
int hi = a.length-1;
if (lo < hi) {
int p = partition(a, lo, hi);
sort(a, lo, p - 1);
sort(a, p 1, hi);
}
}
private void sort(int[] a, int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
sort(a, lo, p - 1);
sort(a, p 1, hi);
}
}
}
測驗代碼：
private static void testSort(IntSorter sorter, int firstN, boolean ordered) {
double t1 = 0;
int N = firstN/2;
while (t1 < 0.7 && N < 10000000) {
N *= 2;
int[] a = create(N, ordered);
t1 = timeit(sorter, a);
System.out.println("T(" N ")=" t1);
ArrayUtil.testOrdered(a);
}
int[] a = create(4*N, ordered);
double t4 = timeit(sorter, a);
ArrayUtil.testOrdered(a);
double t01 = t1 / (N * Math.log(N ));
double t04 = t4 / (4*N * Math.log(4*N));
System.out.println("T(" 4*N ")=" t4 " growth per N log N: " t04/t01);
if (t04/t01 > 1.25) {
System.out.println(sorter.getClass().getName() ".sort appears not to run in O(N log N) time");
System.exit(1);
}
}
public static void testOrdered(int[] a) {
int N = a.length;
for (int i = 1; i < N; i ) {
if (a[i] < a[i-1]) {
throw new SortingException("Not sorted, a[" (i-1) "] > a[" i "]");
}
}
}
uj5u.com熱心網友回復：
正如 Thomas 評論的那樣，使用中間元素作為樞軸應該可以正常作業。實際上，這是一個常見的選擇，因為它適用于碰巧已經完全或部分排序的輸入陣列。
至于避免堆疊溢位，一種常見的方法是在磁區步驟后僅在較短的部分遞回 - 這確保在每個級別處理的陣列至少減半，因此例如 1,000,000 個元素的陣列將具有最大呼叫深度大約 20 ( log2(1,000,000) )。
所以，而不是
private void sort(int[] a, int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
sort(a, lo, p - 1);
sort(a, p 1, hi);
}
}
你做
private void sort(int[] a, int lo, int hi) {
while (lo < hi) {
int p = partition(a, lo, hi);
// recurse on smaller part, loop on larger part
if (((p - 1) - lo) > (hi - (p 1))) {
sort(a, p 1, hi);
hi = p - 1;
}
else {
sort(a, lo, p - 1);
lo = p 1;
}
}
}
uj5u.com熱心網友回復：
在使用下面的方法排序之前對陣列進行洗牌似乎也解決了我遇到的問題
public void shuffle(int[] a) {
int N = a.length;
Random randomGenerator = new Random();
for (int i = 0; i < N; i ) {
int r = i randomGenerator.nextInt(N-i); // between i and N-1
int t = a[i]; a[i] = a[r]; a[r] = t;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/377765.html
上一篇：使用默認值從串列中初始化Map鍵
下一篇：java中默認建構式的實際使用