C qsort 与 C++ sort 函数

C++ 有两个常用的排序函数：sort 与 qsort。下面介绍二者用法与区别。

1.qsort

qsort 是 C 标准库函数，申明于头文件 <stdlib.h>，基于快速排序实现。

函数原型如下：

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

base 待排序数组首地址。

num 数组中待排序元素数量。

size 各元素的占用空间大小。

compar 指向函数的指针，根据返回值确定排序的顺序 。

使用示例：

#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare(const void* a, const void* b) {
	return (*(int*)a - *(int*)b);
}

int main() {
	qsort(values, 6, sizeof(int), compare);
	for (int i = 0; i < 6; i++){
		printf("%d ", values[i]);
	}
	return 0;
}

运行输出：

10 20 25 40 90 100

2.sort

sort 是 C++ 标准模板库（STL）中的函数模板，定义于头文件<algorithm>，所在名字空间为 std。

将范围 [first,last) 中的元素按升序排序。

第一个版本使用 operator< 来比较元素，第二个版本使用 comp 来比较元素。

不保证等效元素保持其原始相对顺序（请参阅 stable_sort ）。

函数原型：

template <class RandomAccessIterator>  void sort (RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

first, last 用于指定待排序元素下标，不包含 last。

comp（可选）为接受范围内的两个元素作为参数，并返回可转换为 bool 的值的二元函数。返回 true 表示第一个参数排在第二个参数之前。

使用示例：

#include <stdio.h>      /* printf */
#include <algorithm>    /* sort */

int values[] = { 40, 10, 100, 90, 20, 25 };

int main() {
	std::sort(values, values + 6);
	for (int i = 0; i < 6; i++){
		printf("%d ", values[i]);
	}
	return 0;
}

运行输出：

10 20 25 40 90 100

3.区别

qsort 和 sort 都是标准库函数，都可用于排序，但是二者也存在着一些区别：

• 性质不同。

qsort 是 C 的库函数，sort 是 C++ STL 中的函数模板。

• sort 更易于使用。

qsort 必须要指定比较函数，而 sort 可以指定，也可以缺省。

• sort 速度更快。

sort 比 qsort 更快，因为 C++ 的模板为特定数据类型和特定比较函数生成优化的代码。sort 速度比手动编写的快速排序快 20% 到 50%，比 qsort 快 250% 到 1000%。C 可能是最快的语言，但 qsort 非常慢。

由于内联，C++ sort() 在同等数据上比 qsort() 快得多。默认情况下，整数容器上的 sort() 将被编译为使用 std::less::operator() ，它将被内联，并且 sort() 将直接比较整数。 而 qsort() 通过函数指针进行间接调用比较元素大小，导致编译器无法优化。

• sort 灵活性更高。

sort 适用于所有数据类型和不同的数据容器，例如 C 数组、C++ 向量、C++ 双端队列等以及用户可以编写的其他容器。 这种灵活性在 C 语言中很难实现。

• sort 安全性更高。

与 qsort 相比，模板化排序更加类型安全，因为它不需要像 qsort 那样通过不安全的 void 指针访问数据项。

综上所述，优先使用 sort。

参考文献

qsort - cplusplus.com sort - cplusplus.com C qsort() vs C++ sort()