基本排序算法的总结

image-20221123105226308

1)不基于比较的排序,对样本数据有严格要求,不易改写

2)基于比较的排序,只要规定好两个样本怎么比大小就可以直接复用

3)基于比较的排序,时间复杂度的极限是O(N*logN)

4)时间复杂度 O(N*logN)、额外空间复杂度低于 O(N) 、且稳定的基于比较的排序是不存在的。

5)为了绝对的速度快排、为了省空间堆排、为了稳定性归并

Sort函数

在C++中使用 sort() 函数需要使用 #include<algorithm>头文件。algorithm 意为"算法",是C++的标准模版库(STL)中最重要的头文件之一,提供了大量基于迭代器的非成员模版函数。

STL中的 sort() 并非只是普通的快速排序,除了对普通的快速排序进行优化,它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况,能自动选用合适的排序方法。

当数据量较大时采用快速排序,分段递归。一旦分段后的数据量小于某个阀值,为避免递归调用带来过大的额外负荷,便会改用插入排序。而如果递归层次过深,有出现最坏情况的倾向,还会改用堆排序

image-20221123105449515

所以说 sort() 是一个比较灵活的函数,它也会根据我们数据的需要进行排序,所以我们就不用担心以上的问题了。对于大部分的排序需求,sort() 都是可以满足的。

但是很显然,sort() 排序不是稳定排序

image-20221123110454186

Effective STL对如何选择排序函数总结的很好:
1)若需对 vector, string, deque, 或 array 容器进行全排序,你可选择 sortstable_sort
2)若只需对 vector, string, deque, 或 array 容器中取得 top n 的元素,部分排序 partial_sort 是首选.
3)若对于 vector, string, deque, 或 array 容器,你需要找到第 n 个位置的元素或者你需要得到 top n 且不关系 top n 中的内部 顺序,nth_element 是最理想的;
4)若你需要从标准序列容器或者 array 中把满足某个条件或者不满足某个条件的元素分开,你最好使用partitionstable_partition
5)若使用的 list 容器,你可以直接使用 partitionstable_partition 算法,你可以使用 list::sort 代替 sortstable_sort 排序。

🧐 本文作者:
😉 本文链接:https://lukeyalvin.site/archives/100.html
😊 版权说明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。
最后修改:2022 年 11 月 23 日
赏杯咖啡