学步园

在网上看到一个两路归并排序的题目，闲着无聊，就把这个算法是实现了一下。

定义：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

#pragma once
class Cbind
{
public:
	Cbind(void);
	virtual ~Cbind(void);
public:
	int combine(int first[], int length1, int second[], int length2, int outcome[]);
};

#include "StdAfx.h"
#include "Cbind.h"


Cbind::Cbind(void)
{
}


Cbind::~Cbind(void)
{
}

int Cbind::combine(int first[], int length1, int second[],int length2, int outcome[])
{
	int *presult = outcome;
	int index1 = 0;
	int index2 = 0;
	int index = 0;
	int totallength = length1 + length2;

	while(index < totallength)
	{
		if (index1 < length1 && index2 < length2)
		{
			if (first[index1] < second[index2])
			{
				*presult = first[index1];
				index++;
				index1++;
				presult++;
			}
			else 
			{
				*presult = second[index2];
				index++;
				index2++;
				presult++;
			}
		}
		else if(index1 == length1 && index2 < length2)
		{
			for(int i=index2; i<length2; i++)
			{
				*presult = second[i];
				presult++;
				index++;
				index2++;
			}
		}
		else if(index2 = length2 && index1 < length1)
		{
			for(int i=index1; i<length1; i++)
			{
				*presult = first[i];
				presult++;
				index++;
				index1++;
			}
		}
	}
	return index;
}


// merge.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Cbind.h"


int _tmain(int argc, _TCHAR* argv[])
{
	int first[9] = {1, 3, 5, 7, 9, 11, 13, 15, 17};
	int second[5] = {2, 4, 6, 8,10};

	Cbind bind;
	int outcome[14];

	int length = bind.combine(first, 9, second, 5, outcome);

	for(int i=0; i<length; i++)
	{
		printf("index%d=%d\n", i, outcome[i]);
	}

	getchar();
	return 0;
}