算法题中排序题的思路、模板与cmp/qsort用法详解-三亩地-编程学习日记

一、排序题解题通用思路

识别排序需求：分析题目，判断是否需要通过排序来获得有序数据，以便后续操作（如贪心、双指针、二分查找）。常见场景包括：
- 求最大/最小值、前K大/小元素。
- 合并区间、安排会议/任务（按开始或结束时间排序）。
- 分组、配对问题（如两数之和、最近点对）。
- 自定义排序规则（如按多个属性排序）。
确定排序依据（Key）：明确按哪个或哪些属性排序。可能是单一属性（如数值大小），也可能是复合属性（先按身高排，身高相同按体重排）。
选择排序方法：
- 语言内置排序：绝大多数情况下，直接使用编程语言提供的排序函数（如C++的sort、Python的sorted）即可，其时间复杂度通常为O(n log n)。
- 特殊数据结构：如果只需要前K个元素，考虑使用堆（优先队列）。
定义比较规则：当排序规则非默认（升序/降序）或涉及复杂对象时，需要自定义比较函数（Comparator）。这是排序题的核心考点。
排序后处理：在有序数组上执行后续算法逻辑。

二、排序模板与核心代码

1. C语言模板（使用qsort）

#include <stdio.h> #include <stdlib.h> #include <string.h> // 示例：对整数数组升序排序 int cmp_int_asc(const void *a, const void *b) { return *(int*)a - *(int*)b; // 升序 } int main() { int nums[] = {3, 1, 4, 1, 5}; int n = sizeof(nums) / sizeof(nums[0]); qsort(nums, n, sizeof(int), cmp_int_asc); // 打印排序结果 for (int i = 0; i < n; i++) { printf("%d ", nums[i]); } printf("\n"); return 0; } // 降序排序 int cmp_int_desc(const void *a, const void *b) { return *(int*)b - *(int*)a; // 降序 } // 使用自定义比较函数（例如按绝对值大小升序） int cmp_abs_asc(const void *a, const void *b) { int x = abs(*(int*)a); int y = abs(*(int*)b); if (x < y) return -1; if (x > y) return 1; return 0; } // 对自定义结构体排序 typedef struct { char name[20]; int age; } Person; int cmp_person(const void *a, const void *b) { Person *pa = (Person*)a; Person *pb = (Person*)b; // 先按年龄升序，年龄相同按名字字典序升序 if (pa->age != pb->age) return pa->age - pb->age; return strcmp(pa->name, pb->name); }

2. Python 模板（使用sorted或list.sort）

# 列表排序（原地修改） nums = [3, 1, 4, 1, 5] nums.sort() # 升序 nums.sort(reverse=True) # 降序 返回新列表（不修改原列表） sorted_nums = sorted(nums) # 升序 sorted_nums_desc = sorted(nums, reverse=True) # 降序 使用key参数自定义排序依据（例如按绝对值排序） sorted_by_abs = sorted(nums, key=lambda x: abs(x)) 多级排序：先按长度，再按字典序 words = ["apple", "banana", "cherry", "date"] sorted_words = sorted(words, key=lambda x: (len(x), x)) 对元组列表排序（默认按第一个元素，然后第二个...） pairs = [(1, 3), (2, 2), (1, 1)] sorted_pairs = sorted(pairs) # 结果：[(1, 1), (1, 3), (2, 2)]

三、C语言qsort与cmp函数详解

在C语言中，标准库函数qsort用于对数组进行快速排序，其核心在于自定义cmp（比较）函数。

1. qsort函数原型

#include <stdlib.h> void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

base：指向待排序数组首元素的指针。
nmemb：数组中元素的个数。
size：每个元素的大小（字节数），可用sizeof获取。
compar：比较函数指针。该函数接收两个const void*参数，返回int。

2. cmp比较函数编写规则

cmp函数的返回值决定了排序顺序：

返回负数（如 -1）：表示第一个参数应排在第二个参数前面（升序时表示a < b）。
返回0：表示两元素相等。
返回正数（如 1）：表示第一个参数应排在第二个参数后面（升序时表示a > b）。

记忆口诀：a - b升序，b - a降序（适用于整型）。

3. 常用cmp函数示例

