首页 > qsort函数使用方法总结(详细全面+代码)
头像
嵌入式与Linux那些事
编辑于 2021-07-05 17:24
+ 关注

qsort函数使用方法总结(详细全面+代码)

@[toc]

1. qsort函数原型

void qsort(
    void *base,
    size_t nmemb,
    size_t size,
    int (*compar)(const void *, const void *)
    );

  头文件:<stdlib.h>

  函数功能:qsort()函数的功能是对数组进行排序,数组有nmemb个元素,每个元素大小为size。

  参数base : base指向数组的起始地址,通常该位置传入的是一个数组名。

  参数nmemb :nmemb表示该数组的元素个数

  参数size :size表示该数组中每个元素的大小(字节数)

  参数(*compar)(const void *, const void *):此为指向比较函数的函数指针,决定了排序的顺序。

  函数返回值:无

  注意:如果两个元素的值是相同的,那么它们的前后顺序是不确定的。也就是说qsort()是一个不稳定的排序算法。

2. compar参数

  compar参数是qsort函数排序的核心内容,它指向一个比较两个元素的函数,注意两个形参必须是const void *型,同时在调用compar 函数(compar实质为函数指针,这里称它所指向的函数也为compar)时,传入的实参也必须转换成const void *型。在compar函数内部会将const void *型转换成实际类型,见下文。

int compar(const void *p1, const void *p2);

  如果compar返回值小于0(< 0),那么p1所指向元素会被排在p2所指向元素的前面

  如果compar返回值等于0(= 0),那么p1所指向元素与p2所指向元素的顺序不确定

  如果compar返回值大于0(> 0),那么p1所指向元素会被排在p2所指向元素的后面

  因此,如果想让qsort()进行从小到大(升序)排序,那么一个通用的compar函数可以写成这样:

//方法一
 int compare (const void * a, const void * b)
 {
   if ( *(MyType*)a <  *(MyType*)b ) return -1;
   if ( *(MyType*)a == *(MyType*)b ) return 0;
   if ( *(MyType*)a >  *(MyType*)b ) return 1;
 }

  注意:你要将MyType换成实际数组元素的类型。

  或者,如下所示。

//方法二
//升序排序
 int compare (const void * a, const void * b)
 {
     return ( *(int*)a - *(int*)b );
 }
//降序排列
 int compare (const void * a, const void * b)
 {
     return ( *(int*)b - *(int*)a );
 }

  如果变量 a 指向一个较小的负整型数,b指向一个较大的正整型数,(*(int*)a - *(int*)b) 表达式会计算出一个正数,这是错误的。

  因此,我们不能用减法来比较int的大小,这会产生溢出。取而代之地,我们可以使用大于、小于运算符来比较,如方法一所示。

3. int 数组排序

/* qsort example */
#include <stdio.h>     
#include <stdlib.h>     

int values[] = { 40, 10, 100, 90, 20, 25 };

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

