《算法导论》—

前言：

　　在今后的日子里，我将持续更新博客，讨论《算法导论》一书中的提到的各算法的C++实现。初来乍到，请多指教。

今日主题：　　

　　今天讨论《算法导论》第二章算法基础中的归并排序算法。下面是该算法的代码Merge.h：

#include <stdlib.h>

namespace dksl

{

	/*

	* 归并

	* numArray为整形数组

	* head为要归并的数组的开始位置索引

	* waist为要归并的数组的中间位置索引

	* tail-1为要归并的数组的结束位置索引

	*/

	void merge(int *numArray,const int head,const int waist,const int tail)

	{

		int begin=head,start=waist,index=0;

		int length=tail-head;

		int* temp=new int[length];

		if(temp==nullptr)

			throw "系统为程序分配内存失败";

		while(begin<waist&&start<tail)

		{

			if(numArray[begin]<numArray[start])

				temp[index++]=numArray[begin++];

			else

				temp[index++]=numArray[start++];

		}

		if(begin==waist)

		{

			while(start<tail)

				temp[index++]=numArray[start++];

		}

		else if(start==tail)

		{

			while(begin<waist)

				temp[index++]=numArray[begin++];

		}

		//memcpy(numArray+head, temp, sizeof(int)*length);

		int i=0;

		for(i,index=head;i<length;i++,index++)

		{

			numArray[index]=temp[i];

		}

		delete(temp);

	}

	void sort(int *numArray,const int head,const int tail)

	{

		int length = tail - head;

		int  begin = head, middle = ((head+tail)%2 == 0) ? (head+tail)/2 : (head+tail+1)/2, end = tail;

		if(length < 2)

			return;

		else if(length == 2)

			merge(numArray,begin,middle,end);

		else

		{

			if( middle- begin > 1)

				sort(numArray,begin,middle);

			if( end- middle > 1)

				sort(numArray,middle,end);

			merge(numArray,begin,middle,end);

		}

	}

}

　　c++动态数组分配很方便，“int* temp=new int[length]; ”length在程序运行过程中确定。为了养成良好的习惯，请在定义的指针空间使用完后，将其删除。

　　下面是本算法的测试代码MergeSort.cpp：

#include "stdafx.h"

#include <iostream>

#include "Merge.h"

using namespace std;

using namespace dksl;

int _tmain(int argc, _TCHAR* argv[])

{

	int a[10] = {1, 4, 8, 5, 10, 25, 54, 15, 12, 2};

	int i = 0;

	sort(a, 0, 10);

	cout<<"The sorted array is:";

	for(i = 0; i < 10; i++)

		cout<<a[i]<<" ";

	cout<<endl;

	system("PAUSE");

	return 0;

}

　　运行结果：

巴特西

《算法导论》——MergeSort

最新文章

热门文章