标准 C 库提供可用于对数组进行排序的qsort() 。顾名思义,该函数使用 QuickSort 算法对给定数组进行排序。以下是 qsort() 的原型
关于 qsort() 的关键点是比较器函数compare。比较器函数接受两个参数并包含确定它们在排序输出中的相对顺序的逻辑。这个想法是提供灵活性,以便 qsort() 可以用于任何类型(包括用户定义的类型),并且可以用于获得任何所需的顺序(增加、减少或任何其他)。
比较器函数将两个指针作为参数(都类型转换为 const void*)并通过返回定义元素的顺序(以稳定和传递的方式
假设我们需要根据分数升序对学生进行排序。比较器函数如下所示:
以下是一个有趣的问题,可以借助qsort()和比较器函数轻松解决。
给定一个整数数组,以奇数先出现,偶数后出现的方式对其进行排序。奇数应按降序排序,偶数应按升序排序。
简单的方法是首先修改输入数组,使偶数和奇数分开,然后分别对两个部分(奇数和偶数)应用一些排序算法。
但是,存在一种有趣的方法,对快速排序的比较器功能稍作修改。这个想法是编写一个比较器函数,它将两个地址 p 和 q 作为参数。令 l 和 r 为 p 和 q 所指向的数。该函数使用以下逻辑:
1) 如果 (l 和 r) 都是奇数,则将两者中的较大者放在首位。
2) 如果 (l 和 r) 都是偶数,则将两者中较小的放在前面。
3)如果其中一个是偶数,另一个是奇数,把奇数放在第一位。
以下是上述方法的 C 实现。
输出:
void qsort (void* base, size_t num, size_t size,
int (*comparator)(const void*,const void*));
int comparator(const void* p1, const void* p2);
返回值含义 <0 p1指向的元素在p2指向的元素之前 0 p1指向的元素等价于p2指向的元素 >0 p1指向的元素在p2指向的元素之后
Source: http://www.cplusplus.com/reference/cstdlib/qsort/例如,让有一个学生数组,其中以下是学生的类型。
struct Student
{
int age, marks;
char name[20];
};
int comparator(const void *p, const void *q)
{
int l = ((struct Student *)p)->marks;
int r = ((struct Student *)q)->marks;
return (l - r);
}
#include <stdio.h>
#include <stdlib.h>
// This function is used in qsort to decide the relative order
// of elements at addresses p and q.
int comparator(const void *p, const void *q)
{
// Get the values at given addresses
int l = *(const int *)p;
int r = *(const int *)q;
// both odd, put the greater of two first.
if ((l&1) && (r&1))
return (r-l);
// both even, put the smaller of two first
if ( !(l&1) && !(r&1) )
return (l-r);
// l is even, put r first
if (!(l&1))
return 1;
// l is odd, put l first
return -1;
}
// A utility function to print an array
void printArr(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
printf("%d ", arr[i]);
}
// Driver program to test above function
int main()
{
int arr[] = {1, 6, 5, 2, 3, 9, 4, 7, 8};
int size = sizeof(arr) / sizeof(arr[0]);
qsort((void*)arr, size, sizeof(arr[0]), comparator);
printf("Output array isn");
printArr(arr, size);
return 0;
}
Output array is
9 7 5 3 1 2 4 6 8
练习:
给定一个整数数组,以交替方式对其进行排序。替代方式意味着偶数索引处的元素单独排序,奇数索引处的元素单独排序。