通用型冒泡、选择、插入、希尔、快速排序的代码实现

17
五月
2021

通用型冒泡、选择、插入、希尔、快速排序的代码实现

/*************************************************************************
  > File Name: sort.c
  > Author: xxx
  > Mail: xxx.com 
  > Created Time: 
 ************************************************************************/
#include <stdio.h>
#include <string.h>
#include <stddef.h>

#define N  5 

void print_arr(float * arr,size_t size);
int cmpfun(const void * a,const void * b);
void swap(void * para1,void * para2,size_t size);

void bubble_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*));
void select_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*));
void insert_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*));
void shell_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*));

void quick_sort_recursive(void *arr,int first,int end,size_t size,int (*compar)(const void*, const void*));
void quick_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*));


float values[] = {22.7,12.5,51.8,51.3,2,90.9,33,67};    

//print_arr
void print_arr(float * arr,size_t size)
{
	int i;                                                                                                                                              
	for( i = 0; i < size; i++)                                                                                                                             
	{                                                                                                                                                   
		printf("%-4.1f ",arr[i]);                                                                                                                        
	}                                                                                                                                                   
	printf("\n");  
}


//compare
int cmpfun(const void * a,const void * b)                                                                                                                                    
{                                                                                                                                                                            
	const float *aa = a;                                                                                                                                                       
	const float *bb = b;                                                                                                                                                       

	return (*aa > *bb) - (*aa < *bb);                                                                                                                                        
}


//swap memory
void swap(void * para1,void * para2,size_t size)
{
	char buff[size];
	char *a = para1;
	char *b = para2;

	memcpy(buff,a,size);
	memcpy(a,b,size);
	memcpy(b,buff,size);

}

//bubble_sort
void bubble_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*))                                                                              
{                                                                                                                                                                            
	int i,j;                                                                                                                                                                 
	char *base1 = base;                                                                                                                                                      
	char buff[size];                                                                                                                                                         
	for(i = 0 ; i < nitems -1; i++)                                                                                                                                          
	{                                                                                                                                                                        
		for(j = 0; j <nitems - i -1;j++ )                                                                                                                                    
		{                                                                                                                                                                    
			if((*compar)((base1 + (j*size)),(base1 + (j + 1)*size)) == 1)                                                                                                    
			{                                                                                                                                                                

				memcpy(buff,base1 + (j*size),size);                                                                                                                          
				memcpy(base1 + (j*size),base1 + (j + 1)*size,size);                                                                                                          
				memcpy(base1 + (j + 1)*size,buff,size);                                                                                                                      
			}                                                                                                                                                                

		}

	}                                                                                                                                   
}

//select_sort
void select_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*))
{
	int i,j,min;
	//printf("%p %p\n",base + 1,base + 2);
	for(i = 0; i < nitems - 1;i++)
	{
		min = i;
		for(j = i + 1; j < nitems;j++ )
		{
			//printf("%d \n",(*cmpfun)((base1 + (min*size)),(base1 + (j*size))));
			if((*compar)(base + min*size,base + j*size) == 1)
			{
				min = j;
			}
		}

		//printf("%d %d\n",min,i);
		if( min != i)
		{
			swap(base + min*size,base + i*size,size);
		}
	}
}

//insert_sort
void insert_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*))
{
	int i,j;
	char buff[size];

	for(i = 1; i < nitems;i++)
	{
		if((*compar)(base + (i - 1)*size,base + i*size) == 1 )
		{
			memcpy(buff,base + i * size,size);

			for(j = i -1; (j >= 0) && (*cmpfun)(base + j * size,buff) == 1;j--)
			{
				//	printf("%d\n",j);
				memcpy(base + (j + 1)*size,base + j*size,size);
			}
			//printf("--------\n");
			memcpy(base + (j + 1)*size,buff,size);

		}

	}
}

//shell_sort
void shell_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*))
{
	int i,j,inc;
	char buff[size];
	for(inc = nitems >> 1; inc >= 1;inc >>= 1)
	{
		for(i = inc; i < nitems; i ++)
		{
			if((*compar)(base + (i - inc)*size,base + i*size) == 1 )
			{
				memcpy(buff,base + i * size,size);  
				for(j = i - inc; (j >= 0) && compar(base + j * size,buff) == 1;j -= inc)
				{
					memcpy(base + (j + inc)*size,base + j*size,size);   

				}
				memcpy(base + (j + inc)*size,buff,size);   
			}

		}
		printf("increment:%d\n",inc);
		print_arr(values,N);


	}

}

//quick_sort_recursive
void quick_sort_recursive(void *arr,int first,int end,size_t size,int (*compar)(const void*, const void*))
{
	int i = first;
	int j = end;
	int pivot;

	while( i < j) 
	{
		while( i < j && ((*cmpfun)(arr + j*size,arr + i*size) >= 0))
			j--;
		if( i < j)
		{
			swap(arr + i*size,arr + j*size,size);
			i++;
		}

		while( i < j && ((*cmpfun)(arr + j*size,arr + i*size) >= 0))
			i++;
		if(i < j)
		{
			swap(arr + i*size,arr + j*size,size);
			j--;
		}

	}

	pivot = i;
	if(first < end)
	{
		quick_sort_recursive(arr,first,pivot-1,size,compar);
		quick_sort_recursive(arr,pivot+1,end,size,compar);
	}

}

//quick_sort
void quick_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*))
{
	
	quick_sort_recursive(base,0,nitems-1,size,compar);
}
//main
int main(int argc, const char *argv[])
{
	printf("排序前:\n");
	print_arr(values,N);
	printf("------------------------------------------\n");
	quick_sort(values,N,sizeof(float),cmpfun);  
	//shell_sort(values,N,sizeof(float),cmpfun);
	//insert_sort(values,N,sizeof(float),cmpfun);
	//bubble_sort(values,N,sizeof(float),cmpfun);
	//select_sort(values,N,sizeof(float),cmpfun);
	printf("排序后:\n");
	print_arr(values,N);
}


TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员