C语言qsort函数总结

　　前几天在leetcode上刷题，用qsort对二维数组进行排序，发现不会写qsort的比较函数。后面在网上找了几篇博客才弄明白，趁今天有空，对这个做一下总结，主要是以下4个方面：

1、qsort总体介绍

2、qsort应用于一维数组

3、qsort应用于指针数组

4、qsort应用于二维数组

1、qsort总体介绍

　　函数声明：void qsort(void *base, size_t nitems, size_t size, int (*compare)(const void *, const void*))

　　参数解释：

　　　　base-- 指向要排序的数组的第一个元素的指针。注意这里说是数组，所以必须是对连续的内存块进行排序。

　　　　nitems-- 由 base 指向的数组中元素的个数

　　　　size-- 数组中每个元素的大小，以字节为单位

　　　　compare-- 用来比较两个元素的函数。这是qsort最难的一部分了。这里主要要注意以下2点：1、在写compare函数时，你的两个形参必须是const void *型，但是在compare函数内部你又必须将const void *类型的形参转换为实际的类型。这是我最当时最难以理解的一个问题了：我需要转换成什么类型。看了别人的总结才知道，是：指向数组元素的指针，指向数组元素的指针，指向数组元素的指针。重要的事情说三遍。具体怎么理解，会在下面的例题中详细讲，我认为这时理解qsort的一个纲领。2、comapre函数的返回值是int，即整型。记住这一点，当你在比较double类型时就不会出错了。如果返回的是一个正数。说明第一个参数排在第二个参数的后面，如果是一个负数，说明第一个参数排在第二个参数的前面。如果等于零，说明它们两是相等的，谁先谁后都没关系。

2、qsort应用于一维数组　

2.1、一维整型数组的用法

　　举例：　

#include <stdio.h>
#include <stdlib.h>

int compare(const void *p1, const void *p2) {

    return (*(int *)p1) - (*(int *)p2); // 升序排序
    //return (*(int *)p2) - (*(int *)p1); // 降序排序
}

