还在用 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 (C) :

#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-C++ 扩展库,但在 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 ,因此比手写快排还长,不再展示。