实验十内部排序

实验十内部排序

完善“参考源程序”，进行典型内部排序算法的比较。
(1) 随机产生整数样本，进行8种排序，并比较各种排序算法的执行时间，如执行时间均为0，可考虑增大样本，如加大至5000或10000。
(2) 设计方案，修改“12.11.4 参考源程序”，对8种排序算法的数据元素比较次数和移动次数进行比较。
(3) 输出8种排序算法每一趟排序的输出结果。

# include <stdio.h>
# include <stdlib.h>
# include <time.h>
#include <windows.h>
 
#define WIDTH 20 
#define MAXK 10
 
int n=0;
long num,compare;
int da[2000000];
int dd[2000000];

void myhead(){
	printf("---    1.直接插入排序     	---\n");
	printf("---    2.折半插入排序     	---\n");
	printf("---    3.希尔排序      		---\n");
	printf("---    4.冒泡排序     		---\n");
	printf("---    5.快速排序     		---\n");
	printf("---    6.选择排序       	---\n");
	printf("---    7.堆排序     		---\n");
	printf("---    8.归并排序		---\n");
	printf("---    9.退出程序     		---\n");
	printf("\n");
}
 
void rand1()//随机数创建数组 
{
	int i;
	srand((unsigned)time(NULL)); /*随机种子*/
	for(i = 0; i < n; i ++) 
		dd[i] = rand();
}
 
void init()//将dd[]赋值给da[] 
{
	for(int i=0;i<n;i++)
		da[i]=dd[i];
	num=0;
	compare=0;
}
 
void swap(int *a,int *b)//数据交换 
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
	num++;
}

void BubbleSort()//冒泡排序 
{
	int i,j,k=0;
	for(i=0;i<n-1;i++)
		for(j=n-1;j>i;j--)
		{
			compare++;
			if(da[j]<da[j-1])
			swap(&da[j],&da[j-1]);
		}
	for(i=0;i<n;i++)
		printf("%d   ",da[i]);
	printf("\n");
}
 
void SelectSort()//选择排序 
{ 
	int i,j,temp;
	for(i=0;i<n-1;i++)
	{
		temp=i;
		for(j=i+1;j<n;j++)
		{
			compare++;
			if(da[j]<da[temp])
			{
				temp=j;
				num++;
			}
		}
		if(temp!=i)
			swap(&da[temp],&da[i]);
	}
	for(i=0;i<n;i++)
		printf("%d   ",da[i]);
	printf("\n");
}
 
void InsertSort()//插入排序 
{
	int i,j;
	int temp=0;
	for(i=1;i<n;i++)
	{
		temp=da[i];
		for(j=i;j>0 && temp<da[j-1];j--)
		{
			compare++;
			if(temp < da[j-1])
				swap(&da[j],&da[j-1]);
		}
		da[j] = temp;
	}
	for(i=0;i<n;i++)
		printf("%d   ",da[i]);
	printf("\n");
}
 

 
void qsort(int l,int r)//一趟快速排序 
{
	int i, j, x;
	if (l<r)
	{
		i=l;
		j=r;
		x=da[i];
		while(i<j)
		{
			while(i<j&&da[j]>x)
			{
				j--;
				compare++;
			}
			if(j<j)
				da[i++]=da[j];
			while(i<j&&da[i]<x)
			{
				i++;
				compare++;
			}
			if(i<j)
				da[j--]=da[i];
		 } 
		da[i]=x;
		num++;
		qsort(l,i-1);
		qsort(i+1,r);
	}
	
}
void QuickSort()//快速排序 
{
	qsort(0,n);	
	for(int i=0;i<n;i++)
		printf("%d   ",da[i]);
	printf("\n");
}

void HeapAdjust(int i, int nLength)
{
	int nChild, nTemp;
	for (nTemp=da[i];2*i+1<nLength;i=nChild)
	{
        	nChild=2*i+1;
        	compare++;
        	if (nChild!=nLength-1 && da[nChild+1]>da[nChild])
            	++nChild;
        	if (nTemp<da[nChild])
			{
				da[i]=da[nChild];
				num++;
        	}
			else{break;}
	}
	da[i]=nTemp;
}
void mydui()
{
	int i;
	for (i=n/2-1;i>=0;--i)
	{
		HeapAdjust(i,n);
	}
	for (i=n-1;i>0;--i)
	{
		swap(&da[0],&da[i]);
        HeapAdjust(0,i);
	}
	for(i=0;i<n;i++)
		printf("%d   ",da[i]);
	printf("\n");
 
}


void Merge(int left, int m, int right)
{
	int aux[200000]={0};
    	int i;
    	int j;
    	int k;
    	for (i=left,j=m+1,k=0;k<=right-left;k++){
		num++;
		compare++;
        	if (i==m+1)
			{
            	aux[k] = da[j++];
           		continue;
        	}
        	if(j==right+1)
			{
            	aux[k] = da[i++];
            	continue;
        	}
        	if(da[i]<da[j])
			{
            	aux[k] = da[i++];
        	}
			else
			{
            	aux[k]=da[j++];
			}
    	}
	for (i=left,j=0;i<=right;i++,j++){
		da[i]=aux[j];
	}
}
void MergeSort(int start,int end)//一次归并排序 
{
	if(start<end)
	{
        int i;
        i = (end + start) / 2;
        MergeSort(start, i);
        MergeSort(i + 1, end);
	    Merge(start, i, end);
    }
    
}
void myguibing()//归并排序 
{ 
	MergeSort(0,n-1);
	for(int i=0;i<n;i++)
		printf("%d   ",da[i]);
	printf("\n");
}
 
 
 void ShellSort()//希尔排序 
{
	int i, j, k;
	int t,g;  
	for (g=n/2;g>0;g/=2)
	{
        for (i=0;i<g;i++)
		{
			for(j=i+g;j<n;j+=g)
			{
				if (da[j]<da[j-g])
				{
					t=da[j];  
					k=j-g;
					while (k>=0 && da[k]>t)
					{
						da[k+g]=da[k];
						k-=g;
					}
					da[k+g]=t;
					num++;
				}
				compare++;
			}
				
		}
	}
 	for(i=0;i<n;i++)
		printf("%d   ",da[i]);
	printf("\n");
}

