我们在学习怎样模拟实现qsort函数之前,我们需要知道在库函数中qsort是怎么实现的。
使用库函数来使用qsort
先看看在库函数中qsort是怎样声名的:
void qsort( void* base, //这里是我们要排序的目标数组 size_t num, //要排序的数组中元素的个数 size_t width, //每个元素的宽度,也就是每个元素所占的字节数 int (*cmp)(const void* e1,const coid * e2)) //这个比较函数是需要我们使用者自己来实现的。
然后我们写一段代码来使用这个qsort库函数
#include<stdio.h> #include<stdlib.h> int cmp (const void* e1,const void *e2) { //以这种形式写,那么数组将会以升序的形式排序,如果你想以降序的形式排列就可以改成 return *(int*)e2-*(int*)e2 return *(int*)e1-*(int*)e2; } int main() { int arr[] = {9,8,7,6,5,4,3,2,1,0,}; int len = sizeof(arr)/sizeof(arr[0]); qsort(arr,len,sizeof(arr[0]),cmp); for(int i = 0; i<10; i++) //将数组打印出来观察 { printf("%d ",arr[i]); } return 0; }
模拟实现qsort
知道了怎样直接使用库函数qsort之后,我们就可以仿照库函数来自己模拟实现。代码如下:
#include<stdio.h> #include<stdlib.h> void swap(char* e1,char* e2,size_t width) { for(int i = 0; i<width; i++) { char tmp = *e1; *e1 = *e2; *e2 = tmp; e1++; e2++; } } int cmp(const void* e1,const void* e2) { return *(int*)e1-*(int*)e2; //这里强制转换类型需要根据你的数组内容来改变 } void my_qsort(void* base,size_t len,size_t width,int (*cmp)(const void* e1,const void *e2)) { for(int i = 0; i<len; i++) { for(int j = 0; j<len-1-i; j++) { //我这里还是以升序为例,如果前面一个元素大于后面一个元素就交换, 如果你想以降序排列的话就将>换成< if(cmp((char*)base+j*width,(char*)base+(j+1)*width)>0) { swap((char*)base+j*width,(char*)base+(j+1)*width) ,size_t width); } } } } int main() { int arr[] = {9,8,7,6,5,4,3,2,1,0}; int len = sizeof(arr)/sizeof(arr[0]); my_qsort(arr,len,sizeof(arr[0]),cmp); return 0; }
这里我们还可以使代码更加优化,那就是定义一个flag变量,将他赋值为一,如果有交换就将flag改为0,如果循环结束后flag还为1,那么就说明该躺排序没有元素进行交换,都没有进行交换的话,就说明此时数组中的元素已经达到了我们的目的,我们就可以直接结束函数,大大的提高了代码的运行效率。
整体代码展示
#include<stdio.h> #include<stdlib.h> void swap(char* e1,char* e2,size_t width) { for(int i = 0; i<width; i++) { char tmp = *e1; *e1 = *e2; *e2 = tmp; e1++; e2++; } } int cmp(const void* e1,const void* e2) { return *(int*)e1-*(int*)e2; //这里强制转换类型需要根据你的数组内容来改变 } void my_qsort(void* base,size_t len,size_t width,int (*cmp)(const void* e1,const void *e2)) { for(int i = 0; i<len; i++) { int flag = 1; for(int j = 0; j<len-1-i; j++) { //我这里还是以升序为例,如果前面一个元素大于后面一个元素就交换, 如果你想以降序排列的话就将>换成< if(cmp((char*)base+j*width,(char*)base+(j+1)*width)>0) { flag = 0; swap((char*)base+j*width,(char*)base+(j+1)*width) ,size_t width); } } if(1 == flag) return; } } int main() { int arr[] = {9,8,7,6,5,4,3,2,1,0}; int len = sizeof(arr)/sizeof(arr[0]); my_qsort(arr,len,sizeof(arr[0]),cmp); return 0; }
这就是模拟实现qsort函数的全部内容了,感谢大家的观看。