一、qsort函数介绍
库函数查询网站(建议使用旧版本查询)
头文件:<stdlib.h>
功能介绍:
使用函数确定顺序，对指向的数组的元素进行排序，每个元素的长度以字节为单位。
此函数使用的排序算法通过调用指定的函数(要自己定义元素比较方式函数传给qsort)并将指向元素的指针作为参数来比较元素.
该函数不返回任何值，而是通过按定义重新排序数组元素来修改指向的数组的内容。
参数介绍:
| 参数1(void* base) | 要排序的数组首地址 |
| 参数2(size_t num) | 数组中的元素个数。 |
| 参数3(size_t size) | 数组中每个元素的大小（以字节为单位）。 |
| 参数4 ( int (compar)(const void,const void*)) | 指向数组中元素比较方式的函数指针 |
二、qsort函数的应用
1.整形数组排序
#include <stdio.h> #include <stdlib.h> //注意,由于qsort排序时,并不知道要排序的元素是何种类型, //所以自定义比较函数的参数都暂时是void*要强制类型转化为对应类型才可以使用. int int_sort(const void* e1, const void* e2)//自定义整形元素比较方式函数 { return *(int*)e1 - *(int*)e2; } int main() { int arr1[10] = { 4,6,1,7,8,2,9,10,3,5 }; int sz1 = sizeof(arr1) / sizeof(arr1[0]);//计算元素个数 qsort(arr1, sz1, sizeof(arr1[0]), int_sort);//整形排序 int i = 0; for (i = 0; i < sz1; i++)//整形打印 { printf("%d ", arr1[i]); } return 0; }
运行结果:
1 2 3 4 5 6 7 8 9 10
2.浮点型数组排序
//浮点型数组排序 #include <stdio.h> #include <stdlib.h> int double_sort(const void* e1, const void* e2)//浮点型比较 { //注意要强制转化为相对于的类型,然后解引用比较. int ret = 0; if ((*(double*)e1) - (*(double*)e2) > 0) { ret = 1;//前面的数比后面大时返回整数 } else ret = -1;//后面数大返回负数; return ret;//两个数相等返回0; } int main() { double arr2[6] = {3.41, 9.45, 4.78, 3.67, 2.9, 7.36 }; int sz2 = sizeof(arr2) / sizeof(arr2[0]);//计算数组元素个数 qsort(arr2, sz2, sizeof(arr2[0]), double_sort); int i = 0; for (i = 0; i < sz2; i++)//浮点型数组打印 { printf("%5.2lf ", arr2[i]); } return 0; }
运行结果:
2.90 3.41 3.67 4.78 7.36 9.45
3.字符型排序
//字符型数组排序 #include <stdio.h> #include <stdlib.h> int char_sort(const void* e1, const void* e2)//字符型比较 { return (*(char*)e1) - (*(char*)e2); } int main() { char arr3[10] = { 'd','g','b','a','e','i','h','c','j','f' }; int sz3 = sizeof(arr3) / sizeof(arr3[0]);//计算元素个数 qsort(arr3, sz3, sizeof(arr3[0]), char_sort); int i = 0; for (i = 0; i < sz3; i++)//字符型打印 { printf("%c ", arr3[i]); } }
运行结果:
a b c d e f g h i j
4.结构体数组排序
strcmp函数用于比较字符串的,它的比较方式是比较字符的ASCII码值,并不是长度,后续在库函数模拟篇会讲到.
//结构体排序 #include <stdio.h> #include <stdlib.h> struct student//创建结构体类型 { char name[15]; char sex[3]; int age; float stature; }; typedef struct student sc;//对结构体类型重命名 int sort_age(const void* e1, const void* e2)//按年龄排序 { return (((sc*)e1)->age - ((sc*)e2)->age); } int sort_name(const void* e1, const void* e2)//按姓名排序 { return strcmp(((sc*)e1)->name, ((sc*)e2)->name); } int main() { sc arr4[5] = { {"chu jie niu","男",20,1.73f}, {"xiao wang","男",19,1.68f}, {"qing niao","女",21,1.59f}, {"wao shu li","男",16,1.83f}, {"peng hu wan","男",15,1.81f} }; int sz4 = sizeof(arr4) / sizeof(arr4[0]); //qsort(arr4, sz4, sizeof(arr4[0]), sort_age); qsort(arr4, sz4, sizeof(arr4[0]), sort_name); int i = 0; printf("姓名 性别 年龄 身高\n"); for (i = 0; i < sz4; i++) { printf("%-12s %-5s %-5d %-5.2fm\n", arr4[i].name, arr4[i].sex, arr4[i].age, arr4[i].stature); } return 0; }
运行结果:
姓名 性别 年龄 身高 chu jie niu 男 20 1.73 m peng hu wan 男 15 1.81 m qing niao 女 21 1.59 m wao shu li 男 16 1.83 m xiao wang 男 19 1.68 m
三、qsort模拟实现(采用冒泡排序模拟)
复习一下冒泡排序吧!
void bubble_sort(int* arr, int sz)//冒泡排序 { int i = 0, j = 0; for (i = 0; i < sz - 1; i++) { 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; } } } } int main() { int arr[10] = { 4,7,1,8,2,3,9,10,5,6 }; int sz = sizeof(arr) / sizeof(arr[0]);//计算元素个数 bubble_sort(arr, sz); for (int i = 0; i < sz; i++)//数组打印 { printf("%d ",arr[i]); } return 0; }
qsort模拟实现(采用冒泡排序模拟实现)
第一步:冒泡函数的参数
首先,要修改的是冒泡排序函数的参数.
void bubble_sort(void * arr, size_t num, size_t width, int (cmp)(const void, const void*))
这四个参数的含义上面介绍qsort参数时有介绍.
需要注意的是,qsort函数事先并不知道要传过来的数组是何种类型,所以先用void*接收.
补充知识:
void*可以接收任何类型的变量,但是并不能直接使用,要强制类型转化为对应类型使用.
第二步:比较元素的的方法
if (arr[j] > arr[j + 1])
语句中的arr[j]和arr[j+1]有两点需要注意.
由于事先不知道类型
1.要先将arr强制类型转化为char*,因为一个字节是类型的最小单位,这时width就发挥作用了.
arr[j]转化为 (char*)arr + j * width
arr[j+1]转化为 (char*)arr + (j + 1) * width
2.元素的比较方式不再是单一的相减就可以,这里就用到了自定义函数,元素的比较方式函数.
if (cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0)
第三步:交换函数
对于这样只能实现整形的交换方式,肯定是不行的.
int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp;
修改为:用char*类型修改交换
swap(char* e1, char* e2, size_t sz)//交换函数 { //由于qsort函数事先不知道要比较的元素是何种类型,所以用最小单位一个字节来交换. //sz代表元素的所占字节大小 int i = 0; char p = 0; for (i = 0; i < sz; i++) { p = *(e1 + i); *(e1 + i) = *(e2 + i); *(e2 + i) = p; } }
最后展示全部代码:
#include <stdio.h> #include <stdlib.h> struct student//创建结构体类型 { char name[15]; char sex[3]; int age; float stature; }; typedef struct student sc;//对结构体类型重命名 int sort_age(const void* e1, const void* e2)//按年龄排序 { return (((sc*)e1)->age - ((sc*)e2)->age); } int sort_name(const void* e1, const void* e2)//按姓名排序 { return strcmp(((sc*)e1)->name, ((sc*)e2)->name); } int int_sort(const void* e1, const void* e2)//整形比较 { return *(int*)e1 - *(int*)e2; } swap(char* e1, char* e2, size_t sz)//交换函数 { //由于qsort函数事先不知道要比较的元素是何种类型,所以用最小单位一个字节来交换. //sz代表元素的所占字节大小 int i = 0; char p = 0; for (i = 0; i < sz; i++) { p = *(e1 + i); *(e1 + i) = *(e2 + i); *(e2 + i) = p; } } //最后一个参数是函数指针,指向两个元素的比较方法这个函数 void bubble_sort(void * arr, size_t num, size_t width, int (*cmp)(const void*, const void*)) { int i = 0, j = 0; for (i = 0; i < num-1; i++) { for (j = 0; j < num - 1 - i; j++) { if (cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0) { swap((char*)arr + j * width , (char*)arr + (j + 1) * width,width); } } } } int main() { int arr[10] = { 4,7,1,8,2,3,9,10,5,6 }; int sz = sizeof(arr) / sizeof(arr[0]);//计算元素个数 bubble_sort(arr,sz,sizeof(arr[0]),int_sort); for (int i = 0; i < sz; i++)//数组打印 { printf("%d ",arr[i]); } printf("\n"); sc arr4[5] = { {"chu jie niu","男",20,1.73f}, {"xiao wang","男",19,1.68f}, {"qing niao","女",21,1.59f}, {"wao shu li","男",16,1.83f}, {"peng hu wan","男",15,1.81f} }; int sz4 = sizeof(arr4) / sizeof(arr4[0]); qsort(arr4, sz4, sizeof(arr4[0]), sort_age); //qsort(arr4, sz4, sizeof(arr4[0]), sort_name); int i = 0; printf("姓名 性别 年龄 身高\n"); for (i = 0; i < sz4; i++) { printf("%-12s %-5s %-5d %-5.2fm\n", arr4[i].name, arr4[i].sex, arr4[i].age, arr4[i].stature); } return 0; }
运行结果:
1 2 3 4 5 6 7 8 9 10 姓名 性别 年龄 身高 peng hu wan 男 15 1.81 m wao shu li 男 16 1.83 m xiao wang 男 19 1.68 m chu jie niu 男 20 1.73 m qing niao 女 21 1.59 m
