【蓝桥】排序与排列

排序

常见排序的介绍与比较

排序是数据处理的基本操作。常见的排序算法有:

排序算法 时间复杂度 原理
选择排序 O(n^2) 比较
插入排序 O(n^2) 比较
冒泡排序 O(n^2) 比较
归并排序 O(nlogn) 比较、分治
快速排序 O(nlogn) 不稳定 比较、分治
堆排序 O(nlogn) 比较、二叉树
计数排序 O(n+k) 不稳定 对数值按位划分
基数排序 O(n) 对数值按位划分
桶排序 O(n) 对数值分类、分治

前三种比较的办法都是暴力排序,效率相对比较低下。快排虽然不稳定,但在通常情况下效果最好,不通常的情况往往指的是已经排好的情况。

对数值按位划分的做法是 以空间换取时间的做法。使用要求十分苛刻!

一般编程语言都有排序的相应函数,很舒服了❤

C++的sort()函数

使用参数是这样的:sort(开始地址,结束地址,[排序方法])

排序方法有四种自带的lessgreaterless_equalgreater_equal。缺省情况下是less从小到大排序。

当然也可以手撸排序策略,具体使用方法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
bool my_less(int i, int j) {return (i < j);} //自定义小于
bool my_greater(int i, int j) {return (i > j);} //自定义大于
int main (){
vector<int> a = {3,7,2,5,6,8,5,4};
sort(a.begin(),a.begin()+4); //对前4个排序,输出2 3 5 7 6 8 5 4
//sort(a.begin(),a.end()); //从小到大排序, 输出2 3 4 5 5 6 7 8
//sort(a.begin(),a.end(),less<int>()); //输出2 3 4 5 5 6 7 8
//sort(a.begin(),a.end(),my_less); //自定义排序,输出 2 3 4 5 5 6 7 8
//sort(a.begin(),a.end(),greater<int>());//从大到小排序,输出 8 7 6 5 5 4 3 2
//sort(a.begin(),a.end(),my_greater); // 输出 8 7 6 5 5 4 3 2
for(int i=0; i<a.size(); i++) //输出
cout<<a[i]<< " ";
return 0;
}

使用 cmp()函数还可以对结构体排序

1
2
3
4
5
6
7
8
9
10
11
struct Student{
char name[256];
int score; //分数
};
bool cmp(struct Student* a,struct Student* b){//按分数从大到小排序
return a->score > b->score;
}
……
vector<struct Student*> list; //定义list,把学生信息存到list里
……
sort(list.begin(), list.end(), cmp); //按分数排序

Python的sort()和sorted()函数

  1. sort()sorted() 的区别 sort() 是应用在 list 上的方法,而 sorted 可以对所有可迭代的对象进行排序操作。  一个关键的区别是:sort 是在原位重新排列,而 sorted() 产生一个新的列表。
  2. sorted() 说明 Python3 和 Python2的 sorted() 定义不同,下面给出 Python3 的定义。 sorted(iterable, key=None, reverse=False)
    • 参数:
      • iterable:可迭代对象。
      • key:用来进行比较的元素,只有一个参数,具体的函数的参数取自于可迭代对象中,指定可迭代对象中的一个元素来进行排序。
      • reverse:排序规则,reverse = True 降序,reverse = False 升序(默认)。
    • 返回值:重新排序的列表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
a = [5,7,6,3,4,1,2]
print(sorted(a)) #输出:[1, 2, 3, 4, 5, 6, 7], a不变
a.sort() #直接在a上原位排序,a改变了
print(a) #输出:[1, 2, 3, 4, 5, 6, 7]

a = "bcdae"
print(sorted(a)) #输出:['a', 'b', 'c', 'd', 'e']
#这样是错的:a.sort(),因为sort 是应用在list上的,a不是list

s1 = [('b', 'A', 15), ('c', 'B', 12), ('e', 'B', 10)]
s2 = sorted(s1, key=lambda s: s[2]) # 按第3个排序,默认升序
print(s2) #输出:[('e', 'B', 10), ('c', 'B', 12), ('b', 'A', 15)]
s3 = sorted(s1, key=lambda s: s[2], reverse=True) # 按第3个排序,降序
print(s3) #输出:[('b', 'A', 15), ('c', 'B', 12), ('e', 'B', 10)]

排列

C++ :next_permutation()

next_permutation()是从当前的全排列开始输出,而不是输出所有的全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <bits/stdc++.h>
using namespace std;
int main(){
string s="bca";
do{
cout<<s<<endl;
}while(next_permutation(s.begin(),s.end()));
return 0;
}
/*
输出:
bca
cab
cba
*/

不过可以通过sort先进行排列,然后在进行全排列输出,这样就能输出全排列了!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main(){
string s="bca";
sort(s.begin(),s.end()); //字符串内部排序,得到最小的排列“abc”
do{
cout<<s<<endl;
}while(next_permutation(s.begin(),s.end()));
return 0;
}
/*输出:
abc
acb
bac
bca
cab
cba
*/

C++还有一个prev_permutation(),是反向输出全排列,用法是一样的!

Python:permutations()

下面两种方法是输出长度为2的全排列,如果把函数里的2去掉变成permutations(s),那么就是全排列了,只不过不是按大小排序的。

1
2
3
4
5
from itertools import *
s = ['a','b','c']
for element in permutations(s, 2):
a = element[0] + element[1]
print(a)
1
2
3
4
5
from itertools import *
s = ['a','b','c']
for element in permutations(s,2):
a=''.join(element) #把所有元素拼起来
print(a)

如果想让python按全排列结果的大小进行排序,可以先sort排序后进行排列!

Python:combinations()

这个排序不区分AB和BA的区别

1
2
3
4
5
from itertools import *
s = ['1','3','2']
for element in combinations(s,2):
a=''.join(element) #把所有元素拼起来
print(a)