算法基础：快排：作弊神器qsort使用指南

快速排序是经典排序之一，传统的快排通过基准值不断就位的递归分割就完成了快速排序，但是快排是一个不稳定的排序，在遭遇到大数量的已经有序的输入序列的情况时，其好不容易降下来的nlogn的复杂度会重新恶化回n平方。而把这些都考虑了之后的快排就会几乎面目全非，c语言中的qsort或者c++中的sort，就是已经这样快看不出原貌的快排算法，调用其可以达到绕开很多基础算法考试的出题人的目的，堪称作弊神器。CJX，拿走不谢。

快排基础知识 传统快排的模拟实现

• https://liumiaocn.blog.csdn.net/article/details/109289285

快排为什么会超时

• https://liumiaocn.blog.csdn.net/article/details/109411350

qsort为什么会这么快

• https://liumiaocn.blog.csdn.net/article/details/109441556

qsort效率

使用如下示例代码即可验证快排效率

#include  #include  #include  #include  int compare(const void * a, const void * b) { return *((const int *)a) - *((const int *)b); } int main() { int n = 0; while (scanf("%d",&n) != EOF) { int* array = (int *)malloc(sizeof(int)*n); memset(array,0,sizeof(int)*n); for (int i=0; i<n; i++) array[i]=i+1; time_t start_time, end_time; start_time=clock(); qsort(array,n,sizeof(int),compare); end_time=clock(); printf("Time Used: %fs\n",(double)(end_time-start_time)/CLOCKS_PER_SEC); free(array); array= NULL; } } 

千万级别的有序序列进行排序，时间控制在600ms左右还是比较优秀的。

100000000
Time Used: 0.619994s

常见使用方式 参数说明

参数格式：qsort (void*, size_t, size_t,int ()(const void, const void*)); 参数1: 数组地址 参数2: 数组长度 参数3: 单个数组大小（可用sizeof(数组名[0])来通用完成) 参数4: 排序函数指针，void *可转换为相应类别，返回值>0/==0/<0分别对应这此函数的第一个参数和第二个参数的>/==/<的三种关系。

方式1: int数组排序

数组定义示例：int* array = (int *)malloc(sizeof(int)*n);

比较函数定义示例：

int compare(const void * a, const void * b) { return *((const int *)a) - *((const int *)b); } 

qsort调用示例 qsort(array,n,sizeof(int),compare);

方式2: char数组排序

数组定义示例：char* array = (char *)malloc(sizeof(char)*n);

比较函数定义示例：

int compare(const void * a, const void * b) { return *((const char *)a) - *((const char *)b); } 

qsort调用示例 qsort(array,n,sizeof(char),compare);

方式3: double数组排序

数组定义示例：double* array = (char *)malloc(sizeof(double)*n);

比较函数定义示例：

int compare(const void * a, const void * b) { return *((const double *)a) > *((const double *)b) ? 1 : -1; } 

qsort调用示例 qsort(array,n,sizeof(double),compare);

方式4: 字符串数组排序

数组定义示例：char** array = (char *)malloc(sizeof(char *)*n);

比较函数定义示例：

int compare(const void * a, const void * b) { return strcmp((const char *)a, (const char *)b); } 

qsort调用示例 qsort(array,n,sizeof(char),compare);

总结：实际上方式1-方式4都是一种使用方式，只是将qsort支持的常见类型列出来了而已, double型的写成这样主要是因为函数的返回值要求为int，所以根据结果进行了转化，另外对于方式4的字符串数组在使用上比较纠结的地方纯粹在于指向指针的指针的2纬字符数组的动态生成和free在使用上的一点小特点而已。

方式5: char数组逆序排序

数组定义示例：char* array = (char *)malloc(sizeof(char)nm);

比较函数定义示例：

int compare(const void * a, const void * b) { return *((const char *)b) - *((const char *)a); } 

qsort调用示例 qsort(array,n,sizeof(char),compare);

总结：这里给出了方式2的逆序排列方式，其他类型也是一样。

方式6: 结构体数组排序

结构体定义示例：

typedef struct Node{ int data; int key; }Node; 

数组定义示例：Node* array = (Node *)malloc(sizeof(Node)*row);

比较函数定义示例：

int compare(const void * a, const void * b) { return (*(const Node *)a).data - (*(const Node *)b).data; } 

qsort调用示例 qsort(array,n,sizeof(char),compare);

代码示例 示例1: 方式5之double类型的降序

方式5中的示例使用的char，这里用double进行演示使用方法。

#include  #include  #include  int compare(const void * a, const void * b) { return *((const double *)a) > *((const double *)b) ? 1 : -1; } void print_array(double* arr, int num) { for (int i=0; i<num; i++) printf("%lf ",arr[i]); printf("\n"); } int main() { int n = 0; while (scanf("%d",&n) != EOF) { double* array = (double *)malloc(sizeof(double)*n); memset(array,0,sizeof(double)*n); for (int i=0; i<n; i++) scanf("%lf",&array[i]); qsort(array,n,sizeof(double),compare); print_array(array,n); free(array); array= NULL; } } 

执行结果如下所示：

5
1 2 3 4 5
5.000000 4.000000 3.000000 2.000000 1.000000

示例2: 字符串数组升序

#include  #include  #include  int compare(const void * a, const void * b) { return strcmp(*(const char **)a,*(const char **)b); } void print_array(char** arr, int num) { for (int i=0; i<num; i++) printf("%s ",arr[i]); printf("\n"); } char** init_string_matrix(int row, int column) { char** array = (char**)malloc(sizeof(char *)*row); for (int i=0; i<row; i++) array[i] = (char *)malloc(sizeof(char)*column); for (int i=0; i<row; i++) scanf("%s",array[i]); return array; } void destroy_array(char** array, int row) { for (int i=0; i<row; i++) { free(array[i]); array[i]=NULL; } free(array); array=NULL; } int main() { int n = 0, m=0; while (scanf("%d %d",&n,&m) != EOF) { char** array = init_string_matrix(n,m); qsort(array,n,sizeof(char *),compare); print_array(array,n); destroy_array(array,n); } } 

执行结果如下所示：

3 10
hello
liumiaocn
world
hello liumiaocn world

示例3: 结构体方式

使用一个简单的结构体，按其成员变量data排序，qsort可以这样写。

#include  #include  #include  typedef struct Node{ int data; int key; }Node; int compare(const void * a, const void * b) { return (*(const Node *)a).data - (*(const Node *)b).data; } void print_array(Node* arr, int num) { for (int i=0; i<num; i++) printf("[%d %d] ",arr[i].key,arr[i].data); printf("\n"); } Node* init_struct_matrix(int row) { Node* array = (Node *)malloc(sizeof(Node)*row); memset(array,0,sizeof(Node)*row); for (int i=0; i<row; i++) { scanf("%d",&array[i].data); array[i].key=i+1; } return array; } void destroy_array(Node* array) { free(array); array=NULL; } int main() { int n = 0, m=0; while (scanf("%d",&n) != EOF) { Node* array = init_struct_matrix(n); qsort(array,n,sizeof(Node),compare); print_array(array,n); destroy_array(array); } } 

执行结果如下所示

5
5 4 3 2 1
[5 1] [4 2] [3 3] [2 4] [1 5]

总结

这篇文章整体介绍了一下qsort的使用方式。