服务器之家

服务器之家 > 正文

关于C语言qsort函数详解

时间:2021-12-29 14:04     来源/作者:芒果再努力

C语言qsort函数详解

一.qsort函数是什么

我们可以使用 搜索库函数网址或者MSDN软件进行查找。

qsort()函数:快速排序的函数 -引用stdlib.h头文件

关于C语言qsort函数详解

参数说明:

void qsort ( 

  void* base, //要排序的目标数组
  size_t num,     //待排序的元素个数
  size_t width,    //一个元素的大小,单位是字节
  int(*cmp)(const void* e1, const void* e2)

);    

其中cmp是函数指针,cmp指向的是:排序时,用来比较两个元素的函数。需要自己编写。

返回值:

关于C语言qsort函数详解

二.使用qsort排序-以升序为例

关于void*型指针:

void*:无具体类型的指针 能够接收任意类型的地址
缺点:不能进行运算。不能+-整数,不能解引用

int a  = 0;
float f = 5.5f;
void* p1 = &a;
void* p2 = &f;
p1 = p1+1;    //err

1.整形数组排序

注意:

(1).比较函数的参数类型为void* ,我们要进行强制类型转换!且要解引用才能得到对应的值!

(2).若我们想排成降序,只需要写成e2-e1即可

void Print(int* arr, int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", *(arr + i));
}
printf("\n");
}
//比较整形
//注意类型时void* 所以要强制类型转化,还要解引用才是对应的值!!!
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
void test1()
{
int arr[] = { 9,8,7,6,7,5,4,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp_int);
Print(arr, sz);
}

2.字符数组排序

注意使用sizeof()操作符strlen()函数的区别

//注意要要强制类型转换!! 要解引用!!!  本质上是比较Ascii值
int cmp_char(const void* e1, const void* e2)
{
  return *(char*)e1 - *(char*)e2;
}
void test4()
{
char arr[] ="mango";
  //若使用sizeof计算长度:
//int sz = sizeof(arr) / sizeof(arr[0]); //6
//qsort(arr, sz-1, sizeof(arr[0]), cmp_float);
  //因为sizeof把\0也算进去了,所以计算出来的值比字符串本身长度多1
  
  int sz = strlen(arr); //5
  qsort(arr, sz, sizeof(arr[0]), cmp_char);
printf("%s\n",arr);
}

3.字符指针数组排序

先看看下面这段程序有没有问题?

int cmp_chars(const void* e1, const void* e2)
{
return strcmp((char*)e1, *(char*)e2);
}
void test2()
{
char* arr1 = "abc";
char* arr2 = "wcad";
char* arr3 = "cab";
char* p[3] = { arr1,arr2,arr3 };
int sz = sizeof(p) / sizeof(p[0]);
qsort(p, sz, sizeof(p[0]), cmp_chars);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%s\n", p[i]);
}
}


打印出来发现:结果是错误的!

关于C语言qsort函数详解

->调试后发现:e2存放的是p的地址(char**类型),e1存放的是p指向的下一个元素的地址(char**类型)

对于这种写法,传进去的是p的地址,strcmp()会将p地址对应的内容转化成字符串,也就是将p中arr1,arr2,arr3的地址转化成字符串

实际上应该传p地址空间中arr1,arr2的地址,这样strcmp()才能找到arr1和arr2对应的字符串,因此得先把e1,e2转化成char**,这样解引用以后才是一个char*的地址

原因:把p传给qsort,p是数组名->首元素地址,元素类型为char*>,所以p的类型为:char**类型。 所以e1 和e2也要强制类型转化为char**,解引用e1,e2才是对应字符串的地址!

关于C语言qsort函数详解

正解:

int cmp_chars(const void* e1, const void* e2)
{
return strcmp(*(char**)e1, *(char**)e2);
}
void test2()
{
char* arr1 = "abc";
char* arr2 = "wcad";
char* arr3 = "cab";
char* p[3] = { arr1,arr2,arr3 };
int sz = sizeof(p) / sizeof(p[0]);
qsort(p, sz, sizeof(p[0]), cmp_chars);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%s\n", p[i]);
}

4.结构体数组排序

比较年龄->实际比较的是整形

比较名字->实际比较的是字符串->使用strcmp函数,不能使用 == 判断

