还在用 STL 排序？

使用 C 库函数

很多人都不知道的是，其实 C 语言也是自带排序函数的，就是位于 <stdlib.h> 库中的 qsort

函数声明：

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

其中

• base - 指向要排序的数组的第一个元素的指针
• nitems - base 指向的数组中元素的个数
• size - 数组中每个元素的大小（以字节为单位）
• compar - 用来比较两个元素的函数

与 <algorithm> 中的 std::sort 略有差异，尤其是在 compar 函数的定义上。

其形参必须是 const void* 型（可以理解为，在 compar 函数内部会将 const void* 型转换成实际类型）。

• 如果返回值小于0（< 0），那么p1所指向元素会被排在p2所指向元素的左面；
• 如果返回值等于0（= 0），那么p1所指向元素与p2所指向元素的顺序不确定；
• 如果返回值大于0（> 0），那么p1所指向元素会被排在p2所指向元素的右面。

在 C11 标准中，新增了另一个排序函数 qsort_s ，但在无编译开关的情况下无法使用。

另外，虽然它的名字叫 qsort ，但目前还没有任何一个 C 标准规定其必须通过快排实现（）

实测在整数排序下，效率与 STL 相差无几，都在 140ms/1.20MB 左右。

Code © :

#include <stdio.h>
#include <stdlib.h>

const int N = 1e5 + 10;
int cmp(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int n, i, a[N];
    scanf("%d", &n);
    for (i=0; i<n; ++i) scanf("%d", a+i);
    qsort(a, n, sizeof(int), cmp);
    for (i=0; i<n-1; ++i) printf("%d ", a[i]);
    printf("%d\n", a[n-1]);
    return 0;
}

使用 PB_DS

PB_DS，又称平板电视，是一个冷门但功能极为强大的 GNU-cpp 扩展库，但在 OI 中（尤其是省选以下）极少用到。

该库中提供了大量数据结构（虽然不开O2的话几乎都会T掉），以树形结构为主，拿出来基本个个都可以排序

堆：

（未开 O2，248ms/5.23MB ）

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

__gnu_pbds::priority_queue < int, greater<int>, pairing_heap_tag > q;

int n;
int main() {
    scanf("%d", &n);
    for(int i=0, a; i<n; ++i) scanf("%d", &a), q.push(a); 
    for(int i=0; i<n; ++i) printf("%d ", q.top()), q.pop();
    return 0;
}

由于 pb_ds 中的 tree 相当于 set 而不是 multiset ，因此比手写快排还长，不再展示。