cxj.cpp

内排序：插入、归并、基数、堆、快速排序vc6.0环境下通过编译

//CourseDesign.cpp
#include "stdio.h"
#include "time.h"
#include "stdlib.h"
#include <conio.h>
#include <string.h>
#include <malloc.h>
//#include "huffman.h"

#define MAXSIZE 10000

//global variable
clock_t tstart=0;
int *A=new int[MAXSIZE];
int *B=new int[MAXSIZE];

//global function 
void   PrintMainInterface();
void   PrintSortInterface();
void   Settime();
double Gettime();
void   InsertSort();
void   MergeSort(int A[],int left,int right);
void   QuickSort(int A[],int i,int j);
void   HeapSort(int A[], int length);
void   RadixSort(int A[],int B[],int n,int k,int r);
void   Huffman();
void   ShortestPath();

void   Randomize(){srand(1);}
void   swap(int A[],int i,int j)
{
	int temp=A[i];
	A[i]=A[j];
	A[j]=temp;
}

void main()
{
	Randomize();
	for(int i=0;i<MAXSIZE;i++)
	{
		A[i]=rand();
		B[i]=A[i];
	}

	int ch;
	while(1)
	{
		PrintMainInterface();
		while(1)
		{
			ch=getchar();
			if(ch>'0' && ch<'6')break;
		}
		if(ch=='5')         //exit
		{
			printf("\n");
			break;
		}
		if(ch=='1')
		{
			while(1)
			{
				PrintSortInterface();
				while(1)
				{
					ch=getchar();
					if(ch>'0' && ch<'7')break;
				}
				if(ch=='6')  //return main menu
					break;
				printf("Waiting...");
				for(int i=0;i<MAXSIZE;i++)
					A[i]=B[i];
				Settime();
				if(ch=='1')
				{
					InsertSort();
					printf("\nYou have selected insert sorting algorithm.");
				}
				else if(ch=='2')
				{
					MergeSort(A,0,MAXSIZE-1);
					printf("\nYou have selected merge sorting algorithm.");
				}
				else if(ch=='3')
				{
					QuickSort(A,0,MAXSIZE-1);
					printf("\nYou have selected QuickSort sorting algorithm.");
				}
				else if(ch=='4')   //heap sorting
				{   HeapSort(A,MAXSIZE-1);
					printf("\nYou have selected heap sorting algorithm.");}
				else if(ch=='5')   //radix sorting
				{   RadixSort(A,B,MAXSIZE-1,MAXSIZE-1,10);
					printf("\nYou have selected radix sorting algorithm.");}

				double cost=Gettime();
				printf("\nPrint unsorted array?(Y/N):");
				while(1)
				{
					ch=getchar();
					if(ch=='y' || ch=='Y' || ch=='n' || ch=='N')break;
				}
				if(ch=='y' || ch=='Y')
				{
					for(int i=0;i<5;i++)
						printf("\n%10d%10d%10d%10d%10d",
						    B[5*i],B[5*i+1],B[5*i+2],B[5*i+3],B[5*i+4]);
				}
				printf("\nPrint sorted array?(Y/N):");
				while(1)
				{
					ch=getchar();
					if(ch=='y' || ch=='Y' || ch=='n' || ch=='N')break;
				}
				if(ch=='y' || ch=='Y')
				{
					for(int i=0;i<5;i++)
						printf("\n%10d%10d%10d%10d%10d",
						    A[5*i],A[5*i+1],A[5*i+2],A[5*i+3],A[5*i+4]);
				}
				printf("\nThe time for sorting is :%lf seconds",cost);
			}
		}
		else if(ch=='2') //Huffman coding
		{
}

		
		else if(ch=='3') //shortest path
		{
		}
		else if(ch=='4') //MST
		{
		}
	}
}


void   PrintMainInterface()
{
	char* str=
		"\n\n\n\
		-----------------------------------------------------------\n\
		1.SORT\n\
		2.HUFFMAIN CODE AND DECODE\n\
		3.DIJKSTRA SHORTEST PATH\n\
		4.MST\n\
		5.EXIT\n\
		-----------------------------------------------------------\n";
	printf("%s",str);
	printf("Please input type of operation(1-5): ");
}
void   PrintSortInterface()
{
		char* str=
		"\n\n\n\
		-----------------------------------------------------------\n\
		1.INSORT SORTING\n\
		2.MERGE SORTING\n\
		3.QUICK SORTING\n\
		4.HEAP SORTING\n\
		5.RADIX SORTING\n\
		6.RETURN\n\
		-----------------------------------------------------------\n";
	printf("%s",str);
	printf("Please input type of operation(1-6): ");

}
void   Settime()
{
	tstart=clock();
}
double Gettime()
{
	return (double)((double)clock()-(double)tstart)/(double)CLOCKS_PER_SEC;
}

void   InsertSort()
{int i,j;
for(i=1;i<MAXSIZE;i++)
for(j=i;(j>0)&&(A[j]<A[j-1]);j--)
swap(A,j,j-1);
}
void   MergeSort(int A[],int left,int right)
{int mid=(left+right)/2;
int temp[MAXSIZE];
if(left==right)    return;
MergeSort(A,left,mid);
MergeSort(A,mid+1,right);
for(int i=left;i<=right;i++)
temp[i]=A[i];
int i1=left;int i2=mid+1;
for(int curr=left;curr<=right;curr++)
{if(i1==mid+1)
A[curr]=temp[i2++];
else if(i2>right)
A[curr]=temp[i1++];
else if(temp[i1]<temp[i2])
A[curr]=temp[i1++];
else A[curr]=temp[i2++];
}
}
int partition(int A[],int l,int r,int &pivot)
{do{
	while(A[++l]<pivot);
	while((r!=0)&&A[--r]>pivot);
	swap(A,l,r);
}while(l<r);
swap(A,l,r);
return l;
}

void QuickSort(int A[],int i,int j)
{if(j<=i) return;
int pivotindex=(i+j)/2;
swap(A,pivotindex,j);
int k=partition(A,i-1,j,A[j]);
swap(A,k,j);
QuickSort(A,i,k-1);
QuickSort(A,k+1,j);
}
void exchange(int *a, int *b)
{   int temp;
    temp = *a;
    *a   = *b;
    *b   = temp;
}
void HeapAdjust(int A[], int i, int length)
{    int child, temp;
     for (temp = A[i]; 2 * i + 1 < length; i = child)
    {   child = 2 * i + 1;
        if (child != length - 1 && A[child + 1] > A[child])
            ++child;
		if (temp < A[child])
        {   A[i] = A[child];
        }
        else    
        {
            break;
        }
    }
    A[i] = temp;
}
void HeapSort(int A[], int length)
{   for (int i = length / 2 - 1; i >= 0; --i)
    {
        HeapAdjust(A, i, length);
    }
     for (i = length - 1; i > 0; --i)
    {exchange(&A[0], &A[i]);
	 HeapAdjust(A, 0, i);
    }
}
void RadixSort(int A[],int B[],int n,int k,int r)
{int *cnt=new int[r];
int j;int rtok=1;
for(int i=0;i<k;i++,rtok*=r)
{for(j=0;j<r;j++)
cnt[j]=0;
for(j=0;j<n;j++)
cnt[(A[j]/rtok)%r]++;
for(j=1;j<r;j++)
cnt[j]=cnt[j-1]+cnt[j];
for(j=n-1;j>=0;j--)
B[--cnt[(A[j]/rtok)%r]]=A[j];
for(j=0;j<n;j++)
A[j]=B[j];
}
}

void   ShortestPath(){}