报名明年4月蓝桥杯软件赛的同学们，如果你是大一零基础，目前懵懂中，不知该怎么办，可以看看本博客系列：备赛20周合集 20周的完整安排请点击：20周计划 每周发1个博客，共20周（读者可以按自己的进度选“正常”和“快进”两种计划）。 每周3次集中答疑，周三、周五、周日晚上，在QQ群上答疑：
文章目录
1. C++ STL sort()2. Python的sort()和sorted()3. Java的sort()4. 例题例1 排序的基本应用例2 排序的基本应用例3 自定义排序比较函数例4 结构体排序例5 结构体排序
5. 习题
第8周第2讲: 排序的应用 在算法竞赛中，一般不需要自己写这些排序算法，而是直接使用库函数，例如C++的sort()函数，Python的sort()和sorted()函数，Java的sort()函数。
1. C++ STL sort()
有以下排序函数。 sort (first, last, comp) 对[first, last) 范围内的元素进行排序。注意排序的范围[first, last)，包括first，不包括last。comp是比较函数，sort()自带4种comp排序：less、greater、less_equal、greater_equal。缺省情况下，程序是按从小到大的顺序排序的，less可以不写。也可以用自定义的比较函数进行排序，见下面第3、4行的例子。
stable_sort (first, last, comp) 和sort()相似，不同之处在于，对于 [first, last) 范围内值相同的元素，该函数不会改变它们的相对位置。 partial_sort(first, middle, last, , comp) 以交换元素存储位置的方式实现部分排序，将 [first, last) 范围内最小（或最大）的 middle-first 个元素移动到 [first, middle) 区域中，并对这部分元素做升序（或降序）排序。 nth_element(first, nth, last, comp) 采用默认的升序时，该函数从某个序列中找到第 k 小的元素e（序列下标从0开始），并将e移动到序列中第k的位置处。而且，整个序列经过nth_element()函数处理后，所有位于e之前的元素都比e小，所有位于e之后的元素都比e大。 is_sorted (first, last, comp) 检测 [first, last) 范围内是否已经排好序，默认检测是否按升序排序。 下面是例子。
#include
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 (){
int a[]={1,3,2,2,6,8,5,4};
sort(a+2,a+6); //对前4个排序，结果：1 3 2 2 6 8 5 4
sort(a,a+8,less
sort(a,a+8,my_less); //自定义排序，结果：1 2 2 3 4 5 6 8
sort(a,a+8,greater
sort(a,a+8,my_greater); //结果：8 6 5 4 3 2 2 1
stable_sort(a+3,a+8); //结果：8 6 5 1 2 2 3 4
int b[]={3,7,2,5,6,8,5,4};
partial_sort(b,b+3,b+8); //结果：2 3 4 7 6 8 5 5
partial_sort(b,b+3,b+8,greater
if(is_sorted(b,b+3,greater vector sort(c.begin(),c.end(),my_greater); //结果：8 7 6 5 4 3 2 1 string s="hello world"; sort(s.begin(),s.end(),greater cout< return 0; } 利用cmp()函数，sort()可以对结构体进行排序，见后面的例题。 C++的sort()有两个优点：（1）能在原数组上排序，不需要新的空间；（2）能在数组的局部区间上排序。 2. Python的sort()和sorted() Python提供了两个排序函数，sort()和sorted()。 1、sort和sorted()的区别 sort()是应用在list上的方法，而sorted 可以对所有可迭代的对象进行排序操作。 一个关键的区别是：sort是在原列表上排序，而sorted()产生一个新的列表，不改变原列表。 2、sorted() sorted(iterable, key=None, reverse=False) 参数说明： iterable：可迭代对象。 key：用来进行比较的元素，只有一个参数，具体的函数的参数取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。 reverse：排序规则，reverse = True 降序，reverse = False 升序（默认）。 返回值：重新排序的列表。 3、sort()和sorted()的例子 a = [3,7,9,3,4,1,2] a.sort() #直接在a上升序排序，a改变了 print(a) #[1, 2, 3, 3, 4, 7, 9] b = sorted(a,reverse = True) print(b) #排序结果给b，输出：[9, 7, 4, 3, 3, 2, 1] print(a) #a不变，输出：[1, 2, 3, 3, 4, 7, 9] a.sort(reverse = True) #降序 print(a) #输出：[9, 7, 4, 3, 3, 2, 1] a = "abadae" print(sorted(a)) #输出：['a', 'a', 'a', 'b', '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)] s = "hello world" s = ''.join(sorted(s, reverse=True)) #Python中字符串不可变，不能直接在原字符串上进行排序 #可以将字符串转换为列表进行排序，然后再转回字符串 print(s) #输出：wroolllhed 注意最后一个是空格 Python的sort()不能在数组的一部分上做排序，只能对整个数组排序；sorted()虽可以对一部分排序，但是不能直接在原数组上排序。 3. Java的sort() 有Arrays.Sort()、Collections.sort()。 Arrays.sort()可以对数组，字符串等排序。Collections.sort()是对list集合排序，list也可以放数字、字符串。自定义比较见后面的例题。 例子： import java.util.*; public class Main { public static void main(String[] args) { int[] a = {8, 3, 6, 2, 3, 5, 9}; Arrays.sort(a); //升序 for (int num : a) System.out.print(num+" "); //输出： 2 3 3 5 6 8 9 System.out.println(); Integer[] b = {2, 3, 4, 1, 0, 6, 5}; Arrays.sort(b,Collections.reverseOrder()); //降序 //不支持基本类型int，double，char，如果是int型需要改成Integer，float要改成Float for (int num : b) System.out.print(num+" "); //输出： 6 5 4 3 2 1 0 System.out.println(); String s = "hello world"; char[] chars = s.toCharArray(); Arrays.sort(chars); s = new String(chars); //Java中字符串是不可变的，因此不能直接在原字符串上进行排序。可以将字符串转换为字符数组进行排序，然后再将排序后的字符数组转换回字符串。 System.out.println(s); //输出： dehllloorw ArrayList list.add(36); list.add(52); list.add(15); Collections.sort(list); System.out.print(list); //输出： [15, 36, 52] } } 4. 例题 例1 排序的基本应用 输油管道问题 已知n个油井的y坐标，把它们排个序， y 0 ≤ y 1 ≤ . . . ≤ y n − 1 y_0≤y_1≤...≤y_{n-1} y0≤y1≤...≤yn−1。 设主管道的y坐标是m，那么就是求 ∣ y 0 − m ∣ + ∣ y 1 − m ∣ + . . . + ∣ y n − 1 − m ∣ |y_0-m|+|y_1-m|+...+|y_{n-1}-m| ∣y0−m∣+∣y1−m∣+...+∣yn−1−m∣的最小值。 m肯定大于 y 0 y_0 y0小于 y n − 1 y_{n-1} yn−1，猜测是平均值，或者中位数。容易证明是中位数，例如n=7，m是 y 3 y_3 y3；n=8，m是 y 3 y_3 y3或 y 4 y_4 y4。 C++代码 #include using namespace std; int y[10001]; int main(){ int n; cin>>n; for (int i=0; i int x; cin>>x>>y[i]; //忽略x坐标 } sort(y,y+n); //对n个y值排序 int m = y[n/2]; //m是中位数 int ans = 0; for (int i=0; i cout< return 0; } Java代码 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] y = new int[n]; for (int i = 0; i < n; i++) { int x = sc.nextInt(); y[i] = sc.nextInt(); } Arrays.sort(y); int m = y[n/2]; int ans = 0; for (int i = 0; i < n; i++) ans += Math.abs(m - y[i]); System.out.println(ans); } } Python代码 n = int(input()) y = [] for i in range(n): x, yi = map(int, input().split()) y.append(yi) y.sort() m = y[n//2] ans = 0 for i in range(n): ans += abs(m - y[i]) print(ans) 例2 排序的基本应用 肖恩的排序 先考虑简单直接的做法。题目要求“所有位置i都有A[i] > B[i]”，先对A从小到大排序，然后枚举B数组，对某个B[i]，若有个A[j]>B[i]，那么A[j]~A[n-1]都合法。找到所有这种排列，就是答案。但是这样做计算量极大。 题目只要求A[i]>B[i]，那么A[]和B[]内部的顺序对答案没有影响。对于位置i，A[i]可以是A[]中所有大于B[i]的元素。所以对A[]和B[]排序方便计算。 先从大到小对A[]和B[]排序，然后枚举B[]数组，步骤如下： B[0]对应的A[]的元素，是大于B[0]的所有A[]的元素，设范围是A[i]~A[j]。 B[1]对应的A[]的元素，包括了两部分：第一部分是A[i]~A[j]，因为B[1] ≤ B[0]；第二部分是A[j]之后大于B[1]的那些A[]的元素。第一部分可以利用上一步的结果。另外，因为当前位置要选一个A[]，所以符合条件的数减一。 继续枚举其他B[]的元素，直到结束。 把每次符合要求的A[]的元素个数乘起来，就是答案。 C++代码。分析计算复杂度，第9行和第10行的sort()是O(nlogn)的，第12行和第13行合起来是O(n2)，总复杂度O(n2)。 #include using namespace std; const int N=1e5+10,MOD=1e9+7; int a[N],b[N]; int main() { long long n=0; cin>>n; for(int i=0;i for(int i=0;i sort(a,a+n,greater sort(b,b+n,greater long long cnt=0,ans=1; for(int i=0,j=0;i while(j cnt++,j++; ans *= cnt--; ans %= MOD; } cout< } Java代码 import java.util.Arrays; import java.util.Scanner; public class Main { static final int N = 100010; static final int MOD = 1000000007; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] a = new int[N]; int[] b = new int[N]; for (int i = 0; i < n; i++) a[i] = scan.nextInt(); for (int i = 0; i < n; i++) b[i] = scan.nextInt(); Arrays.sort(a, 0, n); //从小到大排序 for (int i = 0; i < n/2; i++) {int tmp=a[i]; a[i]=a[n-1-i];a[n-1-i]=tmp;} //从大到小 Arrays.sort(b, 0, n); //从小到大排序 for (int i = 0; i < n/2; i++) {int tmp=b[i]; b[i]=b[n-1-i];b[n-1-i]=tmp;} //从大到小 long cnt = 0, ans = 1; int j = 0; for (int i = 0; i < n; i++) { while (j < n && a[j] > b[i]) { cnt++; j++; } ans *= cnt; cnt--; ans %= MOD; } System.out.println(ans); } } Python代码 n = int(input()) a = list(map(int, input().split())) b = list(map(int, input().split())) a.sort(reverse=True) b.sort(reverse=True) cnt, ans = 0, 1 j = 0 for i in range(n): while j < n and a[j] > b[i]: cnt += 1 j +=1 ans *= cnt cnt -= 1 ans %= int(1e9+7) print(ans) 例3 自定义排序比较函数 用这一题熟悉sort()中的自定义比较函数。 数位排序 C++代码。本题看似不好做，实际上可以利用sort (first, last, comp)中的自定义比较函数comp，简单地实现。 #include using namespace std; const int N = 1e6 + 10; int a[N], b[N]; int sum(int x){ //计算x的数位和 int ans = 0; while(x) ans += x % 10, x /= 10; return ans; } bool cmp(int x, int y){ //自定义比较，数位和小的在前面 if(b[x] == b[y]) return x < y; return b[x] < b[y]; } int main(){ int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { a[i] = i; b[i] = sum(i); } sort(a + 1, a + 1 + n, cmp); cout< return 0; } java代码。注意Arrays.sort()如何自定义比较。 import java.util.*; public class Main { public static int sum(int num) { int ans = 0; while(num>0) { ans+=num%10; num/=10; } return ans; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int [][]a = new int[n][2]; for (int i=0;i a[i][0] = sum(i+1); a[i][1] = i+1; } Arrays.sort(a,(v1,v2)->{ if (v1[0]!=v2[0]) return v1[0]-v2[0]; return v1[1]-v2[1]; }); System.out.println(a[m-1][1]); } } Python代码。用lambda自定义比较。 def sum(x): # 计算每一个数的数位和 ans = 0 while x: ans += x % 10 x //= 10 return ans n=int(input()) m=int(input()) a=list(range(1,n+1)) #赋值a[0]~a[n]，注意rang(1,n+1)最后一个是a[n] a.sort(key=lambda i:sum(i)) print(a[m-1]) 例4 结构体排序 排队接水 用这一题熟悉结构体排序 C++代码 #include using namespace std; struct node{ int t,id;}; //定义结构体a struct node a[1010]; //定义结构体数组 bool cmp(node x,node y) { return x.t int main(){ int n; cin>>n; for(int i=1; i<=n; i++){ cin>>a[i].t; a[i].id=i; //序号存起来 } sort(a+1,a+n+1,cmp); //排序 for(int i=1; i<=n; i++) //输出 cout< cout< double time=0; //总时间 for(int j=n-1; j>=1; j--) { //等待人数，由n-1开始 int i=n-j; //当前最少时间的人序号 + 要等待的人数=n time += a[i].t*j; //累加 } printf("%.2lf",time/n); //算平均时间，保留两位小数 return 0; } Java代码 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); double time=0; node[] a=new node[n+10]; for (int i = 1; i <=n ; i++) a[i]=new node(i,sc.nextInt()); Arrays.sort(a,1,n+1,(x,y)->(x.t-y.t)); for (int i = 1; i <=n ; i++) System.out.print(a[i].id+" "); for (int i = 1; i <=n; i++) time+=a[i].t*(n-i); System.out.println(); System.out.printf("%.2f",time/n); } } class node{ int id; int t; public node(int id, int t) { this.id = id; this.t = t; } } Python代码 n = int(input()) t = list(map(int, input().split())) a = [(id, e) for id, e in enumerate(t)] a.sort(key=lambda x:x[1]) print(' '.join([str(i + 1) for i, e in a])) time = [0] * n tmp = 0 for i, (j, e) in enumerate(a): time[i] = tmp tmp += e print('{:.2f}'.format(sum(time) / len(time))) 例5 结构体排序 分香蕉 这是一道有点啰嗦的排序题，需要做多次排序：（1）香蕉按质量排序；（2）猴子按分配到的香蕉排序；（3）猴子按编号排序。最好用结构体排序。 C++代码 #include using namespace std; const int N=1e5+5; int banana[N],part[N]; //香蕉、分成m份 struct Monkey{ int w,id,y; //猴子的重量、编号、吃到的香蕉 }mon[N]; bool com1(Monkey a, Monkey b){ return a.w > b.w;} //比较重量 bool com2(Monkey a, Monkey b){ return a.id < b.id;} //比较编号 int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin >> banana[i]; sort(banana+1,banana+1+n); //香蕉排序 for(int i=1;i<=m;i++) { cin >> mon[i].w; mon[i].id=i; } sort(mon+1,mon+1+m,com1); //猴子按重量排序 for(int i=1;i<=n;i++) part[i%m] += banana[n-i+1]; //把香蕉分成m份 for(int i=1;i<=m;i++) mon[i].y = part[i%m]; //分给m个猴子 sort(mon+1,mon+1+m,com2); //按编号排序，也就是回到初始排序 for(int i=1;i<=m;i++) cout<< mon[i].y <<" "; return 0; } Java代码 import java.util.*; public class Main { static class Monkey { int w, id, y; //猴子的重量、编号、吃到的香蕉 public Monkey(int w, int id, int y) { this.w = w; this.id = id; this.y = y; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); ArrayList for (int i = 0; i < n; i++) banana.add(scanner.nextInt()); Collections.sort(banana); ArrayList for (int i = 0; i < m; i++) monkeys.add(new Monkey(scanner.nextInt(), i + 1, 0)); Collections.sort(monkeys, (a, b) -> b.w - a.w); //猴子按重量排序 int[] part = new int[m]; for (int i = 0; i < n; i++) part[i % m] += banana.get(n - i - 1); //把香蕉分成m份 for (int i = 0; i < m; i++) monkeys.get(i).y = part[i % m]; //分给m个猴子 Collections.sort(monkeys, (a, b) -> a.id - b.id); //按编号排序，回到初始排序 for (int i = 0; i < m; i++) System.out.print(monkeys.get(i).y + " "); //输出每个猴子的香蕉数量 } } Python代码 n,m=map(int,input().split()) banana=list(map(int,input().split())) #香蕉质量 banana.sort(reverse=True) #香蕉排序 monkey=list(map(int,input().split())) #猴子重量 id=[i for i in range(1,m+1)] #猴子编号 part=[0 for i in range(1,m+1)] weight=list(zip(id,monkey,part)) weight=map(list,weight) weight=sorted(weight,key=lambda x:x[1],reverse=True) #猴子按重量排序 for i in range(len(banana)): #把香蕉分成m份 weight[i%m][2] += banana[i] weight.sort() #猴子按编号排序 for i in range(len(monkey)): print(weight[i][2],end=' ') 5. 习题 统计数字 错误票据 奖学金 外卖店优先级 双向排序 第几个幸运数字 插入排序 排个序 图书管理员 瑞士轮 肖恩的大富翁 精彩链接
您阅读本篇文章共花了：
发表评论