定义于头文件 <stdlib.h>
算法库提供大量用途的函数(例如查找、排序、计数、操作),它们在元素范围上操作。注意范围定义为 [first, last)
,其中 last
指代要查询或修改的最后元素的后一个元素。
对一个范围内的拥有一定未指定类型的元素排序
qsort,
qsort_s
定义于头文件 | ||
void qsort( void *ptr, size_t count, size_t size, | (1) | |
errno_t qsort_s( void *ptr, rsize_t count, rsize_t size, int (*comp)(const void *, const void *, void *), void *context ); | (2) | (C11 起) |
1) 对 ptr
所指向的数组以升序排序。数组包含 count
个长度为 size
字节的元素。用 comp
所指向的函数比较对象。
2) 同 (1) ,除了传递给 comp
附加环境参数 context
,还会在运行时检测下列错误,并调用当前安装的制约处理函数:
count
或size
大于 RSIZE_MAXkey
、ptr
或comp
是空指针(除非count
为零)
同所有边界检查函数, qsort_s
仅若实现定义了 __STDC_LIB_EXT1__ ,且用户在包含 stdlib.h
前定义 __STDC_WANT_LIB_EXT1__ 为整数常量 1 才保证可用。
若 comp
指示两元素相等,则它们排序后的结果是未指定的。
参数
ptr | - | 指向待排序的数组的指针 |
count | - | 数组的元素数目 |
size | - | 数组每个元素的字节大小 |
comp | - | 比较函数。若首个参数小于第二个,则返回负整数值,若首个参数大于第二个,则返回正整数值,若两参数相等,则返回零。 比较函数的签名应等价于如下形式: int cmp(const void *a, const void *b); 该函数必须不修改传递给它的对象,而且在调用比较相同对象时必须返回一致的结果,无关乎它们在数组中的位置。 |
context | - | 附加信息(例如,对照序列),作为第三个参数传递给 comp |
返回值
1) (无)
2) 成功时为零,若检测到运行时制约违规,则为非零
注意
与名称无关,C 和 POSIX 标准都未要求此函数用快速排序实现,也未保证任何复杂度或稳定性。
与其他边界检查函数不同, qsort_s
不将零大小数组视作运行时强制违规,而是不修改数组并成功返回(另一个接受零大小数组的函数是 bsearch_s )。
在 qsort_s
之前,qsort
的用户通常用全局变量来将附加语境传递给比较函数。
调用示例
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
#include <time.h>using namespace std;struct Cell
{int x;int y;Cell &operator +=(const Cell &cell){x += cell.x;y += cell.y;return *this;}bool operator <(const Cell &cell) const{if (x == cell.x){return y < cell.y;}else{return x < cell.x;}}bool operator >(const Cell &cell) const{if (x == cell.x){return y > cell.y;}else{return x > cell.x;}}
};int compare_Cells_less(const void* a, const void* b)
{Cell arg1 = *(const Cell*)a;Cell arg2 = *(const Cell*)b;if (arg1 < arg2){return -1;}if (arg1 > arg2){return 1;}return 0;// return (arg1 > arg2) - (arg1 < arg2); // 可行的简写// return arg1 - arg2; // 错误的简写(若给出 INT_MIN 则会失败)
}int compare_Cells_greater(const void* a, const void* b)
{Cell arg1 = *(const Cell*)a;Cell arg2 = *(const Cell*)b;if (arg1 < arg2){return 1;}if (arg1 > arg2){return -1;}return 0;
}std::ostream &operator<<(std::ostream &os, const Cell &cell)
{os << "{" << cell.x << "," << cell.y << "}";return os;
}int main()
{srand((unsigned)time(NULL));;std::cout.setf(std::ios_base::boolalpha);auto func1 = [](){int n = std::rand() % 10 + 100;Cell cell{n, n};return cell;};Cell cells[] = {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}};std::generate(std::begin(cells), std::end(cells), func1);std::cout << "cells : ";std::copy(std::begin(cells), std::end(cells), std::ostream_iterator<Cell>(std::cout, " "));std::cout << std::endl;std::cout << "is_sorted: " << std::is_sorted(std::begin(cells), std::end(cells));std::cout << std::endl << std::endl;qsort(cells, std::distance(std::begin(cells), std::end(cells)), sizeof(Cell), compare_Cells_less);std::cout << "cells : ";std::copy(std::begin(cells), std::end(cells), std::ostream_iterator<Cell>(std::cout, " "));std::cout << std::endl;std::cout << "is_sorted: " << std::is_sorted(std::begin(cells), std::end(cells));std::cout << std::endl << std::endl;auto is_sortf = [](const Cell & a, const Cell & b){if (a.x == b.x){return a.y > b.y;}return a.x > b.x;};std::generate(std::begin(cells), std::end(cells), func1);std::cout << "cells : ";std::copy(std::begin(cells), std::end(cells), std::ostream_iterator<Cell>(std::cout, " "));std::cout << std::endl;std::cout << "is_sorted: " << std::is_sorted(std::begin(cells), std::end(cells), is_sortf);std::cout << std::endl << std::endl;qsort(cells, std::distance(std::begin(cells), std::end(cells)), sizeof(Cell), compare_Cells_greater);std::cout << "cells : ";std::copy(std::begin(cells), std::end(cells), std::ostream_iterator<Cell>(std::cout, " "));std::cout << std::endl;std::cout << "is_sorted: " << std::is_sorted(std::begin(cells), std::end(cells), is_sortf);std::cout << std::endl << std::endl;return 0;
}
输出
cells : {109,109} {106,106} {107,107} {106,106} {108,108}
is_sorted: falsecells : {106,106} {106,106} {107,107} {108,108} {109,109}
is_sorted: truecells : {103,103} {105,105} {108,108} {109,109} {108,108}
is_sorted: falsecells : {109,109} {108,108} {108,108} {105,105} {103,103}
is_sorted: true