归并算法

爱被打了一巴掌 2022-06-09 06:10 114阅读 0赞

## 一、原理 ##

归并排序算法完全遵循分治模式。

操作：

分解：分解待排序的n个元素序列成各具n/2个元素的两个子序列。

解决：使用归并排序递归的排序两个子序列。

合并：合并两个已排序的子序列以产生已排序的答案。

## 二、合并算法 ##

两个子序列的合并（MERGE）过程如下列示意图所示：

![1361103947_3916.JPG][]

![1361103975_8842.JPG][]

伪码：

MERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q Let L[0.. n1] and R[0..n2] be new arrays for i = 0 to n1 - 1 L[i] = A[p + i] for j = 0 to n2 - 1 R[j] = A[q + j] i = j = 0; for k = p to r if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1

## 三、归并排序算法 ##

归并算法用示意图表示如下：

![1361104158_7962.JPG][]

归并排序算法的伪代码如下：

MERGE_SORT(A, p, r) if p < r q = (p + r) / 2 MERGE_SORT(A, p, q) MERGE_SORT(A, q + 1, r) MERGE(A, p, q, r)

## 四、程序实现 ##

#include<iostream>
    using namespace std;
    
    void MERGE_SORT(int arr[], int p, int r);
    void MERGE(int arr[], int p, int q, int r);
    void Print(int *arr);
    
    void MERGE_SORT(int arr[], int p, int r)
    {
    	int q;
    	if (p <r)
    	{
    		q = (p + r) / 2;
    		MERGE_SORT(arr,p, q);
    		MERGE_SORT(arr, q + 1, r);
    		MERGE(arr, p, q, r); 
    
    	}
    
    }
    
    void MERGE(int arr[], int p, int q, int r)
    {
    	int n1 = q - p + 1, n2 = r - q;
    	int L1[10], L2[10]; int i = 0;
    	for (; i < n1; i++)
    		L1[i] = arr[p+i];
    	
    	int j = 0;
    	for (; j < n2; j++)
    		L2[j] = arr[q+j];
    	L2[j] = -1;L1[i] = -1;
    	int i1 = 0, j1 = 0; 
    	for (int k=p; k <=r; k++)
    	{
    		if (L1[i1] <=L2[j1]&&L1[i1]!=-1)
    		{
    
    			arr[k] = L1[i1++];
    
    		}
    		else if (L1[i1] > L2[j1] && L2[j1] != -1)
    		{
    			arr[k] = L2[j1++];
    
    		}
    			
    	}
    
    		
    }
    
    void Print(int *arr)
    {
    	for (int i = 0; i < 8; i++)
    	{
    		cout << arr[i] << ' ';
    	}
    	cout << endl;
    }
    
    
    
    int main()
    {
    	int arr[8] = { 0,1,5,6,8,7,4,9 };
    	MERGE_SORT(arr, 0, 7);
    	Print(arr);
    
    	system("pause");
    	return 0;
    }

其中输出堆的终值处理不当，输出有误。

参考正确代码：

#include <iostream>  
    using namespace std;
    
    //将有二个有序数列a[first...mid]和a[mid...last]合并。  
    void __merge(int a[], int first, int mid, int last, int temp[])
    {
    	int i = first, j = mid + 1;
    	int m = mid, n = last;
    	int k = 0;
    
    	while (i <= m && j <= n)
    	{
    		if (a[i] <= a[j])
    			temp[k++] = a[i++];
    		else
    			temp[k++] = a[j++];
    	}
    
    	while (i <= m)
    		temp[k++] = a[i++];
    
    	while (j <= n)
    		temp[k++] = a[j++];
    
    	for (i = 0; i < k; i++)
    		a[first + i] = temp[i];
    }
    
    void __merge_sort(int a[], int first, int last, int temp[])
    {
    	if (first < last)
    	{
    		int mid = (first + last) / 2;
    		__merge_sort(a, first, mid, temp);
    		__merge_sort(a, mid + 1, last, temp);
    		__merge(a, first, mid, last, temp);
    	}
    }
    bool MergeSort(int a[], int n)
    {
    	int *p = new int[n];
    	if (p == NULL)
    	{
    		return false;
    	}
    	else
    	{
    		__merge_sort(a, 0, n - 1, p);
    		delete[] p;
    		return true;
    	}
    }
    
    int main()
    {
    	const int LEN = 10;
    
    	int a[LEN] = { 23, 40, 45, 19, 12, 16, 90, 39, 87, 71 };
    
    	cout << "Before the merge sort, the Array is:" << endl;
    	for (int i = 0; i < LEN; ++i)
    	{
    		cout  << a[i] << " ";
    	}
    	cout << endl;
    	cout << endl;
    	MergeSort(a, LEN);
    	cout << "After the merge sort, the Array is:" << endl;
    	for (int i = 0; i < LEN; ++i)
    	{
    		cout  << a[i] << " ";
    	}
    	cout << endl;
    	system("pause");
    	return 0;
    }

## 五、算法复杂度 ##

该算法的时间复杂度为O(nlogn)

[1361103947_3916.JPG]: https://img-my.csdn.net/uploads/201302/17/1361103947_3916.JPG
[1361103975_8842.JPG]: https://img-my.csdn.net/uploads/201302/17/1361103975_8842.JPG
[1361104158_7962.JPG]: https://img-my.csdn.net/uploads/201302/17/1361104158_7962.JPG