sort.c

算法导论上面各种排序算法的实现及排序性能比较的c语言实现代码

//file  sort.c

#include "sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h> 

void merge(double array[], int p, int q, int r) 
{     
    int n1, n2;
	int i,j,k;
    n1 = q - p + 1;     
    n2 = r - q;        
    for(i = 0, k = p; i < n1; i++, k++)         
        L[i] = array[k];     
    for(i = 0, k = q + 1; i < n2; i++, k++)         
        R[i] = array[k];     
    for(k = p, i = 0, j = 0; i < n1 && j < n2; k++)     
    {         
        if(L[i] <= R[j])         
        {             
            array[k] = L[i];             
            i++;         
        }         
        else         
        {             
            array[k] = R[j];             
            j++;         
        } 
    }
    if(i < n1)     
    {         
        for(j = i; j < n1; j++, k++)             
        array[k] = L[j];     
    }     
    if(j < n2)     
    {         
        for(i = j; i < n2; i++, k++)             
            array[k] = R[i];     
    }  
}


void merge_sort(double array[], int p, int r) 
{     
    if(p < r)     
    {         
        int q = (p + r) / 2;         
        merge_sort(array, p, q);         
        merge_sort(array, q + 1, r);         
        merge(array, p, q, r);     
    } 
} 



double mergesort(double array[],int size)
{
	clock_t start,end;
	start = clock();
	merge_sort(array,0,size - 1);
	end = clock();
	return (double)(end - start) / CLOCKS_PER_SEC;
}




double insertsort(double array[],int n)
{
	clock_t start,end;
	int i,j;
	double temp;
	start = clock();
	for(j=1;j<n;j++)
	{
		temp = array[j];
		i = j-1;
		while ((i>=0) && (array[i]>temp))
		{
			array[i+1] = array[i];
			i = i - 1;
		}
		array[i+1] = temp;
	}
	end = clock();
	return (double)(end - start) / CLOCKS_PER_SEC;
}


double shellsort(double array[], int n)
{
	clock_t start,end;
	int h, i, k;
	double temp;
	start = clock();
	for (h=n/2; h>0; h=h/2)
	{
		for (i=h; i<n; i++)
		{
			temp = *(array+i); 
			for (k=i-h; (k>=0 && temp<*(array+k)); k-=h) 
			{
				*(array+k+h) = *(array+k); 
			}
			*(array+k+h) = temp; 
		}
	}
	end = clock();
	return (double)(end - start) / CLOCKS_PER_SEC;
}


void swap(double *a, double *b)
{
	double temp = *a;
	*a = *b;
	*b = temp;
}


int partition(double *array, int low, int high)
{
	double temp = array[high];
	int i,j;
	i = low - 1;
	for(j = low;j<high;j++)
	{
		if(array[j]<=temp)
		{
			i = i + 1;
			swap(&array[i],&array[j]);
		}
	}
	swap(&array[i+1],&array[high]);
	return i + 1;
}

void quick_sort(double *array, int low, int high)
{
	int q;
	if(low<high)
	{
		q = partition(array,low,high);
		quick_sort(array,low,q-1);
		quick_sort(array,q+1,high);
	}
}


double quicksort(double *array, int size)
{
	clock_t start,end;
	start = clock();
	quick_sort(array, 0, size-1);
	end = clock();
	return (double)(end - start) / CLOCKS_PER_SEC;
}


double bubblesort(double *array, int size)
{
	int i, j;
	double temp;
	clock_t start,end;
	start = clock();
    for (i=size-1; i>0; i--)
		for (j=0; j<i; j++)
			if (array[j] > array[j+1]) 
			{
				temp = array[j+1];
				array[j+1] = array[j];
				array[j] = temp;
			}
	end = clock();
	return (double)(end - start) / CLOCKS_PER_SEC;
}


//初始化桶
void init(headnode *b)
{
	int i;
	for(i=0;i<10;i++)
	{
		b[i].num = 0;
	}
}

//向桶中插入数据
void insertelements(headnode b[],double array[],int size)
{
	int i,k;
	for(i=0;i<size;i++)
	{
		k = (int)(array[i]*10);
		if(k == 10)
		{
			b[k-1].b_array[b[k-1].num] = array[i];
			b[k-1].num = b[k-1].num + 1;
		}
		else
		{
			b[k].b_array[b[k].num] = array[i];
			b[k].num = b[k].num + 1;
		}
	}
}