struct Stu
{
int age;
char name[20];
};
//比较结构体中元素的年龄
int cmp_age(const void* e1, const void* e2)
{
//本质是比较整形
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
//比较名字
int cmp_name(const void* e1, const void* e2)
{
//本质是字符串比较->使用strcmp函数
return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}
void test2()
{
//创建结构体数组,用大括号初始化
struct Stu s[3] = { {19,"Mango"},{18,"Lemon"},{20,"Hello"} };
int sz = sizeof(s) / sizeof(s[0]);
//以年龄排
qsort(s, sz, sizeof(s[0]), cmp_age);
printf("%s %d ",s[0].name,s[0].age);
printf("%s %d ", s[1].name, s[1].age);
printf("%s %d ", s[2].name, s[2].age);
printf("\n");
//以姓名排
qsort(s, sz, sizeof(s[0]), cmp_name);
printf("%s %d ", s[0].name, s[0].age);
printf("%s %d ", s[1].name, s[1].age);
printf("%s %d ", s[2].name, s[2].age);
printf("\n");
}

5.浮点型数组排序

注意:比较函数中,返回类型是int,最后相减的值要强制类型转化为int ,但这也会造成错误,建议使用方法2.

写法1:可能会出错

// 原因: 0.2 -0.1 = 0.1 强制类型转化为int后 结果为0
//int cmp_float(const void* e1, const void* e2)
//{
// //返回类型是int  所以相减后的结果要强制类型转化
// return (int)(*(float*)e1 - *(float*)e2);
//}



写法2:对应上qsort的返回值

int cmp_float(const void* e1, const void* e2)
{
if ((*(float*)e1 - *(float*)e2) > 0.00000)
return 1;
else if ((*(float*)e1 - *(float*)e2) == 0.000000)
return 0;
else
return -1;
}
void test3()
{
float arr[5] = { 5.01f,5.01f,0.02f,0.01f,5.001f };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp_float);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%f ", arr[i]);
}
}

三.使用冒泡排序思想模拟实现qsort函数

1.什么是冒泡排序

关于C语言qsort函数详解

主要思想:相邻的两个元素进行比较

关于C语言qsort函数详解

对于冒泡排序: n个元素 共进行n-1趟冒泡排序。一趟可以使一个元素在特定位置上,每趟排序可以少比较一个元素

但是冒泡排序只能排序整形

2.冒泡排序代码

void BubbleSort(int* arr, int sz)
{
int i = 0;
int j = 0;
//共进行sz-1趟
for (i = 0; i < sz-1; i++)
{
int flag = 1;//每一趟进来都假设有序
      // 每一趟
for (j = 0; j < sz - 1 - i; j++)
{
 if (arr[j] > arr[j + 1])
 {
  int tmp = arr[j];
  arr[j] = arr[j + 1];
  arr[j + 1] = tmp;
  flag = 0;
 }
}
      //若falg还是1,说明没有交换->已经有序了break退出
if (flag == 1)
{
 break;
}
}
}
int main()
{
int arr[10] = { 2,3,6,7,9,0,0,3,2,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
BubbleSort(arr, sz);
return 0;
}

3. 使用冒泡排序思想模拟实现qsort函数

qsort库函数使用的是什么参数,我们设计的函数就使用什么参数!

关于C语言qsort函数详解

(1)为何将base强制类型转化为char*型指针:

原因:char* 指针+1跳过一个字节,+width:跳过width个字节,指向下一个元素。转化为其他类型不合适

(2)交换函数:还要把宽度(每个元素所占字节数)传过去

因为交换的时候是传地址,所以要知道元素的宽度,一个字节一个字节的交换 ,这样也证明了使用char*指针的好处!

(3)char*)base + j * width, (char*)base + (j + 1) * width,

当j = 0时:比较的是第一个元素和第二个元素
j = 1时,比较的是第二个元素和第三个元素
.... 很妙的写法

//交换 --一个字节一个字节的交换,共交换width次
void Swap(char* buf1, char* buf2, size_t width)
{
size_t i = 0;
for (i = 0; i < width; i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
void my_BubbleSort(void* base, size_t num,size_t width, int(*cmp)(const void* e1, const void* e2))
{
//冒泡排序
//若要排序n个元素,只需要进行n-1趟
//每一趟可以少比较一个元素,每一趟可以使一个元素在确定的位置上
//num:要排序元素的个数 类型是size_t 
  //num是无符号数 防止产生警告 所以i和j也定义为size_t
  // size_t == unsigned int 
size_t i = 0;
size_t j = 0;

//共进行num-1趟
for (i = 0; i < num; i++)
{
//每一趟
for (j = 0; j < num - 1 - i; j++)
{
 //比较
 //传地址   
 //相邻两个元素比较   width:宽度,每个元素所占字节
 //排成升序
 if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
 {
  //交换两数
  Swap( (char*)base + j * width, (char*)base + (j + 1) * width, width );
 }
}
}
}

当然 ,交换也可以使用库函数memcpy

关于C语言qsort函数详解

dest:目标空间

src:要拷贝到目标空间的字符 -因为不作修改,所以可以用const修饰

count:字节数

char tmp [30];    //防止结构体类型之类的类型    临时空间
memcpy(tmp, (char*)base + j * size, size); 
memcpy( (char*)base + j * size,  (char*)base + (j + 1) * size, size);
memcpy( (char*)base + (j + 1) * size, tmp, size);

以上就是关于C语言qsort函数详解的详细内容,更多关于C语言qsort函数的资料请关注服务器之家其它相关文章!希望大家以后多多支持服务器之家!

原文链接:https://blog.csdn.net/chuxinchangcun/article/details/120046062

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整
蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整 2021-08-24
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
返回顶部