PTA 7-12 排序

题目描述

给定 n 个（长整型范围内的）整数，要求输出从小到大排序后的结果。

本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据1：只有1个元素；
• 数据2：11个不相同的整数，测试基本正确性；
• 数据3：103个随机整数；
• 数据4：104个随机整数；
• 数据5：105个随机整数；
• 数据6：105个顺序整数；
• 数据7：105个逆序整数；
• 数据8：105个基本有序的整数；
• 数据9：105个随机正整数，每个数字不超过1000。

  输入格式:

  输入第一行给出正整数 n（≤105），随后一行给出 n 个（长整型范围内的）整数，其间以空格分隔。

  输出格式:

  在一行中输出从小到大排序后的结果，数字间以 1 个空格分隔，行末不得有多余空格。

  输入样例:

  11
  4 981 10 -17 0 -20 29 50 8 43 -5
  

  输出样例:

  -20 -17 -5 0 4 8 10 29 43 50 981

题目分析 

题目是说给n个长整型范围内的整数，然后输出从小到大排序后的结果。看起来这个题目的测试数据有不同的情况，包括不同的数据量和不同特点的数据，比如有序、逆序、重复等等。所以我要选择一个高效的排序算法来处理这些情况。

首先，考虑时间复杂度。因为n可以达到1e5，也就是十万级别。这时候像冒泡排序、插入排序这样的O(n²)算法肯定是不行的，时间会超限。那应该选择更高效的算法，比如快速排序、归并排序或者堆排序，这些的平均时间复杂度是O(n log n)。或者还可以用C++标准库里的sort函数，这个函数通常是经过高度优化的，应该能处理各种情况。

然后，题目里的各种测试数据需要注意。比如数据6是顺序的，数据7是逆序的，数据8是基本有序的。这时候如果使用普通的快速排序，在已经有序的情况下可能会退化成O(n²)的时间复杂度。所以在这种情况下，可能需要选择一种优化的快速排序，比如三数取中或者随机化选择枢轴，或者改用归并排序。不过C++的sort函数在实现时应该已经考虑到了这些情况，比如使用introsort，结合了快速排序和堆排序，来避免最坏情况。所以可能直接使用sort函数是可行的。

那这样的话，用C++的sort函数应该可以应对所有的测试点。接下来需要处理输入输出的问题。

输入的时候，n的值可能很大，比如1e5，这时候如果用cin读取的话可能会比较慢，尤其是当输入量大的时候。为了提高输入效率，可以考虑使用更快的输入方法，比如用scanf或者用ios::sync_with_stdio(false)来关闭同步，加速cin的读取速度。

另外，输入的整数可能有负数，所以读取的时候需要注意处理符号。输出的时候要确保行末没有多余的空格，所以可能需要先输出第一个元素，然后后面的元素前面加空格。

那具体来说，步骤如下：

1. 读取n的值。

2. 读取n个整数，存储到一个数组中。

3. 对这个数组进行排序。

4. 输出排序后的结果，每个数之间用空格分隔，行末不能有空格。

关于输入的方法，例如：

当n是1e5的时候，用cin可能会比较慢，特别是当默认情况下C++的cin和stdio是同步的。所以可以取消同步，加快速度。通常的做法是在main函数开头添加：

ios::sync_with_stdio(false);

cin.tie(nullptr);

这样可以提高cin的读取速度。不过需要注意的是，一旦这样做了，就不能再混用C的输入函数如scanf等，否则会出现问题。

然后，读取数组的时候，可以用vector<int>来存储，或者用动态数组。例如：

vector<long long> arr(n);

for (int i=0; i<n; i++) {

cin >> arr[i];

}

或者用数组的话，可能更高效，但vector更方便，特别是当n很大的时候，动态分配内存可能更灵活。

然后排序的时候直接调用sort函数：

sort(arr.begin(), arr.end());

然后输出的时候需要注意格式。比如第一个元素单独输出，后面的元素前面加一个空格。或者遍历数组，每个元素后面加空格，但最后一个元素不加。例如：

for (int i=0; i<n; i++) {

if (i>0) cout << " ";

cout << arr[i];

}

cout << endl;

这样处理的话，无论n是0还是其他情况都不会有问题。不过题目中n>=1吗？看题目描述，输入样例中的n是11，所以可能n>=1。所以不需要处理n为0的情况。

接下来，要考虑数据范围的问题。题目中的整数是长整型范围内，所以应该用long long类型存储，而不是int。因为比如输入可能有超过int范围的数值。例如，在C++中，int的范围通常是-2^31到2^31-1，而long long的范围更大。所以必须使用long long类型。

所以，数组应该定义为vector<long long>。

那综合以上分析，代码的大体结构应该是：

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

int n;

cin >> n;

vector<long long> arr(n);

for (int i=0; i<n; i++) {

cin >> arr[i];

}

sort(arr.begin(), arr.end());

for (int i=0; i<n; i++) {

if (i != 0) {

cout << " ";

}

cout << arr[i];

}

cout << endl;

return 0;

}

这样应该就可以解决问题了。但需要考虑特殊情况，比如当n=0的时候怎么办？不过题目里给出的输入样例中的n是11，而且题目中输入的n是正整数，所以n>=1。所以代码中不需要处理n=0的情况。

另外，关于数据量较大的测试点，比如数据5到数据9都是1e5个元素，这时候输入输出的效率就变得非常重要。使用上述的优化方法应该可以满足时间要求。比如，关闭同步后的cin比默认情况下更快，而用vector存储数据不会有问题，sort的时间复杂度是O(n log n)，对于1e5来说，这个时间应该在允许范围内。

总结，这道题的正确做法是使用快速输入输出优化，读取所有数据到vector中，然后调用标准库的sort函数进行排序，然后按格式输出。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>  // 包含sort函数using namespace std;int main() {// 关闭同步，加速输入输出ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<long long> arr(n);  // 存储长整型数据for (int i = 0; i < n; ++i) {cin >> arr[i];}// 使用标准库的sort函数进行排序，默认升序sort(arr.begin(), arr.end());// 输出结果，控制格式for (int i = 0; i < n; ++i) {if (i != 0) {cout << " ";}cout << arr[i];}cout << endl;return 0;
}

代码解释

1. 输入输出优化：

   • ios::sync_with_stdio(false); 和 cin.tie(nullptr); 用于关闭C++标准流与C标准流的同步，加快输入输出速度。

2. 读取输入：

   • 使用vector<long long>存储输入的整数，确保能够处理长整型范围内的数值。

   • 循环读取n个整数到数组中。

3. 排序处理：

   • 使用sort(arr.begin(), arr.end());对数组进行升序排序。该函数在C++标准库中实现高效，适用于各种数据分布。

4. 输出结果：

   • 遍历排序后的数组，按格式输出每个元素。第一个元素直接输出，后续每个元素前添加一个空格，确保行末无多余空格。