首页 > 代码库 > 归并排序

归并排序

#include <iostream>using namespace std;void merge(int a[], int p, int q, int r){	int n1 = q - p + 1;	int n2 = r - q;	int* L = new int[n1 + 2];	int* R = new int[n2 + 2];	L[n1+1]=0x7fffffff;	R[n2+1]=0x7fffffff;	//复制数组	for(int i = 1; i <= n1; i++)		L[i] = a[p + i - 1];	//复制数组	for(int i = 1; i <= n2; i++)		R[i] = a[q + i];	int i = 1;	int j = 1;	//合并	for(int k = p; k <= r; k++)	{		if(L[i] <= R[j])		{			a[k] = L[i];			i++;		}		else		{			a[k] = R[j];			j++;		}	}}void mergesort(int a[], int p, int r){	if(p < r)	{		int q = (p + r) / 2;		mergesort(a, p, q);		mergesort(a, q + 1, r);		merge(a, p, q, r);	}}int main(){	/*	 * 归并排序	 *将一个问题的模n分解成n/2个子问题	 *将子问题n分解成n/2个子问题	 *最小子问题的模等于1	 *初始化:	 *保持:	 *终止:	 */	int a[] = { 0, 8, 6, 7, 1, 5, 4, 2, 3 };	mergesort(a, 1, 8);	for(int i = 1; i <= 8; i++)		cout << a[i] << " ";	cout << endl;	return 0;}

  

归并排序