归并排序

前几天遇到了一道题，快排过不去，一定要用mergesort，特来学习一下。

该算法时间复杂度为O(NlogN).

当数据量很大的时候 nlogn的优势将会比n^2越来越大，当n=10^5的时候，nlogn的算法要比n^2的算法快6000倍，那么6000倍是什么概念呢，就是如果我们要处理一个数据集，用nlogn的算法要处理一天的话，用n^2的算法将要处理6020天。这就基本相当于是15年。一个优化改进的算法可能比一个比一个笨的算法速度快了许多，这就是为什么我们要学习算法的原因。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

void merge(int a[], int l, int r, int mid) //并的思想
{
	int *aux = new int[r - l + 1], i, j, k;
	for (k = l; k <= r; k++)
		aux[k - l] = a[k];
	i = l;
	j = mid + 1;
	for (k = l; k <= r; k++)
	{
		if (i > mid)
		{
			a[k] = aux[j - l];
			j++;
		}
		else if (j > r)
		{
			a[k] = aux[i - l];
			i++;
		}
		else if (aux[i - l] > aux[j - l])
		{
			a[k] = aux[j - l];
			j++;
		}
		else
		{
			a[k] = aux[i - l];
			i++;
		}
	}
}
void merge_sort(int a[], int l, int r)//归的思想
{
	if (l >= r)
		return;
	int mid = (l + r) / 2;
	merge_sort(a, l, mid);
	merge_sort(a, mid + 1, r);
	merge(a, l, r, mid);
}
void mergesort(int a[], int l, int r)//再写个函数，方标调用
{
	merge_sort(a, l, r - 1);
}

int main()
{
	int a[105], n, i;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	mergesort(a, 0, n);
	for (i = 0; i < n; i++)
		printf("%d ", a[i]);
	return 0;
}

下附运行结果：