我始終相信一句話：只有自己足夠強大。

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：主機域名、網站空間、營銷軟件、網站建設、濟陽網站維護、網站推廣。

歸并排序

• 一、分治思想
• 二、歸并排序實現
• 三、代碼展示

一、分治思想

分治，就是把一個問題分成多個相似或相同的子問題，直到子問題可以簡單的解決。
歸并排序就是運用了這個分治思想，通過遞歸把要排序的元素分成多個子序列，l記錄起始位置，r記錄末尾位置，在進行循環，去判斷大小，從而完成排序。

二、歸并排序實現

要排序得先開數組，在輸入數據

代碼如下（示例）：

const int N = 1e6 + 10;

int q[N], tmp[N];

int n;

	cin >>n;
	for (int i = 0; i< n; i++)
	{cin >>q[i];
	}

在這里，用了一個臨時數組tmp，是為了把排序元素存在這個數組里，最后在賦值給原始數組。

找一個分界點，每次遞歸把元素分開，直到 l>=r 不符合條件為止，起始位置怎么可能>= 末尾位置。

if (l >= r)
	{return;
	}

	int mid = l + r >>1; //這個等價于(l + r) /2;

注：+ 的優先級是要比 >>高的，所以不用帶括號。

然后進行遞歸

MergeSort(q, l, mid);
	MergeSort(q, mid + 1, r);

這樣，就能把數組的元素分開了。分開之后，mid左邊的，起始位置就是l，末尾位置就是mid。
mid右邊的，起始位置就是mid + 1，末尾位置就是r。

然后進行排序，先把小的元素給tmp，大的元素最后在給

int i = l;
	int j = mid + 1;
	int k = 0;
	while (i<= mid && j<= r)
	{if (q[i]<= q[j])
		{	tmp[k++] = q[i++];
		}
		else
		{	tmp[k++] = q[j++];
		}
	}

i走到頭或者j走到頭，但是還有元素沒有放在tmp里怎么辦

while (i<= mid)
	{tmp[k++] = q[i++];
	}
	while (j<= r)
	{tmp[k++] = q[j++];
	}

在進行判斷就🆗了，

就是這樣，就可以把所有元素放在tmp數組里了。

最后把tmp里的元素給q，就完成了。

for (int i = l, j = 0; i<= r; i++)
	{q[i] = tmp[j++];
	}

三、代碼展示

#includeusing namespace std;

const int N = 1e6 + 10;

int q[N], tmp[N];

int n;

void MergeSort(int q[], int l, int r)
{if (l >= r)
	{return;
	}

	int mid = l + r >>1;
	MergeSort(q, l, mid);
	MergeSort(q, mid + 1, r);
	int i = l;
	int j = mid + 1;
	int k = 0;
	while (i<= mid && j<= r)
	{if (q[i]<= q[j])
		{	tmp[k++] = q[i++];
		}
		else
		{	tmp[k++] = q[j++];
		}
	}

	while (i<= mid)
	{tmp[k++] = q[i++];
	}
	while (j<= r)
	{tmp[k++] = q[j++];
	}

	for (int i = l, j = 0; i<= r; i++)
	{q[i] = tmp[j++];
	}
}

int main()
{cin >>n;
	for (int i = 0; i< n; i++)
	{cin >>q[i];
	}

	MergeSort(q, 0, n - 1);

	for (int i = 0; i< n; i++)
	{cout<< q[i]<< ' ';
	}

	return 0;
}

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

名稱欄目：歸并排序—C++實現-創新互聯
網頁地址：http://vcdvsql.cn/article2/csigoc.html

成都網站建設公司_創新互聯，為您提供關鍵詞優化、網站維護、微信小程序、外貿網站建設、手機網站建設、Google

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