马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
1.排序算法先容和常用排序方法复杂度
在现实生存中，常常必要对事物或信息举行排序。排序是什么呢？排序就是把无序的序列变革成有序的。排序之后，我们就可以通过 O ( 1 ) O(1) O(1)的时间复杂度查询。
排序算法又分为比力排序和非比力排序。下表为各人提供了常见的排序方法和复杂度以及备注。反面我也会举行逐一解说。
常见的比力排序方法
名称匀称时间复杂度最坏时间复杂度空间复杂度是否稳固备注冒泡排序 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)✔无选择排序 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)✘假如利用 O ( n ) O(n) O(n)的额外空间，可以做到稳固排序。此时必要利用元素插入而非互换的方式。插入排序 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)✔最坏时间复杂度可以更正确地表现为 O ( n + d ) O(n+d) O(n+d)，此中 d d d为原始序列中的逆序数量。归并排序 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( n ) O(n) O(n)✔无快速排序 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( n 2 ) O(n^2) O(n2) O ( l o g 2 n ) O(log_2n) O(log2n)✘可用原址(in-palce)来淘汰储存空间的占用。堆排序 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( 1 ) O(1) O(1)✘无 注1：稳固性指排序完之后，假如有雷同元素，那么雷同元素的相对位置稳定。
注2：原址这个词通常用于形貌算法或数据布局的操纵，它意味着在处置惩罚过程中不必要额外的空间，而是直接修改原有的数据布局，好比数组。
常见的非比力排序方法
名称匀称时间复杂度最坏时间复杂度空间复杂度是否稳固备注基数排序 O ( k n + ∑ i = 1 k w i ) O(kn+\sum_{i=1}^kw_i) O(kn+∑i=1kwi) O ( k n + ∑ i = 1 k w i ) O(kn+\sum_{i=1}^kw_i) O(kn+∑i=1kwi) O ( n + m a x i w i ) O(n+max_iw_i) O(n+maxiwi)✔ k k k为关键值的分别个数， w i w_i wi为第 i i i个关键值分别的值域规模。计数排序 O ( n + w ) O(n+w) O(n+w) O ( n + w ) O(n+w) O(n+w) O ( n + w ) O(n+w) O(n+w)✔ w w w为值域规模桶排序 O ( n + n 2 m + m ) O(n+\frac{n^2}{m}+m) O(n+mn2+m) O ( n 2 ) O(n^2) O(n2) O ( n m ) O(n_m) O(nm)✔对应 m m m个桶且桶内做插入排序的情况。假如在桶内接纳归并排序等，最坏时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) 在比赛中，一样平常不会单独考你排序算法，而是会联合其他的算法或数据布局（好比贪心，可变数组）来出题。
2.sort函数应用
在这篇文章中，我们起首会解说STL中最方便实用的sort函数。它可不但是简单的快速排序。
当数据量较大时，sort函数利用快速排序算法，分段归并排序；一旦分段后的数据量小于某个门槛，为克制快速排序的递归调用带来过大的额外负荷，就改用插入排序；假如递归条理过深，还会改用堆排序（HeapSort）。因此它具有很好的匀称性能，时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)。
sort(数组名+起始下标,数组名+停止下标+1,排序规则);
前两个参数我们已经很熟悉了。紧张看看排序规则。 S T L STL STL为我们提供了6中默认的排序规则。
名称功能equal_to相称not_equal_to不相称less小于greater大于less_equal小于即是greater_equal大于即是利用示比方下：
- int a[]={8,5,2,6,9,10};
- sort(a,a+6,greater<int>());
- bool cmp(int x,int y)//从大到小排序
- {
- return x>y;
- }
- sort(a,a+n,cmp);
字符串存储高精度数字从小到大比力规则。
- bool cmp(string a,string b)
- {
- if(a.size()!=b.size())return a.size()<b.size();
- return a<b;//按照字典序排序
- }
- struct node
- {
- int x,y,z;
- }a[10010];
- bool cmp1(node a,node b)//单关键字排序
- {
- return a.x<b.x;
- }
- bool cmp2(node a,node b)//双关键字排序
- {
- if(a.x==b.x)return a.y<b.y;
- return a.x<b.x;
- }
- bool cmp3(node a,node b)//三关键字排序
- {
- if(a.x==b.x)
- if(a.y==b.y)
- return a.z<b.z;
- else
- return b.y<b.y;
- else
- return a.x<b.x;
- }
函数功能void sort(first, last)对容器或平常数组中 [ f i r s t , l a s t ) [first, last) [first,last)范围内的元素举行排序，默认举行升序排序。bool is_sorted(first, last)检测 [ f i r s t , l a s t ) [first, last) [first,last)范围内是否已经排好序，默认检测是否按升序排序。bool is_sorted_until (first, last)和is_sorted()函数功能雷同，唯一的区别在于，假如 [ f i r s t , l a s t ) [first, last) [first,last)范围的元素没有排好序，则该函数会返回一个指向首个不遵照排序规则的元素的迭代器。void nth_element (first, nth, last)找到 [ f i r s t , l a s t ) [first, last) [first,last) 范围内按照排序规则（默认按照升序排序）应该位于第 n t h nth nth个位置处的元素，并将其放置到此位置。同时使该位置左侧的全部元素都比其存放的元素小，该位置右侧的全部元素都比其存放的元素大。4.sort函数练习
详见【题解】sort函数应用——【洛谷P1059】[NOIP2006 遍及组] 明显的随机数，【洛谷P1093】[NOIP2007 遍及组] 奖学金。
喜欢就订阅此专辑吧！
假如您还想相识更多内容，欢迎扫码关注蓝胖子编程教导
|
发表于 2026-2-7 14:34:15