本文共 1780 字，大约阅读时间需要 5 分钟。

【深基9.例1】选举学生会

输入输出描述

输入格式：无

输出格式：无

输入输出样例

输入 #1

5 10

2 5 2 2 5 2 2 2 1 2

输出 #1

1 2 2 2 2 2 2 2 5 5

解题思路

对此问题，快速排序和计数排序是两个常用的解决方案。我们需要根据数据规模和性能要求选择合适的算法。

选算法方法

在处理这类排序问题时，选择合适的算法至关重要。以下是两种主要算法的分析：

1. 快速排序：

• 时间复杂度：O(m log m)
• 空间复杂度：O(1)
• 特点：适合大部分数据集，其中大多数数据分布较均匀。

2. 计数排序：

• 时间复杂度：O(m + n)
• 空间复杂度：O(n)
• 特点：当数据范围较小时，效率非常高。

由于题目中n的上限是999（较小），而m的数据规模较大（至2,000,000），计数排序在小范围内非常高效。而快速排序可以在较大数据规模下表现更好。

Java 实现

代码示例

import java.util.Arrays;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        int m = scanner.nextInt();        int[] votes = new int[m];        for (int i = 0; i < m; i++) {            votes[i] = scanner.nextInt();        }        Arrays.sort(votes);        for (int vote : votes) {            System.out.print(vote + " ");        }    }}

说明：使用Java的内置排序方法Arrays.sort()，直接将选票数据按升序排列。这在处理、排序和输出时都非常高效。

C++快速排序实现

代码示例

#include 
   
    #include 
    
     using namespace std;int main() {    int n, m;    cin >> n >> m;    int a[m];    for (int i = 0; i < m; i++) {        cin >> a[i];    }    sort(a, a + m);    for (int i = 0; i < m; i++) {        cout << a[i] << " ";    }}
    
   

说明：使用C++的标准库快速排序函数sort()，同样能高效解决该问题。该方法的时间复杂度为O(m log m)，适用于较大的m值。

C++计数排序实现

代码示例

#include 
   
    using namespace std;#define ll long longint main() {    int n, m;    cin >> n >> m;    ll b[n + 1] = {0};    for (int i = 1; i <= n; ++i) {        int k;        cin >> k;        b[k]++;    }    for (int i = 1; i <= m; ++i) {        while (b[i] > 0) {            cout << i << " ";            b[i]--;        }    }    return 0;}
   

说明：这种方法通过创建频率数组统计候选人票数。之后按顺序输出每个候选人的票数，直到所有选票都被处理。这种做法在n较小时表现非常优异。

总结

根据问题规模和具体需求，我们选择合适的算法是关键。对于n较小的情况，计数排序是高效且占据较少内存的选择；而对于大部分数据集，快速排序是更通用的解决方案。仔细分析数据规模和性能需求，是开发选择算法的关键所在。

转载地址：http://pdtzz.baihongyu.com/