C++ STL提供了类似C语言中 qsort() 的函数排序，它对向量或数组进行排序，其中数组中的项是随机排列的。
sort() 函数通常需要两个参数，第一个参数是数组/向量开始排序的位置，第二个参数是我们希望数组/向量排序的长度。第三个参数是可选的，可以在我们想按字典顺序对元素排序的情况下使用。
默认情况下，sort() 函数按升序对元素进行排序。
下面是一个显示 sort() 工作的简单程序。
// C++ program to demonstrate default behaviour of
// sort() in STL.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
/*Here we take two parameters, the beginning of the array and the length n upto which we want the array to be sorted*/
sort(arr, arr + n);
cout << "\nArray after sorting using "
"default sort is : \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}输出：
Array after sorting using default sort is :
0 1 2 3 4 5 6 7 8 9sort() 接受第三个参数，用于指定元素排序的顺序。我们可以通过“greater()”函数进行降序排序。此函数以将更大元素放在前面的方式进行比较。
// C++ program to demonstrate descending order sort using
// greater<>().
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n, greater<int>());
cout << "Array after sorting : \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}输出：
Array after sorting :
9 8 7 6 5 4 3 2 1 0我们还可以编写自己的比较器函数并将其作为第三个参数传递。这个“comparator”函数返回一个值；转换为bool，它基本上告诉我们传递的“first”参数是否应该放在传递的“second”参数之前。
例如：在下面的代码中，假设区间 {6,8} 和 {1,9} 在“compareInterval”函数（比较器函数）中作为参数传递。现在因为 i1.first (=6) > i2.first (=1)，所以我们的函数返回“false”，这告诉我们“first”参数不应该放在“second”参数之前，所以排序将先按 {1,9} 排序，然后按 {6,8} 排序。
// A C++ program to demonstrate
// STL sort() using
// our own comparator
#include <bits/stdc++.h>
using namespace std;
// An interval has a start
// time and end time
struct Interval {
int start, end;
};
// Compares two intervals
// according to staring times.
bool compareInterval(Interval i1, Interval i2)
{
return (i1.start < i2.start);
}
int main()
{
Interval arr[]
= { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } };
int n = sizeof(arr) / sizeof(arr[0]);
// sort the intervals in increasing order of
// start time
sort(arr, arr + n, compareInterval);
cout << "Intervals sorted by start time : \n";
for (int i = 0; i < n; i++)
cout << "[" << arr[i].start << "," << arr[i].end
<< "] ";
return 0;
}输出：
Intervals sorted by start time :
[1,9] [2,4] [4,7] [6,8]标准C库提供了qsort函数，可用于对数组进行排序。下面是 qsort() 函数的原型。
// Sort an array of any type. The parameters are, base
// address of array, size of array and pointer to
// comparator function
void qsort (void* base, size_t num, size_t size,
int (*comparator)(const void*, const void*));它需要一个指向数组的指针、数组中元素的数量、每个元素的大小和一个比较器函数。
C++ 标准库提供了一个源自 STL 的类似函数 sort()。 我们已经在上文讨论了 C++ 排序。 以下是 C++ sort() 函数的原型。
// To sort in default or ascending order.
template
void sort(T first, T last);
// To sort according to the order specified
// by comp.
template
void sort(T first, T last, Compare comp);相等元素的顺序不能保证不变。C++ 提供了可用于保持顺序的 std::stable_sort。
不同之处：
1.实现的细节：
顾名思义，qsort 函数使用 QuickSort 算法对给定的数组进行排序，尽管 C 标准不要求它实现快速排序。
C++ 排序函数使用混合算法 introsort。不同的实现使用不同的算法。例如，GNU 标准 C++ 库使用 3 部分混合排序算法：首先执行 introsort（introsort 本身是快速排序和堆排序的混合），然后对结果进行插入排序。
2.复杂度：
C标准没有提到qsort的复杂度。新的C11标准要求排序的复杂度在最坏情况下为O(N log N)。以前的 C 版本（例如 C03）允许 O(N^2) 的最坏情况，平均复杂度为 O(N log N)。
3.运行时间：
STL sort的运行速度比C的qsort排序快，因为C的模板为特定的数据类型和特定的比较函数生成优化代码。
STL的排序比手工编码的快速排序快20%到50%，比c库qsort函数快250%到1000%。C语言可能是最快的语言，但是qsort非常慢。
当我们尝试在 C14 上对一百万个整数进行排序时，C qsort() 花费的时间为 0.247883 秒，而 C sort() 花费的时间仅为 0.086125 秒。
// C++ program to demonstrate performance of
// C qsort and C++ sort() algorithm
#include <bits/stdc++.h>
using namespace std;
// Number of elements to be sorted
#define N 1000000
// A comparator function used by qsort
int compare(const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
// Driver program to test above functions
int main()
{
int arr[N], dupArr[N];
// seed for random input
srand(time(NULL));
// to measure time taken by qsort and sort
clock_t begin, end;
double time_spent;
// generate random input
for (int i = 0; i < N; i++)
dupArr[i] = arr[i] = rand()%100000;
begin = clock();
qsort(arr, N, sizeof(int), compare);
end = clock();
// calculate time taken by C qsort function
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
cout << "Time taken by C qsort() - "
<< time_spent << endl;
time_spent = 0.0;
begin = clock();
sort(dupArr, dupArr + N);
end = clock();
// calculate time taken by C++ sort
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
cout << "Time taken by C++ sort() - "
<< time_spent << endl;
return 0;
}输出：
Time taken by C qsort() - 0.247883
Time taken by C++ sort() - 0.086125由于内联，C++ sort() 在等效数据上比 qsort() 快得多。默认情况下，整数容器上的 sort() 将被编译为使用 std::less::operator()，它将被内联，而 sort() 将直接比较整数。另一方面，对于编译器未能优化的每个比较，qsort() 将通过函数指针进行间接调用。
4.灵活性：
STL 的排序适用于所有数据类型和不同的数据容器，如 C 数组、C++ 向量、C++ 双端队列等，以及其他可由用户编写的容器。这种灵活性在 C 中很难实现。
5.安全性：
与qsort相比，模板化排序更具有类型安全性，因为它不需要像 qsort 那样通过不安全的 void 指针访问数据项。
[1]Shubham Agrawal.std::sort() in C++ STL[EB/OL].https://www.geeksforgeeks.org/sort-c-stl/,2021-02-17.
[2]Aditya Goel.C qsort() vs C++ sort()[EB/OL].https://www.geeksforgeeks.org/c-qsort-vs-c-sort/,2018-08-14.
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/zsx0728/article/details/118542200
内容来源于网络，如有侵权，请联系作者删除！