@[toc]
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() 是一个不稳固的排序算法。
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 );
}
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;
}
构造体排序
#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;
}
字符串指针数组排序
#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 进行比拟。(数组名自身算一层指针,而外面的内容又是一层指针,数组寄存的是指向字符串的地址)
字符串二维数组排序
#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 进行比拟。
整型二维数组(力扣题目)
- 最靠近原点的 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 < pointsi < 10000
-10000 < pointsi < 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。
**CSDN:[CSDN 搜寻“嵌入式与 Linux 那些事”]