C++ qsort函数排序与冒泡模拟实现流程详解
本章重点：
1.能够正确的理解qsort函数各个参数的含义，并能够正确的使用qsort函数进行各类型排序。
2.重点掌握qsort函数中的参数cmpar——自定义比较函数的地址。借此进一步理解回调函数。 3.学习以冒泡排序思想模拟实现qsort函数。
一、qsort排序函数
1、函数功能特点
//头文件:#include<stdlib.h>
void qsort(void* base, size_t num, size_t size,int (*compar)(const void*, const void*));
注：因为qsort可以对任意类型数据排序，所以待排数据的起始类型可以是任意类型，C语言中可以用void*接收任意类型的地址。
2、函数参数
3、比较函数
qsort之所以可以对任意类型的数据排序正是因为传入的比较函数是相对自定义的：
对于比较函数 int compar(const void *p1,const void *p2)
（1）比较整数：
int compareMyType(const void* p1, const void* p2)
{
return *(MyType*)p1 - *(MyType*)p2;
}
1、如果compar返回值小于0（< 0），即*(MyType*)p1 < *(MyType*)p2那么p1所指向元素会被排在p2所指向元素的前面,也就是升序 。
2、如果compar返回值等于0（= 0），即*(MyType*)p1 = *(MyType*)p2那么p1所指向元素与p2所指向元素的顺序不确定。
3、如果compar返回值大于0（> 0），即*(MyType*)p1 > *(MyType*)p2那么p1所指向元素会被排在p2所指向元素的后面,也是升序。
所以为了方便理解我们可以简单这样认为：对于qsort函数如果compar函数的返回值<0(不进行置换)，>0(进行置换)，0(不进行置换)。
即：
return *(MyType*)p1 - *(MyType*)p2;——qsort升序排序
return *(MyType*)p2 - *(MyType*)p1;——qsort降序排序
对于具体qsort函数内部具体是怎么进行置换或排序的我们不必关心。（内部实现为快排思想）
（2）比较字符串：
int compareMyType(const void* p1, const void* p2)
{
return strcmp((MyType *) p1, (MyType *) p2);
}
同理：
return strcmp((MyType*)p1,(MyType*)p2);——qsort升序排序
return strcmp((MyType*)p2,(MyType*)p1);——qsort降序排序
（3）比较结构体
与上述思想类似，比较结构体时需要具体情况具体分析。
4、测试qsort排序
（1）测试qsort函数排序整形
#include<stdio.h>
#include<stdlib.h>
//输出函数
void print(int arr[], int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
}
//比较函数
int compar(const void* e1, const void* e2)
{
return *((int*)e1) - *((int*)e2);//升序
//return *((int*)e2) - *((int*)e1);//降序
}
int main()
{
int arr[] = { 3,5,2,6,8,1,9,0,4,7 };
int sz = sizeof(arr) / sizeof(arr[0]);
//arr-数据起始地址
//sz-数据元素个数
//sizeof(arr[0])-数据元素的大小
//compar-比较函数指针
qsort(arr, sz, sizeof(arr[0]), compar);
print(arr, sz);
return 0;
}
（2）测试qsort函数排序结构体
?按年龄排序
#include<stdio.h>
#include<stdlib.h>
//结构体
struct stu
{
char name[20];
int age;
};
//(1)按年龄排序
int compar_struct_age(const void* e1, const void* e2)
{
return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
int main()
{
struct stu s[] = { {"zhangsan",20},{"lisi",55},{"wangwu",40} };
int sz = sizeof(s) / sizeof(s[0]);
qsort(s, sz, sizeof(s[0]), compar_struct_age);
return 0;
}
?按名字排序
#include<stdio.h>
#include<stdlib.h>
//结构体
struct stu
{
char name[20];
int age;
};
//(2)按名字排序
int compar_struct_name(const void* e1, const void* e2)
{
//使用strcmp比较字符串
return strcmp(((struct stu*)e1)->name,((struct stu*)e2)->name);
}
int main()
{
struct stu s[] = { {"zhangsan",20},{"lisi",55},{"wangwu",40} };
int sz = sizeof(s) / sizeof(s[0]);
qsort(s, sz, sizeof(s[0]), compar_struct_name);
return 0;
}
二、冒泡模拟qusort函数实现
1、实现思路
理解了库函数qsort()的使用后，下面我们来用冒泡排序的思想实现一下qsort函数，首先我们先回忆一下冒泡排序：
void bubble_sort(int arr[], int sz)
{
int i = 0;
for (i = 0; i < sz - 1; i++)//冒泡排序趟数
{
int j = 0;
for (j = 0; j < sz - i - 1; j++)//每趟冒泡排序
{
//判断和交换
if (arr[j] > arr[j + 1])//升序
//if (arr[j] < arr[j + 1])降序
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
通过冒泡排序的参数部分我们就可以看出void bubble_sort(int arr[], int sz)冒泡排序仅支持单一类型的数据排序。想要用冒泡排序模拟实现qsort函数排任意类型数据，我们可以仿照qsort函数参数对冒泡排序进行改进：
void bubble_sort(void* base, int sz, int width, int (*cmp)(const void*e1, const void*e2))下面我们只需要将冒泡排序中的判断和交换部分以qsort思想实现即可。
2、模拟实现
（1）判断部分
判断部分我们需要使用传入的比较函数指针，利用回调函数的机制进行判断，同时仿照qsort函数内部交换思想即：比较函数cmp返回值大于零（>0）进行交换：
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{
//交换
}
注释：已知base的类型为void*，这里将void*类型转换为char*类型是一步非常巧妙的过程，因为转换之后我们只需分别加上j*width 和（j+1）*width即可找到相邻数据的起始地址，之后在利用回调函数的机制，调用外部定义的cmp比较函数，此时cmp实参为（char*)base+ j * width, (char*)base + (j + 1) * width分别为两相邻数据的起始位置地址，我们已知cmp函数的形参类型为void*，将得到的起始数据位置的指针转换为相应类型的指针再进行比较，即可得到返回值。
（2）交换部分
交换部分我们可以独立出一个交换函数-swap()
void swap(char* buf1, char* buf2,int width)
{
int i = 0;
for (i = 0; i < width;i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
判断交换部分
--------------------------------------------------------------------------
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{
//交换
swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
}
--------------------------------------------------------------------------注释：对于swap函数传入实参，为两相邻数据的起始地址 与
待排数据元素的大小。我们回到qsort函数的定义：qsort函数是对数组元素进行排序。数组的特点即是，连续存放的相同类型数据。对于相同类型的连续数据也就意味着每个数据的大小是相同的，即每个元素占用的字节大小相同。所以根据这样一个特点，我们就可以通过交换相邻数据的每个字节，以达到交换相邻数据的目的。这样我们就有了遍历元素字节排序的思想：for (i = 0; i < width;i++)
（3）完整代码与测试
//以冒泡模拟实现qsort
#include<stdio.h>
#include<stdlib.h>
//交换函数
void swap(char* buf1, char* buf2,int width)
{
int i = 0;
for (i = 0; i < width;i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
//冒泡实现
void bubble_qsort_sort(void* base, int sz, int width, int (*cmp)(const void*e1, const void*e2))
{
int i = 0;
for (i = 0; i < sz - 1; i++)//趟数
{
int j = 0;
for (j = 0; j < sz - i - 1; j++)//每趟
{
//判断
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{
//交换
swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
}
}
}
}这样我们就完全实现了用冒泡思想模拟实现qsort函数，并且使用规则相同，下面我们可以测试一下：
测试整数
//打印函数
void print(int arr[], int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
}
//比较函数
int compar(const void* e1, const void* e2)
{
return *((int*)e1) - *((int*)e2);
}
int main()
{
int arr[] = { 3,5,2,6,8,1,9,0,4,7 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_qsort_sort(arr, sz, sizeof(arr[0]), compar);
print(arr, sz);
return 0;
}
同样测试结构体也与库函数qsort结果相同，这里就不在过多测试。
总结
以上就是对qsort函数的理解、应用以及模拟实现。相信通过本章对qsort函数的解剖，你已经对qsort函数有了更深的理解。
到此这篇关于c++ qsort函数排序与冒泡模拟实现流程详解的文章就介绍到这了,更多相关C++ qsort函数排序内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！
相关文章