【蓝桥杯软件赛 零基础备赛20周】第8周——排序算法及应用

2024-01-08 14:29:45

在算法竞赛中,一般不需要自己写这些排序算法,而是直接使用库函数,例如C++的sort()函数,Python的sort()和sorted()函数,Java的sort()函数。

1. 快速排序

十大排序算法里,最常考,也是最常用的排序算法,就是快速排序,因此这里只单独讲一个快速排序算法。

很多算法题,不会直接考排序算法,而是考察排序算法中的思想。比如快速排序是怎么分治的,怎么分割的,要会变形,要会举一反三。

快速排序的思路是:把序列分成左右两部分,使得左边所有的数都比右边的数小;递归这个过程,直到不能再分为止。如何把序列分成左右两部分?最简单的办法是设定两个临时空间X、Y和一个基准数t;检查序列中所有的元素,比t小的放在X中,比t大的放在Y中。不过,其实不用这么麻烦,直接在原序列上操作就行了,不需要使用临时空间X、Y。

直接在原序列上进行划分的方法有很多种,下面的图示介绍了一种很容易操作的方法:
在这里插入图片描述

下面分析复杂度。

每一次划分,都把序列分成了左右两部分,在这个过程中,需要比较所有的元素,有O(n)次。如果每次划分是对称的,也就是说左右两部分的长度差不多,那么一共需要划分O(logn)次。总复杂度O(nlogn)。

如果划分不是对称的,左部分和右部分的数量差别很大,那么复杂度会高一些。在极端情况下,例如左部分只有1个数,剩下的全部都在右部分,那么最多可能划分n次,总复杂度是 O ( n 2 ) O(n^2) O(n2)。所以,快速排序的效率和数据本身有关。

不过,一般情况下快速排序效率很高,甚至比归并排序更好。读者可以观察到,下面给出的快速排序的代码比归并排序的代码更简洁,代码中的比较、交换、拷贝操作很少。 快速排序几乎是目前所有排序法中速度最快的方法。STL的sort()函数就是基于快速排序算法的,并针对快速排序的缺点做了很多优化。

(1)C++代码

#include<bits/stdc++.h>
using namespace std;
int a[100005],n;
void qsort(int L,int R){
	int i=L,j=R;
	int key=a[(L+R)/2];
	while(i<=j)	{
		while(a[i]<key)	i++;
		while(a[j]>key) j--;
		if(i<=j){
			swap(a[i],a[j]);
			i++; j--;
		}
	}
	if(j>L) qsort(L,j);
	if(i<R) qsort(i,R);
}
int main(){
    cin>>n;
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	qsort(0,n-1);
	for(int i=0;i<n;i++) printf("%d ",a[i]);
	return 0;
}

(2)Java代码

import java.util.Scanner;
public class Main {
    static int[] a = new int[100005];
    static int n;
    public static void qsort(int L, int R) {
        int i = L, j = R;
        int key = a[(L + R) / 2];
        while (i <= j) {
            while (a[i] < key) i++;
            while (a[j] > key) j--;
            if (i <= j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            }
        }
        if (j > L)   qsort(L, j);
        if (i < R)   qsort(i, R);
    }
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        for (int i = 0; i < n; i++)    a[i] = input.nextInt();
        qsort(0, n - 1);
        for (int i = 0; i < n; i++)    System.out.print(a[i] + " ");
    }
}

(3)Python代码

def qsort(L, R):
    i, j = L, R
    key = a[(L + R) // 2]
    while i <= j:
        while a[i] < key:  i += 1
        while a[j] > key:  j -= 1
        if i <= j:
            a[i], a[j] = a[j], a[i]
            i += 1
            j -= 1
    if j > L:  qsort(L, j)
    if i < R:  qsort(i, R)
n = int(input())
a = list(map(int, input().split()))
qsort(0,n-1)
for i in range(n):  print(a[i], end=" ")

2. 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<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 (){
    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<int>());              //结果:1 2 2 3 4 5 6 8
    sort(a,a+8,my_less); 	              //自定义排序,结果:1 2 2 3 4 5 6 8
    sort(a,a+8,greater<int>());           //从大到小排序,结果:8 6 5 4 3 2 2 1
    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<int>());   //结果:8 7 6 2 3 4 5 5
    if(is_sorted(b,b+3,greater<int>())) cout<<"is sorted"<<endl;  //输出:is sorted

    vector<int> c = {1,2,3,4,5,6,7,8};
    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<char>());  
    cout<<s;                               //输出: wroolllhed    注意最后一个是空格
    return 0;
}

利用cmp()函数,sort()可以对结构体进行排序,见后面的例题。

C++的sort()有两个优点:(1)能在原数组上排序,不需要新的空间;(2)能在数组的局部区间上排序。

3. 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()虽可以对一部分排序,但是不能直接在原数组上排序。

4. 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<Integer> list  = new ArrayList<>();
       list.add(36);
       list.add(52);
       list.add(15);
       Collections.sort(list);
       System.out.print(list);       //输出: [15, 36, 52]  
    }
}

5. 例题

例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<bits/stdc++.h>
using namespace std;
int y[10001];
int main(){
    int n; cin>>n;
    for (int i=0; i<n; 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<n; i++)  ans += abs(m-y[i]);
    cout<<ans;
    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<bits/stdc++.h>
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<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    sort(a,a+n,greater<int>());    //A数组从大到小排序
    sort(b,b+n,greater<int>());    //B数组从大到小排序
    long long cnt=0,ans=1;
    for(int i=0,j=0;i<n;i++) {     //枚举每个B[i]
        while(j<n && a[j]>b[i])    //找所有大于b[i]的数
            cnt++,j++;
        ans *= cnt--;
        ans %= MOD;
    }
    cout<<ans<<endl;
}

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代码
```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<bits/stdc++.h>
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<<a[m]<<endl;
    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<n;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<bits/stdc++.h>
using namespace std;
struct node{ int t,id;};          //定义结构体a
struct node a[1010];              //定义结构体数组
bool cmp(node x,node y) { return x.t<y.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<<a[i].id<<" ";
    cout<<endl;                    //换行
    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<bits/stdc++.h>
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<Integer> banana = new ArrayList<>();  
        for (int i = 0; i < n; i++) banana.add(scanner.nextInt());          
        Collections.sort(banana);    
        ArrayList<Monkey> monkeys = new 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=' ')

6. 习题

统计数字
错误票据
奖学金
外卖店优先级
双向排序
第几个幸运数字
插入排序
排个序
图书管理员
瑞士轮
肖恩的大富翁

文章来源:https://blog.csdn.net/samsara_of_ice/article/details/135452617
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。