我已經在 C/C 中實作了歸并排序。但是我的代碼比我從網站上提取的代碼花費的時間更長。
對于這兩種情況，遞回代碼似乎完全相同：
void mergeSort(int* arr, int l, int h) {
if (l < h) {
int mid = (l h) / 2;
mergeSort(arr,l,mid);
mergeSort(arr, mid 1, h);
merge(arr, l, mid, h);
}
}
然而合并演算法有點不同，但我在這里沒有看到任何顯著差異。
我的合并演算法：
void merge(int *arr, int l, int mid, int h) {
int i = l, j = mid 1, k = l;
int* newSorted = new int[h 1]();
while (i <= mid && j <= h) {
if (arr[i] < arr[j])
newSorted[k ] = arr[i ];
else
newSorted[k ] = arr[j ];
}
for (; i <= mid; i )
newSorted[k ] = arr[i];
for (; j <= h; j )
newSorted[k ] = arr[j];
k = 0;
for (int x = l; x <= h; x )
arr[x] = newSorted[x];
delete[] newSorted;
}
200000（二十萬個輸入）所用的時間：
17 秒
來自網站的合并演算法：
void merge(int arr[], int p, int q, int r) {
int n1 = q - p 1;
int n2 = r - q;
int* L = new int[n1];
int *M = new int[n2];
for (int i = 0; i < n1; i )
L[i] = arr[p i];
for (int j = 0; j < n2; j )
M[j] = arr[q 1 j];
int i, j, k;
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i ;
}
else {
arr[k] = M[j];
j ;
}
k ;
}
while (i < n1) {
arr[k] = L[i];
i ;
k ;
}
while (j < n2) {
arr[k] = M[j];
j ;
k ;
}
delete[] L;
delete[] M;
}
200000（二十萬個輸入）所用的時間：
0 秒
時間上存在巨大差異。我不明白我的代碼中的問題。如果有人能幫我解決這個問題，我將不勝感激。謝謝你。
uj5u.com熱心網友回復：
您的演算法需要為每一步分配 [h 1]。
一個網站的演算法只需要分配[r-p 1]（你的h=它的r，你的l=它的p）
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/333886.html
上一篇：合并排序：分段錯誤C