int main(int argc, char** argv)
{
    int i;
    int arr[5] = { 13, 17, 2, 7, 71 };
    printf("Before qsort: ");
    for (i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("
");

    qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), compare);
    printf("After qsort: ");
    for (i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("
");
    return 0;
}

　　运行结果：

　　解释一下 qsort的每一个参数。qsort第一个参数是指向待排序的数组的第一个元素的指针。由于数组名作为函数的参数时，那么数组名立刻就会转化为指向该数组第一个元素的指针。因此，第一个参数我们写的是数组名arr。第二个参数是数组元素的个数，所以可以写成：sizeof(arr)/sizeof(arr[0])。第三个参数是每个元素的大小，所以可以写成 sizeof(arr[0])。我们重点来看第四个参数，即compare函数。首先compare函数的入参都写成了const void*。其次，在函数中，我们需要把入参p1,p2转换成实际的类型。什么类型？ 依据纲领：指向数组元素的指针。我们的数组元素是什么？一个int(整型)。那么指向int的指针自然就是int*了。所以p1,p2在compare函数内部转换为了 (int *)p1, (int *)p2。然后再取解引用对int进行比较。

　　

2.2、一维double型数组的用法

　　举例：

#include <stdio.h>
#include <stdlib.h>
#define ARRAY_LEN 6

int compare1(const void *p1, const void *p2) {
    return (*(double *)p1) - (*(double *)p2);
}

int main(int argc, char** argv)
{
    int i;
    double arr1[ARRAY_LEN] = {1.2, -1.2, 1.3, 33.3, 44.5, 77.5};
    printf("Before qsort: ");
    for (i = 0; i < ARRAY_LEN; i++) {
        printf("%.1f ", arr1[i]);
    }
    printf("
");

    qsort(arr1, sizeof(arr1)/sizeof(arr1[0]), sizeof(arr1[0]), compare1);
    printf("After qsort: ");
    for (i = 0; i < ARRAY_LEN; i++) {
        printf("%.1f ", arr1[i]);
    }
    printf("
");
    return 0;
}

　　我以为这个程序会正确排序，但结果却啪啪打脸：

 　　what? 1.3 比 1.2要小？我读书虽然少，但1.3比1.2大这个常识，我还是知道的。那到底哪里出错了？没错，就是比较函数compare1的返回值写错了。比较函数的返回值类型是啥？ 整型。int型。但是你看compare1中返回值都写的是啥？我返回的是两个double类型相减的类型，还是double型。这样返回的double类型就会截断(假如我返回的是 -0.1，截断后返回的就是0了，就是说1.2和1.3它们谁先谁后都没关系，那我当然是啥都不做方便啊，自然1.2就放前面了)。返回的结果就不确定了，导致出现这个错误。

　　下面是修改之后的程序：

#include <stdio.h>
#include <stdlib.h>
#define ARRAY_LEN 6

int compare1(const void *p1, const void *p2) {
    return ((*(double *)p1) > (*(double *)p2)) ? 1 : -1;
}

int main(int argc, char** argv)
{
    int i;
    double arr1[ARRAY_LEN] = {1.2, -1.2, 1.3, 33.3, 44.5, 77.5};
    printf("Before qsort: ");
    for (i = 0; i < ARRAY_LEN; i++) {
        printf("%.1f ", arr1[i]);
    }
    printf("
");

    qsort(arr1, sizeof(arr1)/sizeof(arr1[0]), sizeof(arr1[0]), compare1);
    printf("After qsort: ");
    for (i = 0; i < ARRAY_LEN; i++) {
        printf("%.1f ", arr1[i]);
    }
    printf("
");
    return 0;
}

运行结果：

 

2.3、一维字符数组

　　这个没啥好说的，和一维整型数组的用法类似。直接看一个例题吧：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare2(const void *p1, const void *p2) {
    return (*(char *)p1) - (*(char *)p2);
}

int main(int argc, char** argv)
{
    char c[] = {'c', 'd', 'a', 'A', 'f', 'B', 'w', 'v', 'W', 'V'};
    printf("Before qsort: ");
    for (int i = 0; i < sizeof(c) / sizeof(c[0]); i++) {
        printf("%c ", c[i]);
    }
    printf("
");

    qsort(c, sizeof(c) / sizeof(c[0]), sizeof(c[0]), compare2);
    printf("After qsort: ");
    for (int i = 0; i < sizeof(c) / sizeof(c[0]); i++) {
        printf("%c ", c[i]);
    }
    printf("
");
    return 0;
}

　　运行结果：

3、qsort应用于指针数组

　　例题：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

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

int main()
{
    int i;
    char *arr[5] = { "i", "love", "c", "programming", "language" };

    qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(char *), compare);
    for (i = 0; i < 5; i++) {
        printf("%s ", arr[i]);
    }
    printf("
");
    return 0;
}

　　我们还是来分析一下为什么arg1的类型是 char **。根据纲领：指向数组元素的指针。我们首先需要确定数组元素的类型。这里数组元素的类型是是 char *。所以，arg1的类型就是指向char*的指针，即char**。

　　运行结果：

4、qsort应用于二维数组

　　例题：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int cmp1(const void *arg1, const void *arg2)
{
    return strcmp((*((char (*)[])arg1)), (*((char (*)[])arg2)));
}

int cmp2(const void *arg1, const void *arg2)
{
    return strcmp((char *)arg1, (char *)arg2);
}

int main(int argc, char **argv)
{
    int i;
    char str1[4][8] = {"java", "c", "python", "peal"};
    printf("COMPARE-FUNCTION-1: ");
    qsort(str1, 4, sizeof(str1[0]), cmp1);
    for (int i = 0; i < 4; i++) {
        printf("%s ", str1[i]);
    }
    printf("
");

    char str2[4][8] = {"java", "c", "python", "peal"};
    printf("COMPARE-FUNCTION-2: ");
    qsort(str2, 4, sizeof(str2[0]), cmp2);
    for (int i = 0; i < 4; i++) {
        printf("%s ", str2[i]);
    }
    printf("
");
    return 0;
 }

　　这一段代码刚开始我也是挺疑惑的，为什么compare函数的入参是这个类型的。其实只要记住qsort的纲领：指向数组元素的指针，就很容易理解了。首先来看cmp1，我们待排序的是一个二维数组，也就是数组的数组，那么我们这个数组元素的类型就是一个数组类型了(char []类型)。cmp1的参数就是指向一个数组类型的指针了。指向一个char []数组类型的指针当然就是用char (*)[]表示了。

　　接下来分析cmp2。我们将str2传入qsort函数，qsort函数将str2理解为指向数组第一个元素的指针，str2的第一个元素是str2[0][0]，所以参数arg1和arg2指的是指向"a[i][0]"的指针，我们知道，a[i][0]是字符，就是char，所以arg1和arg2指的是char *。

　　运行结果：

参考文献：

http://www.cppblog.com/Joe/archive/2010/10/29/131746.aspx?opt=admin

https://www.cnblogs.com/nipan/p/4119714.html