快速排序库函数qsort的调用细则

快速排序库函数qsort的调用细则 快速排序库函数qsort是C标准库中的一种排序算法，用于对数组进行排序。qsort函数包含在<stdlib.h>头文件中，需要在函数头部加上#include<stdlib.h>以便调用。qsort函数有四个参数，分别是参与排序的数组名、元素个数、单个元素的大小和比较函数。 qsort函数的调用格式为：qsort(s, n, sizeof(s[0]), cmp);其中，s是参与排序的数组名，n是参与排序的元素个数，sizeof(s[0])是单个元素的大小，cmp是比较函数的名字。cmp函数是指导qsort如何进行排序的函数，目的是告诉qsort以什么样的方式进行排序。 cmp函数的定义为：int cmp(const void *a, const void *b);其中，a和b是两个指针，指向要比较的元素。cmp函数的返回值是整数类型，用于确定元素的顺序。如果返回值小于0，则a排在b之前；如果返回值等于0，则a和b的顺序不变；如果返回值大于0，则a排在b之后。 关于qsort的调用细则，需要注意以下几点： 1. 快排的复杂度：快排的平均时间复杂度为N*Log2(N)，最坏情况为N^2，当元素全部是已经排好的顺序时，最好情况为N。当元素个数比较少时（10^2的数量级左右），快排的速度跟冒泡相比并没有快很多。 2. 快排是不稳定的：快排会打乱相同元素的先后顺序。如果需要对相同元素进行稳定排序，可以使用结构体来实现。 3. cmp函数的参数必须都是const void *的，否则会出问题。 4. qsort的第三个参数sizeof(s[0])是安全且方便的，特别是对结构体。 5. 如果要对数组进行部分排序，可以修改第一个和第二个参数，例如：qsort(&s[i], m, sizeof(s[i]), cmp);其中，s[i]是开始排序的地址，m是参与排序的元素个数。 下面是一个简单的示例程序，用于对int数组进行排序： ```c #include <stdio.h> #include <stdlib.h> int s[10000], n, i; int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } void main() { scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &s[i]); } qsort(s, n, sizeof(s[0]), cmp); for (i = 0; i < n; i++) { printf("%d\n", s[i]); } } ``` 这个程序首先读取用户输入的数组元素个数n，然后读取n个整数并将其存储在数组s中。接着，使用qsort函数对数组进行排序，最后将排序结果输出。