目录
- 前言
- 一、qsort()的介绍及使用
- 1.1 qsort()的介绍
- 1.2 qsort()的使用
- 1.2.1 使用qsort|()对整型数组按照升序排序
- 1.2.2 使用qsort()对整型数组按照降序排序
- 1.2.3 使用qsort()对结构体数组数据进行排序
- 二、利用冒泡排序模拟实现对任何数据进行排序
- 2.1 冒泡排序
- 2.2 模仿qsort()实现bubble_sort()对任何数据类型的数据排序
- 2.2.1 代码实现
- 2.2.2 测试对整型数组排序
- 2.2.3 测试对结构体数组数据排序
- 总结
前言
本篇文章介绍库函数qsort()的使用以及利用冒泡排序的思想模拟对任何类型的数据进行排序。
一、qsort()的介绍及使用
1.1 qsort()的介绍
下面是cplusplus对qsort()的叙述，详情https://cplusplus.com/reference/cstdlib/qsort/
qsort()可以对任意类型的数据进行排序。
对qsort()参数进行介绍：
void* base：指向需要被排序数组的起始位置。
size_t num：待排序的元素个数
size_t size：待排序的元素的大小（单位：字节）
int (*compar)(const void*, const void*)：函数指针，指向比较函数，可以实现自定义比较规则。
1.2 qsort()的使用
1.2.1 使用qsort|()对整型数组按照升序排序
//升序
int compare_asc(const void* e1, const void* e2)
{
return (*(int*)e1 - *(int*)e2);
}
int main()
{
int arr[] = { 40, 10, 100, 90, 20, 25 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), compare_asc);
int i = 0;
for (i = 0; i < sz; i++)
printf("%d ", arr[i]);
return 0;
}
1.2.2 使用qsort()对整型数组按照降序排序
//降序
int compare_dec(const void* e1, const void* e2)
{
return (*(int*)e2 - *(int*)e1);
}
int main()
{
int arr[] = { 40, 10, 100, 90, 20, 25 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), compare_dec);
int i = 0;
for (i = 0; i < sz; i++)
printf("%d ", arr[i]);
return 0;
}
1.2.3 使用qsort()对结构体数组数据进行排序
按照年龄升序排序：
//定义结构体
struct Stu {
char name[20];
int age;
float height;
};
//输出结构体数组数据
void print_stu(struct Stu* stu,int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%s\t%-6d\t%.2f\n", (stu + i)->name, (stu + i)->age, (stu + i)->height);
}
}
//按照年龄升序进行排序
int compare_stuByAge_asc(const void* e1, const void* e2)
{
return (((struct Stu*)e1)->age - ((struct Stu*)e2)->age);
}
int main()
{
struct Stu student[3] = { {"zhangsan", 18, 170.50f},
{"lisi", 20, 185.25f},
{"wangwu", 17, 165.55f} };
int sz = sizeof(student) / sizeof(student[0]);
printf("原顺序\n");
print_stu(student, sz);
//按照年龄升序排序
qsort(student, sz, sizeof(student[0]), compare_stuByAge_asc);
printf("按照年龄升序\n");
print_stu(student, sz);
return 0;
}
二、利用冒泡排序模拟实现对任何数据进行排序
2.1 冒泡排序
void bubble_sort(int arr[], int sz)
{
int i = 0;
int flag = 1;//假设数据有序
//排序趟数
for (i = 0; i < sz - 1; i++)
{
int j = 0;
//每趟要比较数据的个数
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;
}
}
//当进行第一趟排序时，flag未改变，说明没有进行交换，数组有序
if (1 == flag)
{
break;
}
}
}
int main()
{
int arr[] = { 40, 10, 100, 90, 20, 25 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz);
int i = 0;
for (i = 0; i < sz; i++)
printf("%d ", arr[i]);
return 0;
}
对比qsort()发现，bubble_sort()只能对整型数组数据进行排序，为了增加bubble_sort()的通用性，可以模仿qsort()的写法实现bubble_sort()对任何数据类型的排序。
2.2 模仿qsort()实现bubble_sort()对任何数据类型的数据排序
2.2.1 代码实现
//每次交换一个字节的内容
//循环交换width个字节的内容
void Swap(char* e1, char* e2, int width)
{
char tmp = 0;
int i = 0;
for(i = 0; i < width; i++)
{
tmp = *e1;
*e1 = *e2;
*e2 = tmp;
e1++;
e2++;
}
}
void bubble_sort(void* base, int sz,int width, int(*compare)(const void* e1, const void* e2))
{
int i = 0;
int flag = 1;//假设数据有序
//排序趟数
for (i = 0; i < sz - 1; i++)
{
int j = 0;
//每趟要比较数据的个数
for (j = 0; j < sz - 1 - i; j++)
{
//利用compare()回调函数, >0进行交换
if (compare((char*)base+j*width, (char*)base+(j+1)*width) > 0)
{
//交换
Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
flag = 0;
}
}
//当进行第一趟排序时，flag未改变，说明没有进行交换，数组有序
if (1 == flag)
{
break;
}
}
}
compare((char*)base+j*width, (char*)base+(j+1)*width) > 0；
返回值有三个
返回值为 =0，说明e1和e2指向的数据值相等
返回值为<0，有两种情况：
- e1指向的数据值小于e2指向的数据值
- e1指向的数据值大于e2指向的数据值
返回值为>0，有两种情况
- e1指向的数据值小于e2指向的数据值
- e1指向的数据值大于e2指向的数据值
为什么出现两种情况？
原因：因为compare()的返回值是两个值相减，但无法确定哪个是减数
升序和降序的控制
升序：当e1指向的数据值作为被减数时，即e1-e2
降序：当e2指向的数据值作为被减数时，即e2-e1。
注意：e1-e2只是作为说明，具体怎么比较，由自定义实现比较规则。(具体看例子)
为什么选择compare((char*)base+j*width, (char*)base+(j+1)width) > 0作为判断交换的条件？
因为默认把e1-e2作为升序，即从小到大排序。
如果把compare((char)base+j*width, (char*)base+(j+1)width) > 0
换成compare((char)base+j*width, (char*)base+(j+1)*width) < 0
那么默认e1-e2是降序，即从大到小排序。
(char*)base + j * width //指向要比较的第一个元素
(char*)base + (j + 1) * width //指向要比较的第二个元素
//利用(char*)base强制类型转换，分别指向被比较元素的起始位置
void Swap(char* e1, char* e2, int width);
实现的是交换每个字节的内容，width是每个元素的大小。由于是char*类型的指针，所以一次交换只能交换一个字节的内容，为了能够交换整个元素的内容，所以需要交换width次。
2.2.2 测试对整型数组排序
//对数组进行升序
int compare_int_asc(const void* e1, const void* e2)
{
return (*(int*)e1 - *(int*)e2);
}
//降序
int compare_int_dec(const void* e1, const void* e2)
{
return (*(int*)e2 - *(int*)e1);
}
int main()
{
int arr[] = { 40, 10, 100, 90, 20, 25 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz, sizeof(arr[0]),compare_int_dec);
int i = 0;
for (i = 0; i < sz; i++)
printf("%d ", arr[i]);
return 0;
}
2.2.3 测试对结构体数组数据排序
//定义结构体
struct Stu {
char name[20];
int age;
float height;
};
//输出结构体数据
void print_stu(struct Stu* stu,int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%s\t%-6d\t%.2f\n", (stu + i)->name, (stu + i)->age, (stu + i)->height);
}
}
//按照年龄升序进行排序
int compare_stuByAge_asc(const void* e1, const void* e2)
{
return (((struct Stu*)e1)->age - ((struct Stu*)e2)->age);
}
//按照名字的字母序排序
int compare_stuByName(const void* e1, const void* e2)
{
return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}
int main()
{
struct Stu student[3] = { {"zhangsan", 18, 170.50f},
{"lisi", 20, 185.25f},
{"wangwu", 17, 165.55f} };
int sz = sizeof(student) / sizeof(student[0]);
printf("原顺序\n");
print_stu(student, sz);
//按照年龄升序排序
//bubble_sort(student, sz, sizeof(student[0]), compare_stuByAge_asc);
//按照名字字母序
bubble_sort(student, sz, sizeof(student[0]), compare_stuByName);
//printf("按照年龄升序\n");
printf("按照名字字母序\n");
print_stu(student, sz);
return 0;
}
总结
本篇文章介绍了库函数qsort()的使用，以及模仿qsort()，利用冒泡排序模拟实现对任何数据类型的数据进行排序。
