我已經實作了歸并排序與我的分配演算法一起使用。它可以作業，但是對于大量測驗用例，回傳結果需要很長時間，但不應該。我已經清除了我的主要方法，并且我確信合并排序是問題所在。有人能解釋一下我做了什么使它如此低效嗎？
public static double[] merge(double[] arrayA, double[] arrayB){
double[] arrayC = new double[0];
while((arrayA.length != 0) && (arrayB.length != 0)){
if(arrayA[0]>arrayB[0]){
arrayC = Array.arrAdd(arrayC, arrayB[0]);
arrayB = Array.arrRem(arrayB);
}else{
arrayC = Array.arrAdd(arrayC, arrayA[0]);
arrayA = Array.arrRem(arrayA);
}
}
while(arrayA.length != 0){
arrayC = Array.arrAdd(arrayC, arrayA[0]);
arrayA = Array.arrRem(arrayA);
}
while(arrayB.length != 0){
arrayC = Array.arrAdd(arrayC, arrayB[0]);
arrayB = Array.arrRem(arrayB);
}
return arrayC;
}
public static double[] mergeSort(double[] arrayA){
if(arrayA.length == 1){
return arrayA;
}
int a;
int b;
if(arrayA.length % 2 != 0){
a = (arrayA.length 1)/2;
b = (arrayA.length-1)/2;
}else{
a = (arrayA.length)/2;
b = (arrayA.length)/2;
}
double[] array1 = new double[a];
double[] array2 = new double[b];
for(int i=0; i<array1.length; i ){
array1[i] = arrayA[0];
arrayA = Array.arrRem(arrayA);
}
for(int i=0; i<array2.length; i ){
array2[i] = arrayA[0];
arrayA = Array.arrRem(arrayA);
}
array1 = mergeSort(array1);
array2 = mergeSort(array2);
return merge(array1, array2);
}
我還包括我的“arrAdd”和“arrRem”方法，它們用于在陣列末尾添加一個元素并從索引 0 中洗掉一個元素。
public static double[] arrAdd(double[] arrayA, double value){
double[] arrayB = new double[arrayA.length 1];
System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length);
arrayB[arrayA.length] = value;
return arrayB;
}
public static double[] arrRem(double[] arrayA){
double[] arrayB = new double[arrayA.length-1];
System.arraycopy(arrayA, 1, arrayB, 0, arrayA.length - 1);
return arrayB;
}
uj5u.com熱心網友回復：
因為arrayRem效率低得可怕。
假設您有一個包含 100 萬個元素的陣列。你想通過這些元素。這樣做的方法是查看第一個元素，然后通過將所有其他元素復制到靠近前面的一個位置來洗掉第一個元素，并重復此操作直到陣列為空。
因此，在消耗第一個元素后，您將復制 999 999 個元素。
消耗第二個元素后，您將復制 999 998 個元素。
消耗第三個元素后，您將復制 999 997 個元素。
（此處省略了 999 996 行）
在消耗第 1 000 000 個元素后，您正在復制 0 個元素。
也就是說，要讀取長度為 100 萬的陣列，您總共要復制 1 000 000 * 500 000 = 500 000 000 000 個元素。這需要一段時間。
歸并排序的正確實作是通過遞增索引來讀取陣列，而不是每次遞增洗掉第一個元素并復制所有剩余元素。
類似地，一種有效的添加元素的方法是創建一個足夠大的陣列來容納所有元素，然后通過跟蹤下一個元素應該寫入的索引將每個元素寫入正確的位置，而不是復制添加的每個元素的所有現有元素。
uj5u.com熱心網友回復：
創建陣列的副本以添加/洗掉單個專案是操作資料的一種非常昂貴的方式。使用ArrayList或 'LinkedList' 而不是普通陣列！
如果您需要一種更快的方式來處理原始型別，請查看 Colt 庫：
https://dst.lbl.gov/ACSSoftware/colt/
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/323497.html