当前位置：首页 > news >正文

初识快速排序函数qsort()

news 2026/7/2 14:29:21

思路：题目说明用二分查找，每次查找向下取整，就清楚是跟二分查找有关了。但是需要注意题目其实并没有说输入的数组是有序的，所以在二分查找之前我们必须要先排序。考虑到时间复杂度的问题，这里我们选择用快速排序的方法。

转自豆包
qsort()是 C 标准库（<stdlib.h>）中的快速排序函数，用于对任意类型的数组进行排序，是 C 语言中常用的通用排序工具。
一、基本语法
c
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *));
参数说明：
base：待排序数组的首地址（任意类型指针）；
nitems：数组的元素个数；
size：数组中单个元素的字节大小（例如int类型填sizeof(int)）；
compar：比较函数指针，用于定义两个元素的比较规则。
二、比较函数的规则
比较函数的格式必须为：
c
int compar(const void *a, const void *b);
函数逻辑：
返回值< 0：a应排在b之前；
返回值= 0：a和b相等；
返回值> 0：a应排在b之后。

代码如下：

#include <stdio.h> #include <stdlib.h> // qsort的比较函数（升序） int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } int main() { int n, target; // 多组输入（EOF终止） while (scanf("%d", &n) != EOF) { int arr[n]; // 1. 输入无序数组 for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } // 2. 输入目标值 scanf("%d", &target); // 3. 对数组升序排序（关键：让二分查找可行） qsort(arr, n, sizeof(int), cmp); // 4. 二分查找（逻辑与之前一致） int left = 0, right = n - 1; int count = 0; int found = 0; while (left <= right) { count++; int mid = (left + right) / 2; if (arr[mid] == target) { found = 1; break; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } // 5. 输出结果 if (found) { printf("%d\n", count); } else { printf("NO.\n"); } } return 0; }

题2

思路：将非负数和负数分离，并记录原位置，分别按要求排序，把排好序的输入到原位置即可。

这里我们同样需要用到快速排序，并对它有进一步的了解。

代码如下：

#include <stdio.h> #include <stdlib.h> // 非负数排序：升序（从小到大） int compare_non_neg(const void *a, const void *b) { return (*(int *)a - *(int *)b); } // 负数排序：降序（即绝对值从小到大，-1 > -2） int compare_neg(const void *a, const void *b) { return (*(int *)b - *(int *)a); } int main() { int n; // 输入序列长度 scanf("%d", &n); int arr[n], res[n]; int non_neg[n], neg[n]; // 存储非负数、负数 int idx_non_neg = 0, idx_neg = 0; // 非负数、负数数组的索引 int pos_non_neg[n], pos_neg[n]; // 存储非负数、负数在原数组中的位置 // 输入原序列，并分离非负数/负数，记录位置 for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); if (arr[i] >= 0) { non_neg[idx_non_neg] = arr[i]; pos_non_neg[idx_non_neg] = i; // 记录非负数的原位置 idx_non_neg++; } else { neg[idx_neg] = arr[i]; pos_neg[idx_neg] = i; // 记录负数的原位置 idx_neg++; } } // 对非负数、负数分别排序 qsort(non_neg, idx_non_neg, sizeof(int), compare_non_neg); qsort(neg, idx_neg, sizeof(int), compare_neg); // 初始化结果数组（可选，避免随机值） for (int i = 0; i < n; i++) { res[i] = 0; } // 回填非负数到原位置 for (int i = 0; i < idx_non_neg; i++) { res[pos_non_neg[i]] = non_neg[i]; } // 回填负数到原位置 for (int i = 0; i < idx_neg; i++) { res[pos_neg[i]] = neg[i]; } // 输出结果 for (int i = 0; i < n; i++) { printf("%d ", res[i]); } printf("\n"); return 0; }

转自豆包（简化了一下）
要理解这个比较函数里的指针用法，就要理解qsort对比较函数的要求：
qsort是 C 标准库的通用排序函数，能排序任意类型的数据（int、char、结构体等），所以它的比较函数参数被设计成const void *类型
const void *a/const void *b：表示 “指向任意类型数据的指针”，且指针指向的内容不可修改（const）；
但我们要排序的是int类型数组，所以必须把void*转换成int*才能操作，这是指针转换的核心原因。