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

爱被打了一巴掌 2022-11-21 14:44 152阅读 0赞

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

### 目录 ###

*  快排基础知识
 *   *  传统快排的模拟实现
     *  快排为什么会超时
     *  qsort为什么会这么快
 *  qsort效率
 *  常见使用方式
 *   *  参数说明
     *  方式1: int数组排序
     *  方式2: char数组排序
     *  方式3: double数组排序
     *  方式4: 字符串数组排序
     *  方式5: char数组逆序排序
     *  方式6: 结构体数组排序
 *  代码示例
 *   *  示例1: 方式5之double类型的降序
     *  示例2: 字符串数组升序
     *  示例3: 结构体方式
 *  总结

--------------------

# 快排基础知识 #

## 传统快排的模拟实现 ##

*  [https://liumiaocn.blog.csdn.net/article/details/109289285][https_liumiaocn.blog.csdn.net_article_details_109289285]

## 快排为什么会超时 ##

*  [https://liumiaocn.blog.csdn.net/article/details/109411350][https_liumiaocn.blog.csdn.net_article_details_109411350]

## qsort为什么会这么快 ##

*  [https://liumiaocn.blog.csdn.net/article/details/109441556][https_liumiaocn.blog.csdn.net_article_details_109441556]

--------------------

# qsort效率 #

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

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <time.h>
    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)*n*m);

> 比较函数定义示例：

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 <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    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 <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    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 <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    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的使用方式。

[https_liumiaocn.blog.csdn.net_article_details_109289285]: https://liumiaocn.blog.csdn.net/article/details/109289285
[https_liumiaocn.blog.csdn.net_article_details_109411350]: https://liumiaocn.blog.csdn.net/article/details/109411350
[https_liumiaocn.blog.csdn.net_article_details_109441556]: https://liumiaocn.blog.csdn.net/article/details/109441556