testdatainf.cpp

5种排序功能的实现

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <windows.h>
#include <iostream.h>
#include <time.h>
int myrand(int maxnum);
void bubble(int *a,int n);
void choise(int *a,int n);
void quick(int *a,int i,int j);
void insert(int *a,int n);
void shell(int *a,int n);
void print(int *a,int n);
void main()
{
	int a = -1200;
	unsigned b = -130;
	srand((unsigned)time(NULL));
	printf("a = %d, b = %d, random num =%d \n",a,b,myrand(15));
	int a1[]={13,0,5,8,1,7,21,50,9,2};
	int a2[]={13,0,5,8,1,7,21,50,9,2};
	int a3[]={13,0,5,8,1,7,21,50,9,2};
	int a4[]={13,0,5,8,1,7,21,50,9,2};
	int a5[]={13,0,5,8,1,7,21,50,9,2};
	printf("the original list:");
	print(a1,10);
	printf("according to bubble:");
	bubble(a1,10);
	print(a1,10);
	printf("according to choise:");
	choise(a2,10);
	print(a2,10);
	printf("according to quick:");
	quick(a3,
	0,9);
	print(a3,10);
	printf("according to insert:");
	insert(a4,10);
	print(a4,10);
	printf("according to shell:");
	shell(a5,10);
	print(a5,10);

}

int myrand(int maxnum)
{
	return rand()%maxnum;
}

void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/
{
	int i,j,temp;
	for(i=0;i<n-1;i++)
		for(j=i+1;j<n;j++) /*注意循环的上下限*/
			if(a[i]>a[j]) 
			{
				temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
}

void choise(int *a,int n)
{
	int i,j,k,temp;
	for(i=0;i<n-1;i++) 
	{
		k=i; /*给记号赋值*/
		for(j=i+1;j<n;j++)
		if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/
		if(i!=k) 
		{ /*当k!=i是才交换，否则a[i]即为最小*/
			temp=a[i];
			a[i]=a[k];
			a[k]=temp;
		}
	}
}

void quick(int *a,int i,int j)
{
	int m,n,temp;
	int k;
	m=i;
	n=j;
	k=a[(i+j)/2]; /*选取的参照*/
	do 
	{
		while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/
			while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/
				if(m<=n) 
				{ /*若找到且满足条件，则交换*/
					temp=a[m];
					a[m]=a[n];
					a[n]=temp;
					m++;
					n--;
				}
	}
	while(m<=n);
	if(m<j) 
		quick(a,m,j); /*运用递归*/
	if(n>i) 
		quick(a,i,n);
}

void insert(int *a,int n)
{
	int i,j,temp;
	for(i=1;i<n;i++) 
	{
		temp=a[i]; /*temp为要插入的元素*/
		j=i-1;
		while(j>=0&&temp<a[j]) 
		{ /*从a[i-1]开始找比a[i]小的数，同时把数组元素向后移*/
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=temp; /*插入*/
	}
}

void shell(int *a,int n)
{
	int i,j,k,x;
	k=n/2; /*间距值*/
	while(k>=1) 
	{
		for(i=k;i<n;i++) 
		{
			x=a[i];
			j=i-k;
			while(j>=0&&x<a[j]) 
			{
				a[j+k]=a[j];
				j-=k;
			}
			a[j+k]=x;
		}
		k/=2; /*缩小间距值*/
	}
}

void print(int *a,int n)
{
	int i;
	for(i=0;i<n;i++)
		printf("%5d",a[i]);
		printf("n \n");
}