门户网站系统开发,做网站的主要内容,亦庄网站开发公司,北京网站建设新鸿微信号目录
什么是qsort#xff1f;
函数原型
比较函数 compar
排序整型数组
排序结构体数组
根据成员字符排序 strcmp函数
根据成员整型排序
自定义qsort实现冒泡排序
qsort的实现原理
具体步骤
快速排序示例代码#xff1a; 什么是qsort#xff1f;
qsort是 C …目录
什么是qsort
函数原型
比较函数 compar
排序整型数组
排序结构体数组
根据成员字符排序 strcmp函数
根据成员整型排序
自定义qsort实现冒泡排序
qsort的实现原理
具体步骤
快速排序示例代码 什么是qsort
qsort是 C 语言标准库stdib.h中的一个函数用于对数组进行快速排序如下
base指向需排序的数组指针同数组首元素地址。num数组中的元素个数。size每个元素的大小以字节为单位。compar比较函数指针用于定义排序顺序。
函数原型
void qsort(void *base, size_t num, size_t size, int (*compar)(const void *, const void *)); 比较函数 compar
比较函数 compar 负责定义数组元素的排序顺序。它应该接受两个参数每个参数的类型都是 const void *并返回一个整型值。比较函数的返回值定义了元素之间的排序关系
如果返回值小于 0则第一个参数应该排在第二个参数之前。如果返回值等于 0则两个参数的相对位置不变。如果返回值大于 0则第一个参数应该排在第二个参数之后。
排序整型数组
void是无具体类型的指针可以接受任意类型的地址但是不能解引用也不能-操作因为它不知道自己有几个字节的权限
int a 10;
void *pv a; compare函数形参中因为指针类型是void不能解引用需要强制类型转换为int再解引用根据自己的数据类型来决定是int还是char还是结构体 #include stdio.h
#include stdlib.hint compare(const void* a, const void* b) {return (*(int*)a - *(int*)b);
}int main() {int arr[] {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};int size sizeof(arr) / sizeof(arr[0]);qsort(arr, size, sizeof(int), compare);for (int i 0; i size; i) {printf(%d , arr[i]); // 1 1 2 3 3 4 5 5 5 6 9}return 0;
}
排序结构体数组
根据成员字符排序
struct Stu
{char name[20];int age;
};int cmp_struct_name(const void *e1, const void *e2)
{return strcmp(((struct Stu *)e1)-name, ((struct Stu *)e2)-name); // lisi、wangwu、zhangsan
}struct Stu s[] {{zhangsan, 22},{lisi, 24},{wangwu, 23}};
int struct_size sizeof(s) / sizeof(s[0]);
qsort(s, struct_size, sizeof(s[0]), cmp_struct_name); strcmp函数 strcmp函数用于比较字符串大小 —— 0 0 0strcmp() 函数比较字符串时会逐个字符地比较它们的 ASCII 码值直到有字符不相同时才停止比较。如果其中一个字符串已经结束了而另一个字符串还没有结束那么这个字符串就被认为比另一个字符串更小。头文件string.h 根据成员整型排序
struct Stu
{char name[20];int age;
};int cmp_struct_age(const void *e1, const void *e2)
{/* 从小到大 */return ((struct Stu *)e1)-age - ((struct Stu *)e2)-age; // 22 23 24
}struct Stu s[] {{zhangsan, 22},{lisi, 24},{wangwu, 23}};
int struct_size sizeof(s) / sizeof(s[0]);
qsort(s, struct_size, sizeof(s[0]), cmp_struct_age);
自定义qsort实现冒泡排序
/* 最终交换字节 */
void Swap(char *buf1, char *buf2, int width)
{for (int i 0; i width; i){char tmp *buf1;*buf1 *buf2;*buf2 tmp;buf1;buf2;}
}void my_qsort(void *base, int sz, int width, int (*cmp)(const void *e1, const void *e2))
{for (int i 0; i sz - 1; i){for (int j 0; j sz - 1 - i; j){/**实参传进去的是待比较的元素的地址之所以用char类型指针转换是因为最保险什么类型指针能访问的字节大小都可以从最小字节1开始活动比如这里数据是int类型那么cmp的实参第一个是 0*4第二是 1*4即第一个int数的地址第二个int数的地址*/if (cmp((char *)base j * width, (char *)base (j 1) * width) 0){Swap((char *)base j * width, (char *)base (j 1) * width, width);}}}
}my_qsort(arr, sz, sizeof(arr[0]), cmp_int);
for (int i 0; i sz; i)
{printf(%d , arr[i]); // 9 8 7 6 5 4 3 2 1 0
}
qsort的实现原理
qsort方法它使用了一种叫做快速排序Quicksort的算法。快速排序是一种分治的排序算法其基本思想是选择一个基准值然后将数组中小于基准值的元素放到基准值的左边大于基准值的元素放到基准值的右边最终使得基准值左边的所有元素都小于等于基准值右边的所有元素都大于等于基准值。然后递归地对基准值两边的子数组进行排序直到整个数组有序为止。
具体步骤
选择基准值从数组中选择一个元素作为基准值通常选择第一个或者中间的元素。分区过程将数组中的元素重新排列将小于或等于基准值的放在基准值的左边大于基准值的放在右边。递归排序对基准值左右两个子数组分别递归执行上述步骤。
快速排序示例代码
void quicksort(int arr[], int low, int high) {if (low high) {int pivot partition(arr, low, high);quicksort(arr, low, pivot - 1);quicksort(arr, pivot 1, high);}
}int partition(int arr[], int low, int high) {int pivot arr[low];int i low, j high;while (i j) {while (i j arr[j] pivot) {j--;}arr[i] arr[j];while (i j arr[i] pivot) {i;}arr[j] arr[i];}arr[i] pivot;return i;
}
在这个示例中quicksort 函数进行了递归排序partition 函数则负责进行分区操作。具体而言partition 函数以第一个元素作为基准值然后对数组进行分区操作并返回新的基准值的位置。对两个子数组进行的递归排序最终能够完成整个数组的排序过程。
快速排序的时间复杂度为 O(n log n)这使得快速排序成为一种非常高效的排序算法。在最好情况下快速排序的时间复杂度是 O(n log n)而在最坏情况下时间复杂度为 O(n^2)但平均情况下时间复杂度依然是 O(n log n)。当然这也取决于选择的基准值和数组的初始状态。
同时快速排序是一种原地排序算法它不需要额外的存储空间来存储临时数据只需要对原始数组进行原地交换和重排列。
总结来说快速排序通过选择基准值、分区和递归排序等步骤能够高效地对数组进行排序在平均情况下的时间复杂度为 O(n log n)适用于大多数场景下的排序需求。因此qsort 函数使用的快速排序算法在实际应用中具有较高的效率和性能表现。
