用冒泡排序的思想模拟实现Qsort

简介: 用冒泡排序的思想模拟实现Qsort

什么是冒泡排序?

假设这里有一个一维数组

int arr1[10]={0,1,2,3,4,5,6,7,8,9};

我们要对他实现降序排列,

arr1[0]与arr[1]进行比较,如果arr1[0]<arr1[1],那么二者交换位置,即arr1[0]=1,arr1[1]=0.否则不交换位置,继续和下一个元素比较.直到它和最后一个元素比较完.
那么整个冒泡排序一共要经历几次呢?
arr1有10个元素,0要和1 2 3 4 5 6 7 8 9比,1要和2 3 4 5 6 7 8 9比,2要和3 4 5 6 7 8 9比...到8 时,它只用和9比,到9时,就不用比较了,因为9已经和所有元素比较过了。因此比较的次数是元素个数-1.
那么元素内要比较几次呢?
根据上述分析,我们可以知道,每到下一个元素时,比较的次数就-1.

以上就是冒泡排序的基本思想了。

那么使用冒泡排序的qsort到底是如何实现不同类型数据的排序的呢?

在qsort(升序版本)原本的定义中,它会获取数组内两个元素e1、e2的地址,并比较它们的大小,倘若e1-e2>0,那么就会交换e1,e2的值.

这是qsort的参数

 
模仿qsort创建自己的函数
void my_qsort(void* base, size_t sz, size_t width, int(*cmp)(const void* e1, const void* e2))
void* base是用来接受被比较数组的地址的
size_t sz是接受数组元素个数的
int(*cmp)(const void* e1,const void* e2)是用来接受函数指针的
接着是各函数的构建
void swap(char* e1, char* e2,int width)
{
    int i = 0;
    for (i = 0; i < width; i++)//一个字节一个字节的转换,具体取决于width的大小
    {
        char tmp = 0;
        tmp = *e2;
        *e2 = *e1;
        *e1 = tmp;
        e1++;
        e2++;
    }
}
int cmp_int(const void* e1, const void* e2)//这实际上是一个回调函数,my_qsort函数通过调用这个函数,得到一个返回值,再通过这个返回值进行判断是否交换数值
{
    return (*(int*)e1) - (*(int*)e2);
}
int cmp_by_name(const void*e1,const void*e2)
{
    return strcmp((struct stu*)e1,(struct stu*)e2);
    
}
int cmp_by_age(const void* e1, const void* e2)
{
    return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
void my_qsort(void* base, size_t sz, size_t width, int(*cmp)(const void* e1, const void* e2))
{
int i=0;
int j=0;
for(i=0;i<sz-1;i++)
{
 for(j=0;j<sz-i-1;j++)
{
   if(cmp((char*)base+j*width,(char*)base+(j+1)*width>0))
        //为什么要将转(char*)以及j和width的用处
        //因为我们无法确认传参进来的指针的类型,因此也就无法确定指针+1的步幅
        //通过width,我们可以确认指针+1的步幅,通过j与j+1,可以得出前后相邻的两地址
            {
               swap((char*)base+j*width,(char*)base+(j+1)*width);
            }
}
}
 
 
 
}
int main()
创建几个不同类型的数组,以便待会测试
{
int arr[10]={5,1,2,6,7,3,8,9,10}
struct stu
{
char name[20];
int age;
}
sturct stu s[3]={{"zhangsan",18},{"lisi",19},{"wangmazi",24}};
    int sz = sizeof(s) / sizeof(s[0]);
    my_qsort(s, sz, sizeof(s[0]), cmp_by_name);//测试不同类型的数组只需传递对应函数的地址即可
}


目录
打赏
0
0
0
0
1
分享
相关文章
模拟实现qsort函数:冒泡排序详解
模拟实现qsort函数:冒泡排序详解
44 1
|
8月前
冒泡排序的快速排序——qsort函数的模拟实现
冒泡排序的快速排序——qsort函数的模拟实现
47 1
用冒泡排序模拟C语言中的内置快排函数qsort!
用冒泡排序模拟C语言中的内置快排函数qsort!
冒泡排序模拟实现qsort()函数
冒泡排序模拟实现qsort()函数
50 0
【冒泡排序】模仿qsort的功能实现一个通用的冒泡排序
【冒泡排序】模仿qsort的功能实现一个通用的冒泡排序
87 0
冒泡排序 - 【利用冒泡排序模拟实现快速排序的功能】
冒泡排序 - 【利用冒泡排序模拟实现快速排序的功能】
qsort函数详细讲解以及利用冒泡排序模拟实现qsort函数
qsort函数详细讲解以及利用冒泡排序模拟实现qsort函数
81 0
冒泡排序的原理
冒泡排序算法的原理如下: 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 3.针对所有的元素重复以上的步骤,除了最后一个。 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比比较 白话就是:比如有6个数,你需要比较5趟,这个是固定死的
255 0
【C语言】“qsort函数详解”与“使用冒泡思想模拟使用qsort”
qsort的介绍: qsort ()函数是 C 库中实现的快速排序算法,包含在 stdlib.h 头文件中 此函数需要四个参数void qsort(void* *base, size_t nitems, size_t size, int (compar)(const void * , const void)) char* base —— 指向要排序的数组首元素地址的指针 size_t nitems —— 要排序数组的元素个数 size_t size —— 数组每个元素大的小 (有非常重要的作用) int compar(const void *,const void *) —— 由使用者提供的一
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等