马周游及旅行商问题

快速排序与归并排序的比较、马周游问题、旅行商算法、

#include
#include
#include
#include

void split_sort（int *array int low int high long &compares）;
void mergessort（int *array int *array1 int low  int high  long &compares）;
const int SIZEE = 50000;
const int MAXNUM = 5000000;
void rand_array（int *&arrayint *&array1int size）;

void output（int *array int size）
{
	for（int i = 0 ; i< size;  i++）
	{
		cout<	}
	cout<}
int main（）
{
	clock_t   start   finish;
	double t;
	srand（ （unsigned）time（ NULL ） ）;
	long compares = 0;
	long starttimecurrenttime;
	int n = 50;
	for（int i = 1 ; i <= n ; i++）
	{
		int num = i * SIZEE;
		int *array = new int[num];
		int *array1 = new int[num];
		rand_array（arrayarray1i*SIZEE）;
		compares = 0;

		start   =   clock（）;     

		split_sort（array 0i*SIZEE-1  compares）;	

		finish   =   clock（）; 
		t   =   （double）（finish   -   start） ;     

		cout<<“第“<			“ ms 比较次数是 ：“<		cout<		compares = 0;


		start   =   clock（）;   
		mergessort（array1 array  0i*SIZEE-1 compares）;

		finish   =   clock（）; 
		t   =   （double）（finish   -   start）; 

		cout<<“第“<			“ ms 比较次数是 ：“<		system（“pause“）;
		cout<		cout<		cout<	}
	return 0;
}


void rand_array（int *&arrayint *&array1  int size）
{
	for（int i = 0 ; i < size ; i++）
	{
		array[i] = rand（） % MAXNUM;
		array1[i] = array[i];
	}
	return ;
}

void change（int &a  int &b）
{
	int temp = a;
	a = b;
	b  = temp;
}
void split_sort（int *array int low int high long &compares）
{
	if（low >= high）
		return ;
	int mid = （low + high） / 2;
//	compares++;
	if（array[low] < array[mid]）
	{
		change（array[low]  array[mid]）;
	}
//	compares++;
	if（array[low] > array[high]）
	{
		change（array[low]  array [high]）;
	}	

	int n = low ; int m = high;int x = array[n];
	int temp;
	while（n < m）
	{
		while（（n < m） && array[m] >= x）
		{
			compares++;
			m--;
		}
		temp = array[n] ; 
		array[n] = array[m];
		array[m] = temp;
		while（（n < m）&& （array[n] <= x））
		{
			compares++;
			n++;
		}
		temp = array[n];
		array[n] = array[m];
		array[m] = temp;
	}
	change（array[low]array[n-1]）;
	
	split_sort（arraylown-1compares）;
	split_sort（arrayn+1highcompares）;
}

void mergessort（int *array int *array1   int low  int high  long &compares）
{
	if（low >= high ）
		return;
//	compares++;
	int mid = （low + high） / 2;
	mergessort（array array1 low mid compares ）;
	mergessort（array array1 mid+1 high compares）;

	for（int i = low ; i <= high ; i++）
	{
		array1[i] = array[i];
	}
	int n = low;
	int m = mid+1;
	int index  =low;
	while（n <= mid && m <= high）
	{
		compares++;
		if（array1[n] < array1[m]）
		{
			array[index++] = array1[n++];
		}
		else
		{
			array[index++] = arr

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3180  2013-06-24 19:20  ALo_1\Alo_1.cpp

     文件       4266  2013-07-29 22:36  ALo_1\ALo_1.dsp

     文件       1905  2013-06-24 08:48  ALo_1\ALo_1.dsw

     文件     246784  2013-12-31 00:43  ALo_1\ALo_1.ncb

     文件      89088  2013-12-31 00:43  ALo_1\ALo_1.opt

     文件       1074  2013-07-29 22:33  ALo_1\ALo_1.plg

     文件       2874  2013-06-24 11:07  ALo_1\alo_3\alo_3.cpp

     文件       4270  2013-06-10 20:20  ALo_1\alo_3\alo_3.dsp

     文件       1409  2013-12-18 20:38  ALo_1\alo_3\alo_3.plg

     文件     626763  2013-12-18 20:38  ALo_1\alo_3\Debug\alo_3.exe

     文件    1229384  2013-12-18 20:38  ALo_1\alo_3\Debug\alo_3.ilk

     文件     287707  2013-12-18 20:38  ALo_1\alo_3\Debug\alo_3.obj

     文件    3248244  2013-12-18 20:38  ALo_1\alo_3\Debug\alo_3.pch

     文件    1115136  2013-12-18 20:38  ALo_1\alo_3\Debug\alo_3.pdb

     文件     212413  2013-12-18 20:38  ALo_1\alo_3\Debug\alo_3.sbr

     文件      82944  2013-12-19 00:13  ALo_1\alo_3\Debug\vc60.idb

     文件     135168  2013-12-18 20:38  ALo_1\alo_3\Debug\vc60.pdb

     文件       4043  2013-06-18 22:19  ALo_1\alo_3_1\alo_3_1.cpp

     文件       4296  2013-06-17 23:58  ALo_1\alo_3_1\alo_3_1.dsp

     文件       1309  2013-12-19 00:13  ALo_1\alo_3_1\alo_3_1.plg

     文件     577615  2013-12-19 00:13  ALo_1\alo_3_1\Debug\alo_3_1.exe

     文件     811024  2013-12-19 00:13  ALo_1\alo_3_1\Debug\alo_3_1.ilk

     文件     301771  2013-12-19 00:13  ALo_1\alo_3_1\Debug\alo_3_1.obj

     文件    6462916  2013-12-19 00:13  ALo_1\alo_3_1\Debug\alo_3_1.pch

     文件    1131520  2013-12-19 00:13  ALo_1\alo_3_1\Debug\alo_3_1.pdb

     文件     197632  2013-12-30 22:25  ALo_1\alo_3_1\Debug\vc60.idb

     文件     159744  2013-12-19 00:13  ALo_1\alo_3_1\Debug\vc60.pdb

     文件        967  2013-06-15 15:22  ALo_1\MM_travel\fds.cpp

     文件       1147  2013-06-15 15:22  ALo_1\MM_travel\fds.h

     文件       1594  2013-06-15 16:24  ALo_1\MM_travel\MainFrm.cpp

............此处省略57个文件信息