©2020-2024 ioDraw All rights reserved,
Privacy Policy
前言
C语言中有三大排序方法：选择排序、冒泡排序和快速排序。
选择排序的工作原理：
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。
以此类推，直到全部待排序的数据元素的个数为零。
冒泡排序的工作原理：
n个数字进行排序，以升序排序为例。
比较相邻两个数的大小，如果前一个数比后一个数大就互换数值，从本轮开始比较的第一个数到最后一个数。共进行n-1轮。
我相信大部分人都很了解选择排序和冒泡排序，但是选择排序和冒泡排序的时间复杂度是比快速排序的时间复杂度高的多的，在代码的编写和运行效率上，快速排序优于选择排序和冒泡排序。但是因为不了解快速排序的实现原理和方法，很多人对快排望而止步，那么今天我就来带大家看看如何使用快速排序。
2、了解qsort函数
1、qsort函数的原型：
void qsort (void* base, size_t num, size_t size,int(*compar)(const void*,
const void*));
base —— 就是要排序数组的起始地址，如对arr[5]排序，则arr就是数组的起始地址
num —— 数组元素的个数
size —— 就是数组中每一个元素的所占字节数，用sizeof(arr[0])来计算
int(*compar)(const void*, const void*)) —— compar这是一个函数指针，指向的是 int 函数名(const
void* e1,const void *e2)
头文件： #include<stdlib.h>
2、qsort函数的使用：
qsort使用起来最大的障碍就是int(*compar)(const void*, const void*))
，到底要编写一个怎样的比较函数呢？别急，我先介绍一下。
这个函数是自己定义的，*e1和*e2是你要排序数组的两个进行比较的元素，你必须保证你所定义的函数返回值遵守下列规则：
* 如果*e1大于*e2，就返回大于0的数（函数的返回类型为整形）
* 如果*e1小于*e2，就返回小于0的数
* 如果*e1等于*e2，就返回等于0的数
*
强制类型转换时，类型应该为实参的类型，比如你要比较int型数据，那么强制转换为int型，如果是结构体就强制转换为结构体，如果是char型就强制转换为char型
比如说我们要比较的数是整形类型
int compare1(const void* e1, const void *e2) { //将void*类型的指针e1和e2强制类型转换成int*型
return *((int*)e1) - *((int *)e2); //一定要强制类型转换，因为e1和e2都是void*指针，没有类型的指针
//如果不想要升序排列，想要按降序排列，就可以return *((int*)e2) - *((int *)e1); }
比如说我们要比较的数是char型
int compare_char(const void * e1, const void * e2) { return *(char *)e1 -
*(char *)e2; }
再比如说我们要比较的数是字符串类型
struct Stu { char name[20]; int age; float grade; }; int compare_name(const
void* e1, const void *e2) { //这可不能直接相加减，要用上strcmp函数 return strcmp((((struct Stu
*)e1)->name), (((struct Stu *)e2)->name)); }
void *指针的注意事项：
* void *p=&a; 无论a是什么数据类型，int，float,double,char均可
* 不能这样写 *p ； 因为不知道p指针的类型，不知道解引用应该访问多少个字节
* 也不能这样写*(p+1);也就是*p+1也不可以用，因为不知道+1是加多少个字节
void*那么麻烦我们为什么还要定义指针变量e1和e2为const void*呢？
因为void*型可以接受各种数据类型的地址，普适性强，不用担心不适配的问题。加一个const是因为要防止通过e1和e2来改变实参。
3、快排的几个应用
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<assert.h>
struct Stu { char name[20]; int age; float grade; }; //整形的比较 int compare1(const
void* e1, const void *e2) { return *((int*)e1) - *((int *)e2); } //结构体中整形的比较
int compare_age(const void* e1, const void *e2) { return ((struct Stu
*)e1)->age - ((struct Stu *)e2)->age; } //结构体中字符串的比较 int compare_name(const
void* e1, const void *e2) { return strcmp((((struct Stu *)e1)->name), (((struct
Stu *)e2)->name)); } //字符串的比较 int compare_char(const void * e1, const void *
e2) { return *(char *)e1 - *(char *)e2; } void test1() { int arr[5] = {
4,3,2,9,1 }; int num = sizeof(arr) / sizeof(arr[0]); qsort(arr, num,
sizeof(arr[0]), compare1); } void test2() { struct Stu arr2[3] = {
{"zhangsan",17,98.5},{"lisi",16,28.76},{"wangwu",25,93} }; int num =
sizeof(arr2) / sizeof(arr2[0]); qsort(arr2, num, sizeof(arr2[0]), compare_age);
qsort(arr2, num, sizeof(arr2[0]), compare_name); } void test3() { char a[20] =
"dcba"; int sz = strlen(a); qsort(a, sz, sizeof(a[0]), compare_char);
printf("%s", a); } int main() { test1();//整形数组的排序 test2();//结构体数组的排序
test3();//字符数组的排序 return 0; } //查看是否真正改变了排序可以通过调试来查看
如果大家想知道qsort函数的使用原理，我将会写一篇 根据qsort函数的实现原理实现bubble_sort函数的改版 的博客。
希望以上内容能被大家喜欢，更新不易，点个赞再走吧（^_^）