merge_sort.h

一个合并排序算法。是按照《算法导论》书中的讲解来写的。

#include <vector>
#include <iostream>

using namespace std;

void merge(vector<int> & v, int p, int q, int r)
{
	int n1 = q - p + 1, n2 = r - q;
	vector<int> v1, v2;
	for(int i = 0; i < n1; i++)
	{
		v1.push_back(v[p + i]);
	}
	for(int i = 0; i < n2; i++)
	{
		v2.push_back(v[q + i + 1]);
	}
	int i = 0, j = 0, k = p;
	while(i < n1 && j < n2)
	{
		if(v1[i] <= v2[j])
		{
			v[k] = v1[i];
			i++;
		}
		else
		{
			v[k] = v2[j];
			j++;
		}
		k++;
	}
	if(i == n1)
	{
		while(j < n2)
		{
			v[k] = v2[j];
			j++;
			k++;
		}
	}
	else
	{
		while(i < n1)
		{
			v[k] = v1[i];
			i++;
			k++;
		}
	}
}

void merge_sort(vector<int> &v, int p, int r)
{
	if(p < r)
	{
		int q = (p + r) / 2;
		merge_sort(v, p, q);
		merge_sort(v, q + 1, r);
		merge(v, p, q, r);
	}
}