#include<bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0) -> sync_with_stdio
#define emp emplace_back
#define vll vector<ll>
using namespace std;
typedef long long ll;
vll A(1e6);
void Merge(vll L , vll R){
ll i = 0 , j = 0 , k = 0;
while(i < L.size() && j < R.size()){
if(L[i] >= R[j]){
A[k] = L[i];
i++;
k++;
}
else{
A[k] = R[j];
j++;
k++;
}
}
while(i < L.size()){
A[k] = L[i];
k++;
i++;
}
while(j < R.size()){
A[k] = R[j];
k++;
j++;
}
}
void Solve(vll v){
if(v.size() <= 1) return;
ll m = v.size() / 2;
vll L(v.begin() , v.begin() + m + 1) , R(v.begin() + m + 1 , v.end()+1);//分一半
Solve(L);//再分
Solve(R);//再分
Merge( L , R );//加總
}
signed main(){
//IO;
ll n;
while(cin >> n){
A.assign(n+1 , 0);
for(int i = 0 ; i < n ; i++){
ll ai;
cin >> ai;
A.emp(ai);
}
Solve(A);
for(int i = 0 ; i < n-1 ; i++){
cout << A[i] << ' ';
}
cout << A[n-1] << endl;
}
}
其實我自己觀念也不太懂 有人能詳解且挑錯嗎QwQ
這份 MergeSort 程式碼有幾個問題需要修正:
MergeSort 函式應當要回傳排序後的結果,而不是將結果寫入全域變數 A 中,因為這樣做會導致每次呼叫 Solve 函式時,A 的值會被改寫,而這很容易導致錯誤結果。
Merge 函式的參數應該是傳址 (pass by reference),這樣才能改變 L 和 R 的內容。
在 Merge 函式中,比較大小的條件應當是 L[i] <= R[j],而不是 L[i] >= R[j],因為 MergeSort 是要按照由小到大的順序排序。
在 Solve 函式中,建立 R 子陣列的方式有誤,應該是 R(v.begin() + m + 1, v.end()),因為 v.end() 已經指向了最後一個元素的下一個位置。