1
所以有一點背景：合併排序問題
我們的老師基本上坐下來，做了一個Java的基本實現，你可以說。他告訴我們嘗試在他製作的這個系統中實現合併算法。
我想做一個合併排序（自上而下的實現），但我有幾個問題。
該合併排序應該採取兩個表（從他做的數據庫實施模擬），並安排他們，使他們按升序（1-8）從最低到最高顯示。
該代碼讓我使用我們的老師編寫的DbIterator來遍歷表及其內容。因此，我們必須具有以下數據的兩個表：
[hello1, 5]
[hello2, 6]
[hello3, 7]
[hello4, 8]
而其他表：
[goodbye4, 4]
[goodbye2, 2]
[goodbye3, 3]
[goodbye1, 1]
合併排序它應該打印出來之後：
[goodbye1, 1]
[goodbye2, 2]
[goodbye3, 3]
[goodbye4, 4]
[hello1, 5]
[hello2, 6]
[hello3, 7]
[hello4, 8]
但這是它打印出來的內容：
null
[hello1, 5]
[hello2, 6]
[hello3, 7]
我對此感到困惑，並試圖調試以找出錯誤，但我可能已經嘗試了太多，以至於對實際問題變得盲目。因此，這裏的代碼（排序發生在過去的三個方法）：
所有的public String[] MergeSort(String table1, String table2) {
DbIterator scannerA = getTableScanner(table1);
DbIterator scannerB = getTableScanner(table2);
HashMap<Integer, String> records = new HashMap<>();
ArrayList<Integer> A = new ArrayList<>();
ArrayList<Integer> B = new ArrayList<>();
int n = 0;
scannerA.open();
while(scannerA.hasNext()) {
Record r = scannerA.next();
StringField sF = (StringField) r.getField(0);
IntegerField iF = (IntegerField) r.getField(1);
records.put(iF.hashCode(), sF.toString());
A.add(iF.hashCode());
n++;
}
scannerA.close();
scannerB.open();
while(scannerB.hasNext()) {
Record r = scannerB.next();
StringField sF = (StringField) r.getField(0);
IntegerField iF = (IntegerField) r.getField(1);
records.put(iF.hashCode(), sF.toString());
B.add(iF.hashCode());
n++;
}
scannerB.close();
int[] mergeResult;
int[] aA = convertIntegers(A);
int[] bB = convertIntegers(B);
mergeResult = TopDownSplitMerge(aA, 0, n, bB);
String[] results = new String[mergeResult.length];
for(int v = 0; v < mergeResult.length; v++) {
if(records.containsKey(v)) {
results[v] = "[" + records.get(v) + ", " + v +"]";
}
}
return results;
}
private int[] CopyArray(int[] B, int iBegin, int iEnd, int[] A) {
for(int k = iBegin; k < iEnd; k++)
A[k] = B[k];
return A;
}
private int[] TopDownSplitMerge(int[]A,int iBegin, int iEnd, int[]B) {
if(iEnd - iBegin < 2) {
return null;
}
int iMiddle = (iEnd + iBegin)/2;
TopDownSplitMerge(A, iBegin, iMiddle, B);
TopDownSplitMerge(A, iMiddle, iEnd, B);
TopDownMerge(A, iBegin, iMiddle, iEnd, B);
int[] tmp = CopyArray(B, iBegin, iEnd, A);
return tmp;
}
public void TopDownMerge(int[] A, int iBegin, int iMiddle, int iEnd, int[] B) {
int i0 = iBegin;
int i1 = iMiddle;
for(int j = iBegin; j < iEnd; j++) {
if(i0 < iMiddle && (i1 >= iEnd || A[i0] <= A[i1])) {
B[j] = A[i0++];
} else {
B[j] = A[i1++];
}
}
}
首先，這不是我個人的算法，而是我想從一個wiki實現它。我唯一無法解決的部分，可能會一起解決整個問題，這就是他們所說的「iEnd」。值爲n。我無法弄清楚如何計算或給出什麼值。可能真的是整個問題。