這個MergeSort 為什麼跑不了

mergesort c/c++系列文章

allthecodes 2023-03-31 20:17:14 ‧ 941 瀏覽

分享至

#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

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

1 個回答

海綿寶寶

iT邦大神 1 級 ‧ 2023-03-31 22:58:16

這份 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() 已經指向了最後一個元素的下一個位置。