一、qsort函数简介

排序方法有很多种：选择排序，冒泡排序，归并排序，快速排序等。 看名字都知道快速排序是目前公认的一种比较好的排序算法。因为他速度很快，所以系统也在库里实现这个算法，便于我们的使用。 这就是qsort函数(全称quicksort)。它是ANSI C标准中提供的，其声明在stdlib.h文件中，是根据二分法写的，其时间复杂度为n*log(n)

功能： 使用快速排序例程进行排序
头文件：stdlib.h
用法： void qsort(void* base,size_t num,size_t width,int(__cdeclcompare)(const void,const void*));
参数： 1 待排序数组，排序之后的结果仍放在这个数组中
　　　 2 数组中待排序元素数量
　　　 3 各元素的占用空间大小（单位为字节）
　　 4 指向函数的指针，用于确定排序的顺序（需要用户自定义一个比较函数）

二、qsort函数常用实例

1.比较整型数组

#include <stdlib.h>
#include <stdio.h>int cmp_int(const void* _a, const void* _b)
{int* a = (int*)_a;    //强制类型转换int* b = (int*)_b;return *a - *b;
}int main() {int arr[] = {1, 3, 6, 2};printf("排序前："); for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i){printf("%d  ",arr[i]);}qsort(arr,sizeof(arr)/sizeof(arr[0]) ,sizeof(arr[0]), cmp_int); printf("\n排序后：");for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i){printf("%d  ",arr[i]);}
} 

2.比较char数组

#include <stdlib.h>
#include <stdio.h>int cmp_char(const void *a,const void *b)
{return *(char *)a - *(char *)b;
}int main() {char arr[] = {'b', 'd', 'a', 'c'};printf("排序前："); for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i){printf("%c  ", arr[i]);}qsort(arr,sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), cmp_char); printf("\n排序后：");for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i){//printf("");printf("%c  ", arr[i]);}
} 

3.比较double数组

#include <stdlib.h>
#include <stdio.h>int cmp_double(const void *a, const void *b)
{return *(double *)a > *(double *)b? 1 : -1;} int main() {double arr[] = {1.0, 3.0, 6.0, 2.0};printf("排序前："); for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i){printf("%.2lf  ",arr[i]);}qsort(arr,sizeof(arr)/sizeof(arr[0]) ,sizeof(arr[0]), cmp_double); printf("\n排序后：");for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i){printf("%.2lf  ",arr[i]);}
} 

4.比较字符串

4.1按首字母排序

#include<stdio.h>
#include<stdlib.h>
#define L 10
#define K 10
int inc(const void *a, const void *b)
{return *(char *)a - *(char *)b;} 
int main ()
{char a[L][K] = {"rbsc","jcse","efgd","arbs","bbs","cbfe","dgafg" ,"ewqrta","ofgd","mbcv",};qsort(a, L, sizeof(char) * K, inc);for (int i = 0; i < L; i++){printf("%s\n", a[i]);}} 

下面是我还在尝试的一种方法，先记录一下

#include <stdlib.h>
#include <stdio.h>int cmp_string(const void *a, const void *b)
{return (char *)a - (char *)b;
} int main() {char* arr[] = {"rbas", "wlyy", "doii", "xkyy"};printf("排序前："); for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i){printf("%s  ",arr[i]);}qsort(arr,4 ,5 , cmp_string); printf("\n排序后：");for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i){printf("%s  ",arr[i]);}
} 
---------------------------------------------------------#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>int cmp_string(const void* a, const void* b)
{assert(a != NULL && b != NULL);const char** lhs = (const char**)a;const char** rhs = (const char**)b;return strcmp(*lhs, *rhs);
}int main() {char* arr[] = {"rbas", "wlyy", "doii", "xkyy"};printf("排序前："); for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i){printf("%s  ",arr[i]);}qsort(arr,0 ,sizeof(arr)/sizeof(arr[0]) - 1, cmp_string); printf("\n排序后：");for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i){printf("%s  ",arr[i]);}
}     

4.2按长度排序

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define L 10
#define K 10
int inc(const void *a, const void *b)
{return strlen((char *)a) > strlen((char *)b) ? 1 : -1;} 
int main ()
{char a[L][K] = {"rbsc","jcsse","efgdsd","arbs","bbs","cbfefaa","dgafg" ,"ewqrta","ofgd","mbcv312",};qsort(a, L, sizeof(char) * K, inc);for (int i = 0; i < L; i++){printf("%s\n", a[i]);}} 

4,3按字典顺序

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define L 10
#define K 10
int inc(const void *a, const void *b)
{return strcmp((char * )a, (char *)b);} 
int main ()
{char a[L][K] = {"rbsc","jcsse","afgdsd","arbs","abs","cbfefaa","cgafg" ,"ewqrta","ofgd","mbcv312",};qsort(a, L, sizeof(char) * K, inc);for (int i = 0; i < L; i++){printf("%s\n", a[i]);}} 

5.结构体排序

5.1 多级排序

结构体体的三级排序测试：
第一级是对学生成绩整体从小到大排序；
第二级是对相同成绩的学生，按照姓名进行排序；
第三级是对相同成绩、姓名的学生，按照学号进行排序；

#include<stdio.h>
#include<stdlib.h>
#include<string.h> 
typedef struct student
{int id;char name[10];int grade;	
}student;int cmp1(const void *a, const void *b)//一级排序
{student *s1 = (student*)a;student *s2 = (student*)b;return s1->id - s2->id;
}int cmp2(const void *a,const void *b)//二级排序
{student *s1 = (student*)a;student *s2 = (student*)b;if(strcmp(s1->name , s2->name) != 0)return strcmp(s1->name , s2->name);	else	return s1->id - s2->id;				
}int cmp3(const void *a,const void *b)//三级排序
{student *s1 = (student*)a;student *s2 = (student*)b;if(s1->grade != s2->grade)	return s1->grade - s2->grade;else{if(strcmp(s1->name , s2->name) != 0)return strcmp(s1->name , s2->name);elsereturn s1->id - s1->id;}
}int main()
{int i,N,C;scanf("%d %d",&N,&C);student *stu;stu=(student*)malloc(N*sizeof(student));for(i = 0 ; i < N ; i++)scanf("%d %s %d" , &stu[i].id , stu[i].name , &stu[i].grade);switch(C){case 1:	qsort(stu, N, sizeof(student), cmp1);break;//一级排序case 2:	qsort(stu, N, sizeof(student), cmp2);break;//二级排序case 3:	qsort(stu, N, sizeof(student), cmp3);break;//三级排序}printf("排序结果:\n");for(i = 0 ; i < N ; i++)printf("%03d %s %d\n" , stu[i].id , stu[i].name , stu[i].grade);return 0;
}

三、qsort深度剖析

qsort函数原型如下：

void qsort(void* base,size_t num,size_t width,int(__cdecl*compare)(const void*,const void*)); 

qsort函数实现对不同元素的排序主要就是通过对compare函数进行定义实现的，对于每一种变量类型的排序，我们都需要重新实现一种compare函数。