首页 算法

还在用 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-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 ，因此比手写快排还长，不再展示。
   
 更新于