#include <stdio.h> #include <stdlib.h> #include <string.h> // 示例1：对int数组升序排序 int cmp_int_asc(const void *a, const void *b) { return (int)a - (int)b; // 升序 } // 降序 int cmp_int_desc(const void *a, const void *b) { return (int)b - (int)a; // 降序 } // 示例2：对double数组升序排序（注意浮点数不能直接相减返回int） int cmp_double_asc(const void *a, const void *b) { double diff = (double)a - (double)b; if (diff < 0) return -1; if (diff > 0) return 1; return 0; } // 示例3：对字符串数组按字典序升序排序 int cmp_str_asc(const void a, const void b) { return strcmp((const char*)a, (const char*)b); } // 示例4：对结构体数组排序（先按分数降序，分数相同按学号升序） typedef struct { int id; int score; } Student; int cmp_student(const void *a, const void *b) { Student sa = (Student)a; Student sb = (Student)b; if (sa->score != sb->score) { return sb->score - sa->score; // 分数降序 } return sa->id - sb->id; // 学号升序 } int main() { // 对int数组排序 int nums[] = {3, 1, 4, 1, 5}; int n = sizeof(nums) / sizeof(nums[0]); qsort(nums, n, sizeof(int), cmp_int_asc); // 对结构体数组排序 Student students[] = {{101, 85}, {102, 90}, {103, 85}}; int m = sizeof(students) / sizeof(students[0]); qsort(students, m, sizeof(Student), cmp_student); return 0; }

4. qsort使用注意事项

类型转换：在cmp函数内，需先将const void*指针转换为实际类型的指针。
稳定性：qsort是不稳定排序，相等元素的相对位置可能改变。若需要稳定排序，需自己实现或使用其他方法。

溢出风险：对整型使用a - b时，若差值超出int范围会导致溢出错误。更安全的写法是：

int cmp_safe(const void *a, const void *b) { int x = *(int*)a; int y = *(int*)b; if (x < y) return -1; if (x > y) return 1; return 0; }

四、经典题型与实战模板

题型1：最大/最小K个数（Top K）

思路：排序后取前K个或后K个。时间复杂度O(n log n)。若只需前K个，可用堆优化至O(n log K)。

// C语言：取最小的K个数 #include <stdio.h> #include <stdlib.h> int cmp_int_asc(const void *a, const void *b) { return *(int*)a - *(int*)b; } void getLeastNumbers(int arr[], int n, int k, int result[]) { // 先排序 qsort(arr, n, sizeof(int), cmp_int_asc); // 取前k个 for (int i = 0; i < k; i++) { result[i] = arr[i]; } } int main() { int arr[] = {3, 2, 1, 5, 6, 4}; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; int result[k]; getLeastNumbers(arr, n, k, result); printf("最小的%d个数: ", k); for (int i = 0; i < k; i++) { printf("%d ", result[i]); } printf("\n"); return 0; }

题型2：自定义排序（如“把数组排成最小的数”）

思路：定义一种新的比较规则，将数字转换为字符串后比较拼接结果。

// C语言：将数组里所有数字拼接成最小的数字 #include <stdio.h> #include <stdlib.h> #include <string.h> // 比较函数：比较两个字符串拼接后的大小 int cmp_min_number(const void *a, const void *b) { char str1[24], str2[24], combine1[48], combine2[48]; sprintf(str1, "%d", *(int*)a); sprintf(str2, "%d", *(int*)b); // 拼接两种顺序 strcpy(combine1, str1); strcat(combine1, str2); strcpy(combine2, str2); strcat(combine2, str1); return strcmp(combine1, combine2); } void minNumber(int nums[], int n, char result[]) { // 先排序 qsort(nums, n, sizeof(int), cmp_min_number); // 拼接结果 result[0] = '\0'; for (int i = 0; i < n; i++) { char str[12]; sprintf(str, "%d", nums[i]); strcat(result, str); } } int main() { int nums[] = {3, 32, 321}; int n = sizeof(nums) / sizeof(nums[0]); char result[100]; minNumber(nums, n, result); printf("拼接成的最小数字: %s\n", result); // 输出: 321323 return 0; }

五、总结与技巧

掌握核心：排序题的核心在于自定义比较规则。深刻理解cmp函数的返回值与排序顺序的关系。
语言选择：。
- Python：灵活运用key和lambda。
- C：牢记qsort和cmp的固定模式。
调试技巧：编写cmp函数时，可在函数内打印比较的值，验证逻辑是否正确。
注意边界：处理浮点数、大整数时，避免溢出和精度问题。
融会贯通：排序常作为其他算法（贪心、双指针、二分）的预处理步骤，结合使用威力更大。

日记详情

算法题中排序题的思路、模板与cmp/qsort用法详解