//对桶进行排序
void sortelements(headnode b[])
{
	int i;
	for(i = 0;i < 10;i++)
	{
		quicksort(b[i].b_array,b[i].num);
	}
}

//收集桶元素
void collectelements(double array[],headnode b[])
{
	int i,j;
	int k = 0;
	for(i = 0;i < 10; i++)
	{
		for(j =0;j < b[i].num;j++)
		{
			array[k] = b[i].b_array[j];
			k++;
		}
	}
}

//清零桶
void zerobucket(headnode b[])
{
	int i,j;
	for(i = 0;i < 10;i++)
	{
		for(j = 0;j < b[i].num;j++)
		{
			b[i].b_array[j] = 0;
		}
		b[i].num = 0;
	}
}


//桶排序
double bucketSort(double array[],int size)
{
	clock_t start,end; 
	start = clock(); 
	init(b);
	insertelements(b,array,size);
	sortelements(b);
	collectelements(array,b);
	zerobucket(b);
	end = clock(); 
	return (double)(end - start) / CLOCKS_PER_SEC;
}



void rand_array(double *array, int length, int N_max)
{
    int i;    
    srand((unsigned)time(0));    
    for(i=0;i<length;i++)    
        array[i] =(double)(rand()%N_max)/N_max;
       
}


void randarray(double *array, int length)
{
	rand_array(array, length,10000 );
}





void printarray(double array[],int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		if(i%5==0)
		{
			printf("\n");
		}
		printf("  %f,",array[i]);
	}
	printf("\n");
}


void copyarray(double *array1,double *array2,int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		array2[i]=array1[i];
	}
}



double aveRunTime(int i,int n,int len)
{
	double sum,avetime;
	int j;
	sum = 0;
	switch(i)
	{
	case 1 :
		{
			if(len==MAXTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(thouarray1,MAXTHOUSAND);
				    sum += mergesort(thouarray1,MAXTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXTENTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(tetharray1,MAXTENTHOUSAND);
				    sum += mergesort(tetharray1,MAXTENTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXHUNDREDTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(hutharray1,MAXHUNDREDTHOUSAND);
				    sum += mergesort(hutharray1,MAXHUNDREDTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
		}
	case 2:
		{
			if(len==MAXTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(thouarray1,MAXTHOUSAND);
				    sum += insertsort(thouarray1,MAXTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXTENTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(tetharray1,MAXTENTHOUSAND);
				    sum += insertsort(tetharray1,MAXTENTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXHUNDREDTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(hutharray1,MAXHUNDREDTHOUSAND);
				    sum += insertsort(hutharray1,MAXHUNDREDTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
		}
	case 3:
		{
			if(len==MAXTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(thouarray1,MAXTHOUSAND);
				    sum += shellsort(thouarray1,MAXTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXTENTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(tetharray1,MAXTENTHOUSAND);
				    sum += shellsort(tetharray1,MAXTENTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXHUNDREDTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(hutharray1,MAXHUNDREDTHOUSAND);
				    sum += shellsort(hutharray1,MAXHUNDREDTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
		}
	case 4:
		{
			if(len==MAXTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(thouarray1,MAXTHOUSAND);
				    sum += quicksort(thouarray1,MAXTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXTENTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(tetharray1,MAXTENTHOUSAND);
				    sum += quicksort(tetharray1,MAXTENTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXHUNDREDTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(hutharray1,MAXHUNDREDTHOUSAND);
				    sum += quicksort(hutharray1,MAXHUNDREDTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
		}
	case 5:
		{
			if(len==MAXTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(thouarray1,MAXTHOUSAND);
				    sum += bubblesort(thouarray1,MAXTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXTENTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(tetharray1,MAXTENTHOUSAND);
				    sum += bubblesort(tetharray1,MAXTENTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXHUNDREDTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(hutharray1,MAXHUNDREDTHOUSAND);
				    sum += bubblesort(hutharray1,MAXHUNDREDTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
		}
	case 6:
		{
			if(len==MAXTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(thouarray1,MAXTHOUSAND);
				    sum += bucketSort(thouarray1,MAXTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXTENTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(tetharray1,MAXTENTHOUSAND);
				    sum += bucketSort(tetharray1,MAXTENTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
			if(len==MAXHUNDREDTHOUSAND)
			{
				for(j=1;j<=n;j++)
				{
					randarray(hutharray1,MAXHUNDREDTHOUSAND);
				    sum += bucketSort(hutharray1,MAXHUNDREDTHOUSAND);
				}
				avetime = sum/(double)n;
				return avetime;
			}
		}
    }
}