冒泡函数模拟qsort函数

有关于qsort函数和冒泡函数可以跳转CSDNhttps://mp.csdn.net/mp_blog/creation/editor/139388503

qsort的底层逻辑是这样的

我们冒泡排序模仿qsort必须要针对的是所以说我们要模仿qsort的底层逻辑来写

我们以整型数组来举例

#include <stdio.h>
int cmp_int(const void*p1,const void *p2)
{
	return *(int*)p1-*(int*)p2;
}
void Swap(char* buf1,char*buf2,size_t width)
{
	char tmp=0;
	for(int i=0;i<width;i++){
		tmp=*buf1;
		*buf1=*buf2;
		*buf2=tmp;
		buf1++;
		buf2++;
	}
}
void print_arr(int arr[],size_t sz)
{
	for(int i=0;i<sz;i++){
		printf("%d ",arr[i]);
	}
}
void bubble_sort(void *base,size_t sz,size_t width,int (*cmp_int)(const void*,const void*))
{
	for(int i=0;i<sz-1;i++){
		for(int j=0;j<sz-1-i;j++){
			if(cmp_int((char*)base+j*width,(char*)base+(j+1)*width)>0){
			  Swap((char*)base+j*width,(char*)base+(j+1)*width,width);
			}
		}
	}
}
void test1()
{
	int arr[]={3,2,4,5,7,8,9,6,1,0};
	size_t sz=sizeof(arr)/sizeof(arr[0]);
	bubble_sort(arr,sz,sizeof(arr[0]),cmp_int);
	print_arr(arr,sz);
}
int main()
{
test1();
	return 0;
}

我们逐语句来分析

void test1()
{
	int arr[]={3,2,4,5,7,8,9,6,1,0};
	size_t sz=sizeof(arr)/sizeof(arr[0]);
	bubble_sort(arr,sz,sizeof(arr[0]),cmp_int);
	print_arr(arr,sz);
}

我们创立一个整型数组，然后创立一个冒泡排序函数和打印函数对它们进行实现

bubble_sort(arr,sz,sizeof(arr[0]),cmp_int);

void qsort (void* base, size_t num, size_t size,
            int (*compar)(const void*,const void*));

既然是模仿我们就根据qsort的参数来一步步对应上去，这样方便适应于所有函数

base是指向待排序数组的第一个元素的指针

num是base指向数组中的元素个数

size是base指向的数组中一个元素的大小，单位是字节

第四个是一个函数指向比较两个元素的函数的指针。
该函数被重复调用排序比较两个元素。

所以我们分别将首元素地址，元素个数，元素大小，比较函数传上去

void bubble_sort(void *base,size_t sz,size_t width,int (*cmp_int)(const void*,const void*))
{
	for(int i=0;i<sz-1;i++){
		for(int j=0;j<sz-1-i;j++){
			if(cmp_int((char*)base+j*width,(char*)base+(j+1)*width)>0){
			  Swap((char*)base+j*width,(char*)base+(j+1)*width,width);
			}
		}
	}
}

因为要适用于所有类型，所以我们的参数统统用void*和无符号整型size_t来接收

然后因为要以冒泡函数为基础，所以我们的底层交换逻辑不用变

int cmp_int(const void*p1,const void *p2)
{
	return *(int*)p1-*(int*)p2;
}

这个代码在面对字符串的时候需要用到strcmp函数，建议浏览过我上一篇文章后进行相应的更改。

如果返回数大于0，我们就进行交换，但是我们要适用于所有函数所以我们要单独剥离一个函数出来

  Swap((char*)base+j*width,(char*)base+(j+1)*width,width);

这里为什么用到的是char*呢因为char字符在编译器中属于一个字节，属于是最小的字节，我们方便得到，比如8个字节或者4个字节大小的元素，我们通过width字节大小的操作就能不断的得到下面几个元素

比如说我们要交换8和9的地址就是把char*arr[0]+0*4，和char*arr[1]+0*4传过去，我们对每个字节进行交换就能得到新的元素，再比如说char*arr[0]+1*4，和char*arr[1]+1*4就得到了下标为1和2的元素进行交换，至于指针用char*指向的只是首元素的第一个字节地址，对元素本身地址并没有太大的影响，所以说我们传过去以后仍然可以对每个字节进行交换

void Swap(char* buf1,char*buf2,size_t width)
{
	char tmp=0;
	for(int i=0;i<width;i++){
		tmp=*buf1;
		*buf1=*buf2;
		*buf2=tmp;
		buf1++;
		buf2++;
	}
}

因为我们是通用的，我们在编写代码的时候就需要对所有的字节进行交换，而对字节里的实际内容交换又需要用到指针。

每交换完一个字节我们就进行交换下一个字节

最终就能实现冒泡排序的类比