void BInsertSort()
{
 
	int left=0,right=n;
	int low,high,mid;
	int temp;
 
	for(int i=left+1;i<=right;++i)
	{
		temp=da[i]; 
		low=left; 
		high=i-1;    
		while(low<=high){    
			mid=(low+high)/2;
			if(da[i]<da[mid])  
				high=mid-1;            
			else     
				low=mid+1;
				compare++;
		}
		for(int j=i-1;j>=low;--j)
			da[j+1]=da[j];
		da[low]=temp;
		num++; 
	}
 for(int i=0;i<n;i++)
		printf("%d   ",da[i]);
	printf("\n");
}
 
double a=1;
long b=10000000;
long c=10000000;
void aaa(double t,long num,long compare,int i)
{
	if(t<a)
		a=t;
	if(num<b)
		b=num;
	if(compare<c)
		c=compare;	
	if(i)
	{
		printf("插入排序最短时间：        %f秒\n",a);
		printf("插入排序最少交换次数：    %ld\n",b);
		printf("插入排序最少比较次数：    %ld\n",c);
	}
		
}




int main()
{	
	clock_t t1,t2;
	double t;

	myhead();
	printf("请输入要产生的随机数的个数：");
	scanf("%d",&n);
	rand1();
	printf("\n");
	
	
	while(1){	
		init();	
		printf("\n");	
		printf("请选择排序算法：");
		int ch;
		scanf("%d", &ch);
		
		switch(ch){
			case 1 :
					t1=clock();
					InsertSort();
					t2=clock();
					t = (double)(t2-t1)/CLOCKS_PER_SEC;
					printf("插入排序时间：        %f秒\n",t);
					printf("插入排序交换次数：    %ld\n",num);
					printf("插入排序比较次数：    %ld\n",compare);
					
					aaa(t,num,compare,0);
					break;
					
					
			case 2 :	
					t1=clock();
					BInsertSort();
					t2=clock();
					t = (double)(t2-t1)/CLOCKS_PER_SEC;
					printf("折半插入时间：        %f秒\n",t); 
					printf("折半插入交换次数：    %ld\n",num);
					printf("折半插入比较次数：    %ld\n",compare);
					aaa(t,num,compare,0);
					break;
			case 3 : 					
					t1=clock();
					ShellSort();
					t2=clock();
					t = (double)(t2-t1)/CLOCKS_PER_SEC;
					printf("希尔排序时间：        %f秒\n",t);
					printf("希尔排序交换次数：    %ld\n",num);
					printf("希尔排序比较次数：    %ld\n",compare); 
					aaa(t,num,compare,0);
					break;
			case 4 : 					
					t1=clock();
					BubbleSort();
					t2=clock();
					t = (double)(t2-t1)/CLOCKS_PER_SEC;  //运行时间 
					printf("冒泡排序时间：        %f秒\n",t);
					printf("冒泡排序交换次数：    %ld\n",num);
					printf("冒泡排序比较次数：    %ld\n",compare);
					aaa(t,num,compare,0);
					break;
			case 5 : 					
					t1=clock();
					QuickSort();
					t2=clock();
					t = (double)(t2-t1)/CLOCKS_PER_SEC;
					printf("快速排序时间：        %f秒\n",t);
					printf("快速排序交换次数：    %ld\n",num);
					printf("快速排序比较次数：    %ld\n",compare); 
					aaa(t,num,compare,0);
					break;
			case 6 : 	
					t1=clock();
					SelectSort();
					t2=clock();
					t = (double)(t2-t1)/CLOCKS_PER_SEC;
					printf("选择排序时间：        %f秒\n",t);
					printf("选择排序交换次数：    %ld\n",num);
					printf("选择排序比较次数：    %ld\n",compare); 
					aaa(t,num,compare,0);
					break;	
			case 7 : 
					t1=clock();
					mydui();
					t2=clock();
					t = (double)(t2-t1)/CLOCKS_PER_SEC;
					printf("堆排序时间：        %f秒\n",t);
					printf("堆排序交换次数：    %ld\n",num);
					printf("堆排序比较次数：    %ld\n",compare);
					aaa(t,num,compare,0);
					break;
			case 8 : 					
					t1=clock();
					myguibing();
					t2=clock();
					t = (double)(t2-t1)/CLOCKS_PER_SEC;
					printf("归并排序时间：        %f秒\n",t); 
					printf("归并排序交换次数：    %ld\n",num);
					printf("归并排序比较次数：    %ld\n\n",compare);
					aaa(t,num,compare,1);
					break;
			case 9 : 
				return 0;	
		}
	}	
}

折半插入排序或快速排序输出的第一个数据莫名出现0，以后修改