int main ()
{
  int n;
  qsort (values, sizeof(values)/sizeof(values[0]), sizeof(int), compare);
  for (n=0; n<sizeof(values)/sizeof(values[0]); n++)
     printf ("%d ",values[n]);
  return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_16933601/article/details/107214404

4. 结构体排序

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>
// void qsort(void* base, size_t num, size_t size, int(*compare)(const void*, const void*))

typedef struct
{
    char name[30];   // 学生姓名
    int Chinese;    // 语文成绩
    int Math;        // 数学成绩  
    int English;     // 英语成绩
}st; 
int cmp(const void* a, const void* b)
{
    st* pa = (st*)a;
    st* pb = (st*)b;
    int num1 = pa->Chinese + pa->English + pa->Math;
    int num2 = pb->Chinese + pb->English + pb->Math;

    //return (int)num1 - num2;   // 从小到大,
    return (int)num2 - num1;   //  从大到小
}
int main(void)
{
    st students[7] = {
        {"周",97,68,45},
        {"吴",100,32,88},
        {"郑",78,88,78},
        {"王",87,90,89},
        {"赵",87,77,66},
        {"钱",59,68,98},
        {"孙",62,73,89}
    };
    qsort(students, 7, sizeof(st), cmp);   // 注意区别 students 与 st

    for (int i = 0; i < 7; i++)
    {
        printf("%s%4d%4d%4d\t", students[i].name, students[i].Chinese, students[i].Math, students[i].English);
        printf("总分:%d\n", students[i].Chinese + students[i].English + students[i].Math);
    }

    system("pause");
    return 0;
}

5. 字符串指针数组排序

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

int compare(const void *arg1, const void *arg2);

int
main(int argc, char** argv)
{
    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("\n");

}

int compare(const void *arg1, const void *arg2) {
    char *a = *(char**)arg1;
    char *b = *(char**)arg2;
    int result = strcmp(a, b);
    if (result > 0) {
        return 1;
    }
    else if (result < 0) {
        return -1;
    }
    else {
        return 0;
    }
}

  那么我们向qsort传入arr之后,qsort将arr理解为指向数组中第一个元素的指针,所以形参表中,arg1和arg2其实是指向“指向常量字符串的指针”的指针,是char**。而我们需要传给strcmp这个字符串比较函数的,是“指向字符串的指针”,是char*,所以我们将void*转换为char**,然后解引用,得到char*,赋予a和b。接下来使用strcmp对a和b进行比较。(数组名本身算一层指针,而里面的内容又是一层指针,数组存放的是指向字符串的地址)

6. 字符串二维数组排序

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

int compare(const void *arg1, const void *arg2);

int
main(int argc, char** argv)
{
    int i;

    char arr[5][16] = { "i", "love", "c", "programming", "language" };

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

int compare(const void *arg1, const void *arg2) {
    char *a = (char*)arg1;
    char *b = (char*)arg2;
    int result = strcmp(a, b);
    if (result > 0) {
        return 1;
    }
    else if (result < 0) {
        return -1;
    }
    else {
        return 0;
    }
}

  这里对二维数组进行排序,其实是对二维数组的第二维中存放的字符串进行排序。所以qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), compare);对qsort函数的调用中,第二个参数是待排元素的个数(5个),第三个参数是待排元素的大小(16)。

  我们将arr传入qsort函数,qsort函数将arr理解为指向数组第一个元素的指针,arr的第一个元素是arr[0][0],所以参数arg1和arg2指的是指向"a[i][0]"的指针,我们知道,a[i][0]是字符,就是char,所以arg1和arg2指的是char *。我们将void*转换为char*,赋予a和b,调用strcmp函数对a和b进行比较。

7. qsort函数应用:整型二维数组

  1. 最接近原点的 K 个点

  我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。(这里,平面上两点之间的距离是欧几里德距离。)你可以按任何顺序返回答案。除了点坐标的顺序之外,答案确保是唯一的。

示例 1:

输入:points = [[1,3],[-2,2]], K = 1
输出:[[-2,2]]
解释: (1, 3) 和原点之间的距离为sqrt(10), (-2, 2) 和原点之间的距离为 sqrt(8), 由于 sqrt(8) < sqrt(10),(-2, 2) 离原点更近。 我们只需要距离原点最近的 K = 1 个点,所以答案就是 [[-2,2]]。
示例 2:
输入:points = [[3,3],[5,-1],[-2,4]], K = 2
输出:[[3,3],[-2,4]] (答案 [[-2,4],[3,3]] 也会被接受。)
提示:
1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

/* qsort排序二维数组,cmp的每个元素都是一个独立的 int 数组,也就是指针 */
int cmp(const void* a, const void* b) {

    // 转换为对应一维数组
    int* arry1 = *(int**)a;
    int* arry2 = *(int**)b;

    // 获取对应arry1 的两个元素
    int x1 = *arry1;
    int y1 = *(arry1 + 1);

    int x2 = *arry2;
    int y2 = *(arry2+1);

    return (x1*x1 + y1*y1) - (x2*x2 + y2*y2);
}


int** kClosest(int** points, int pointsSize, int* pointsColSize, int K, int* returnSize, int** returnColumnSizes){
    if(points==NULL || pointsSize==0 || K==0) return NULL;

    qsort(points, pointsSize, sizeof(int)*pointsColSize[0], cmp);
    /*   这里注意 qsort 的传参,使用不当会报错
    Line 11: Char 11: runtime error: load of misaligned address 0x602000000032 for type 'int *', which requires 8 byte alignment (solution.c)       0x602000000032: note: pointer points here
    */

    // 指定return输出的二维数组是包含有几个一维数组
    *returnSize = pointsSize > K ? K : pointsSize;

    *returnColumnSizes = (int*)malloc(sizeof(int*)*(*returnSize));
    // 指定每个一维数组的 col 
    for(int i = 0; i< (*returnSize); i++) {
        (*returnColumnSizes)[i] = 2;
    }
    return points;
}


【嵌入式软件笔试面试】牛客干货贴汇总(持续更新中~)

如果觉得本篇文章对你有帮助,在【收藏】的时候,可以点个【赞】支持下作者,你的每一个【赞】我都当成了喜欢!

动态引导三联_CSDN_

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

热门推荐