快捷導航

超詳細解析C++實現(xiàn)歸并排序算法

更新時間：2022年09月26日 10:05:33 作者：sunny-ll

歸并排序是比較穩(wěn)定的排序方法。它的基本思想是把待排序的元素分解成兩個規(guī)模大致相等的子序列。本文將用C++實現(xiàn)這一排序算法，需要的可以參考一下

一、前言

分治算法

歸并排序，其實就是一種分治算法，那么在了解歸并排序之前，我們先來看看什么是分治算法。在算法設(shè)計中，我們引入分而治之的策略，稱為分治算法，其本質(zhì)就是將一個大規(guī)模的問題分解為若干個規(guī)模較小的相同子問題，分而治之。

分治算法解題方法

1.分解：

將要解決的問題分解為若干個規(guī)模較小、相互獨立、與原問題形式相同的子問題。

2.治理：

求解各個子問題。由于各個子問題與原問題形式相同，只是規(guī)模較小而已，而當子問題劃分得足夠小時，就可以用簡單的方法解決。

3.合并

按原問題的要求，將子問題的解逐層合并構(gòu)成原問題的解。

二、歸并排序

1.問題分析

歸并排序是比較穩(wěn)定的排序方法。它的基本思想是把待排序的元素分解成兩個規(guī)模大致相等的子序列。如果不易分解，將得到的子序列繼續(xù)分解，直到子序列中包含的元素個數(shù)為1。因為單個元素的序列本身就是有序的，此時便可以進行合并，從而得到一個完整的有序序列。

2.算法設(shè)計

（1）分解：

將待排序的元素分成大小大致一樣的兩個子序列。

（2）治理：

對兩個子序列進行個并排序。

（3）合并：

將排好序的有序子序列進行合并，得到最終的有序序列。

3.算法分析

首先我們先給定一個無序的數(shù)列（42，15，20，6，8，38，50，12），我們進行合并排序數(shù)列，如下圖流程圖所示：

步驟一：首先將待排序的元素分成大小大致相同的兩個序列。

步驟二：再把子序列分成大小大致相同的兩個子序列。

步驟三：如此下去，直到分解成一個元素停止，這時含有一個元素的子序列都是有序的。

步驟四：進行合并操作，將兩個有序的子序列合并為一個有序序列，如此下去，直到所有的元素都合并為一個有序序列。

舉例，下面我將以序列（4，9，15，24，30，2，6，18，20）進行圖解。

（1）初始化：i = low，j = mid+1，mid = (low+hight)/2 ，申請一個輔助數(shù)組 b

int* b = new int[hight - low + 1];  //用 new 申請一個輔助函數(shù)
	int i = low, j = mid + 1, k = 0;    // k為 b 數(shù)組的小標

（2）現(xiàn)在比較 a [i] 和 b[j] ，將較小的元素放在 b 數(shù)組中，相應(yīng)的指針向后移動，直到 i > mid 或者 j>hight 時結(jié)束。

while (i <= mid && j <= hight)  
 {
	if (a[i] <= a[j])
	{
		b[k++] = a[i++];  //按從小到大存放在 b 數(shù)組里面
	}
	else
	{
		b[k++] = a[j++];
	}
  }

進行第一次比較 a[i]=4 和 a[j]=2，將較小的元素 2 放入數(shù)組 b 中，j++,k++，如下圖：

進行第二次比較 a[i]=4 和 a[j]=6，將較小的元素放 4 入數(shù)組 b 中，i++,k++，如下圖：

進行第三次比較 a[i]=9 和 a[j]=6，將較小的元素放 6 入數(shù)組 b 中，j++,k++，如下圖：

進行第四次比較 a[i]=9 和 a[j]=18，將較小的元素放 9 入數(shù)組 b 中，i++,k++，如下圖：

進行第五次比較 a[i]=15 和 a[j]=18，將較小的元素放 15 入數(shù)組 b 中，i++,k++，如下圖：

進行第六次比較 a[i]=24 和 a[j]=18，將較小的元素放 18 入數(shù)組 b 中，j++,k++，如下圖：

進行第七次比較 a[i]=24 和 a[j]=20，將較小的元素放 20 入數(shù)組 b 中，j++,k++，如下圖：

此時，j>hight 了，while循環(huán)結(jié)束，但 a 數(shù)組還剩下元素（i<mid）可直接放入 b 數(shù)組就可以了。如下圖所示：

while (i <= mid)  // j 序列結(jié)束，將剩余的 i 序列補充在 b 數(shù)組中 
	{
		b[k++] = a[i++];
	}
	while (j <= hight)// i 序列結(jié)束，將剩余的 j 序列補充在 b 數(shù)組中 
	{
		b[k++] = a[j++];
	}

現(xiàn)在將 b 數(shù)組的元素賦值給 a 數(shù)組，再將 b 數(shù)組銷毀，即可。

for (int i = low; i <= hight; i++)  //將 b 數(shù)組的值傳遞給數(shù)組 a
	{
		a[i] = b[k++];
	}
	delete[]b;     // 輔助數(shù)組用完后，將其的空間進行釋放（銷毀）

（3）遞歸的形式進行歸并排序

void mergesort(int* a, int low, int hight) //歸并排序
{
	if (low < hight)
	{
		int mid = (low + hight) / 2;
		mergesort(a, low, mid);          //對 a[low,mid]進行排序
		mergesort(a, mid + 1, hight);    //對 a[mid+1,hight]進行排序
		merge(a, low, mid, hight);       //進行合并操作
	}
}

三、AC代碼

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
void merge(int* a, int low, int mid, int hight)  //合并函數(shù)
{
	int* b = new int[hight - low + 1];  //用 new 申請一個輔助函數(shù)
	int i = low, j = mid + 1, k = 0;    // k為 b 數(shù)組的小標
	while (i <= mid && j <= hight)  
	{
		if (a[i] <= a[j])
		{
			b[k++] = a[i++];  //按從小到大存放在 b 數(shù)組里面
		}
		else
		{
			b[k++] = a[j++];
		}
	}
	while (i <= mid)  // j 序列結(jié)束，將剩余的 i 序列補充在 b 數(shù)組中 
	{
		b[k++] = a[i++];
	}
	while (j <= hight)// i 序列結(jié)束，將剩余的 j 序列補充在 b 數(shù)組中 
	{
		b[k++] = a[j++];
	}
	k = 0;  //從小標為 0 開始傳送
	for (int i = low; i <= hight; i++)  //將 b 數(shù)組的值傳遞給數(shù)組 a
	{
		a[i] = b[k++];
	}
	delete[]b;     // 輔助數(shù)組用完后，將其的空間進行釋放（銷毀）
}
void mergesort(int* a, int low, int hight) //歸并排序
{
	if (low < hight)
	{
		int mid = (low + hight) / 2;
		mergesort(a, low, mid);          //對 a[low,mid]進行排序
		mergesort(a, mid + 1, hight);    //對 a[mid+1,hight]進行排序
		merge(a, low, mid, hight);       //進行合并操作
	}
}
int main()
{
	int n, a[100];
	cout << "請輸入數(shù)列中的元素個數(shù) n 為：" << endl;
	cin >> n;
	cout << "請依次輸入數(shù)列中的元素：" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	mergesort(a, 0, n-1);
	cout << "歸并排序結(jié)果" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}