這篇文章主要講解了“c++如何實(shí)現(xiàn)二路歸并排序”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“c++如何實(shí)現(xiàn)二路歸并排序”吧！

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)！專(zhuān)注于網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、微信小程序開(kāi)發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶(hù)創(chuàng)新互聯(lián)還提供了淅川免費(fèi)建站歡迎大家使用！

二路歸并排序

基本思想

二路歸并排序就是將兩個(gè)有序子表歸并成一個(gè)有序表。首先我們得有一個(gè)算法用于歸并：兩個(gè)有序表放在同一數(shù)組的相鄰位置上，arr[left]到arr[center-1]為第一個(gè)有序表，arr[center]到arr[right]是第二個(gè)有序表。每次從兩端中取出一個(gè)進(jìn)行比較，小的先放在一個(gè)temp數(shù)組，最后將比較剩下的直接放到temp中去，最后將temp又復(fù)制回arr。這是“治”。
所謂“分”，就是遞歸地將前半部分和后半部分的數(shù)據(jù)各自歸并排序即可。

算法分析

每一趟歸并的時(shí)間復(fù)雜度為O(n)，共需要進(jìn)行?log2n?趟。對(duì)應(yīng)的算法的時(shí)間復(fù)雜度為O(nlog2n)。歸并排序的空間復(fù)雜度O(n)。另外，歸并排序中歸并的算法并不會(huì)將相同關(guān)鍵字的元素改變相對(duì)次序，所以歸并排序是穩(wěn)定的。
二路歸并排序的前提是兩個(gè)序列本身有序。

void Merger(int *arr, int len, int width)
{
 int *temp =(int *)malloc(sizeof(int) * (len));
 //首先對(duì)兩路下標(biāo)分別進(jìn)行初始化
 int l1 = 0;
 int h2 = l1 + width - 1;
 int l2 = h2 + 1;
 int h3 = l2 + width - 1 < len - 1 ? l2 + width - 1 : len - 1;
 int temppos = 0;
 //判斷所在下標(biāo)位置的值
 while (l1 < len && l2 < len)
 {
 while (l1 <= h2 && l2 <= h3)
 {
  if (arr[l1] < arr[l2])
  {
  temp[temppos++] = arr[l1++];
  }
  else
  {
  temp[temppos++] = arr[l2++];
  }
 }
 //l1有剩余
 while (l1 <= h2)
 {
  temp[temppos++] = arr[l1++];
 }
 //l2有剩余
 while (l2 <= h3)
 {
  temp[temppos++] = arr[l2++];
 }
 //l1 l2向后移動(dòng)
 l1 = h3 + 1;
 h2 = (l1 + width - 1) < (len - 1) ? (l1 + width - 1) : (len - 1);
 l2 = h2 + 1;
 h3 = (l2 + width - 1) < (len - 1) ? (l2 + width - 1) : (len - 1);
 }
 //奇數(shù)歸并塊 剩下的一個(gè)單都?jí)K操作
 while (l1 
PS:二路合并排序算法
#include
using namespace std;
class SortableList
{
public:
	SortableList(int mSize)
	{
		maxSize = mSize;
	  l= new int[maxSize];
		n = 0;
	}
	~SortableList()
	{
		delete[]l;
	}
	void Merge(int, int, int);
	void MergeSort(int,int);
	void Input();
	void Output();
	
   private:
		 int* l;
		 int maxSize;
		 int n;

};
void SortableList::Input()
{
	cout << "請(qǐng)輸入要排序的數(shù)：";
	for (int i = 0; i <= maxSize - 1; i++)
		cin >> l[i];
}
void SortableList::Output()
{
	cout << "排序后的數(shù)是：";
	for (int i = 0; i <= maxSize - 1; i++)
		cout << l[i]<<' ';
}
void SortableList::MergeSort(int left,int right)
{
	if (left < right)//如果序列長(zhǎng)度大于1則劃分
	{
		int mid = (left + right) / 2;
		MergeSort(left, mid);//對(duì)左序列進(jìn)行排序
		MergeSort(mid + 1, right);//對(duì)右序列進(jìn)行排序
		Merge(left, mid, right);//合并
	}
}
void SortableList::Merge(int left, int mid, int right)
{
	int* temp= new int[right - left + 1];
	int i = left, j = mid + 1, k = 0;
	while ((i <= mid) && (j <= right))//判斷序列是否為空
		if (l[i] <= l[j])
			temp[k++] = l[i++];
		else temp[k++] = l[j++];
	while (i <= mid)
		temp[k++] = l[i++];//右序列空了左序列依次寫(xiě)入
	while (j <= right)
		temp[k++] = l[j++];//左序列空了右序列依次寫(xiě)入
	for (i = 0, k = left; k <= right;)
		l[k++] = temp[i++];//臨時(shí)在數(shù)組temp中的排列好的數(shù)據(jù)放入數(shù)組l
}
int main()
{
	int m;
	cout << "請(qǐng)輸入要排序的數(shù)的數(shù)目：";
	cin >> m;
	SortableList a1(m);
	a1.Input();
	a1.MergeSort(0, m-1);
	a1.Output();
}
感謝各位的閱讀，以上就是“c++如何實(shí)現(xiàn)二路歸并排序”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)c++如何實(shí)現(xiàn)二路歸并排序這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！
            
            
                        

            名稱(chēng)欄目：c++如何實(shí)現(xiàn)二路歸并排序            

            鏈接分享：http://weahome.cn/article/peeihs.html