mergesort.cpp

快速排序算法

#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include <string.h>

typedef struct 
{
	int value;
	char s[55];
}Item;

void merge(int x[],int swap[],int k ,int n);
void mergesort(int x[],int N)
{
	int i ,k;
	int temp;
	int swap[78];
	k = 1;
	while( k < N)
	{
		temp = k;
		merge(x,swap,temp,N);
		cout << " k = " << k << endl;
		for( i = 0;i < N;i ++)
		{
			x[i] = swap[i];
			cout << x[i] << " ";
		}
		cout << endl;
		 k = k * 2;
	}

	for(int j = 0;j < N ; j++ )
	{
		cout << x[j ] << "  ";
	}
}

void merge(int x[],int swap[],int k ,int n)
{
	int i,j,l1,u1,l2,u2,m;
	l1 = 0;
	m = 0;
	while(l1 + k < n)
	{
		l2 = l1 + k;
		u1 = l2 - 1;
		u2 = (l2 + k - 1 <= n - 1) ? (l2 + k - 1) :(n - 1);	

		for( i  = l1,j = l2; i <= u1 && j <= u2 ;m++)
		{
			if(x[i] >= x[j])
			{
				swap[m] = x[i];
				i ++;
			}
			else
			{
				swap[m] = x[j];
				 j++;
			}
		}

		while(i <=  u1)
		{
			swap[m] = x[i];
			m ++;
			i ++;
		}
		while(j <= u2)
		{
			swap[m] = x[j];
			m ++;
			j ++;
		}
		l1 = u2 + 1;	
	}
	for( i =l1;i < n && m < n; i ++,m++)
		swap[m ] = x[i];
}



int main()
{
	int i = 0;
	int j;

	int r[40] = {12 ,32,9 ,6,9,1200,456,369,18,47,
		6 ,4 ,5,2,3,789,596,963,74,86,
		4800 ,2,3000,45,603,78979,98566,9663,385,789474,
		36,789,6,60000,2,784,9666,96328,354,900
	};
	int Count;
	cin >>Count;
	cout <<"*******************" <<endl;

	for(j = 0;j < Count ; j++ )
	{
		cout << r[j] << "  " ;
	}
	cout << endl;

	mergesort(r,Count);


	return  0;
}

/*
int i,j;
Item r[100],r1[100];
int merge(Item r[],Item r2[],int l,int m,int n);
int mergesort(Item r[],Item r1[],int s,int t)
{
	Item r2[100];
	if(s == t)
		r1[s] = r[s];
	else
	{
		mergesort(r,r2,s,(s+t)/2);
		mergesort(r,r2,(s+t)/2+1,t);
		merge(r2,r1,s,(s+t)/2,t);
	}
	return 0;
}
int merge(Item r[],Item r2[],int i,int m,int n)
{
	int j,k;
	int l = i;

	for(j = m + 1,k = i; l <= m && j <= n;++k)
	{
		if(r[l].value < r[j].value)
			r2[k].value = r[l ++].value;
		else
			r2[k].value = r[j ++].value;
	}


	while(l <= m)
	{
		r2[k++].value = r[l ++].value;
	}
	
	while(j <= n)
	{
		r2[k++].value = r[j ++].value;
	}
	return 0;
}

*/