pta7-4 一维数组排序

Question

7-4 一维数组排序
分数 18
作者 陈宇璟
单位 浙江大学
对数组的元素按从小到大进行排序。

输入格式:
第一行有一个整数n (<10)；

第二行n有元素,在10^19范围内。

输出格式:
输出排序后的数组。

输入样例:
在这里给出一组输入。例如：

8
1 2 3 6 8 7 4 5
输出样例:
在这里给出相应的输出。例如：

1 2 3 4 5 6 7 8
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制

Answer 1

引自GPT4o回答
以下是一个使用 C 语言编写的程序，用于对一维数组进行排序。该程序首先读取数组的大小和元素，然后使用简单的排序算法（如泡排序）对数组进行排序，最后输出排序后的数组。

C 语言代码示例

#include <stdio.h>

int main() {
    int n;
    
    // 输入数组的大小
    scanf("%d", &n);
    
    // 定义数组并输入元素
    long long arr[n]; // 使用 long long 以支持最大范围 10^19
    
    for (int i = 0; i < n; i++) {
        scanf("%lld", &arr[i]);
    }
    
    // 冒泡排序
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 和 arr[j + 1]
                long long temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    
    // 输出排序后的数组
    for (int i = 0; i < n; i++) {
        printf("%lld", arr[i]);
    }
    printf("\n");
    
    return 0;
}

代码解释

1. 输入部分：

   • 首先，程序读取一个整数 n，表示数组的大小。
   • 然后，程序定义一个 long long 类型的数组 arr，以支持较大的整数（最大可达 (10^{19})）。
   • 使用循环读取 n 个元素。

2. 排序部分：

   • 使用冒泡排序算法对数组进行排序。嵌套循环比较相邻的元素，如果前一个元素大于后一个元素，则交换它们。

3. 输出部分：

   • 最后，程序输出排序后的数组元素，所有元素在同一行输出。

使用示例

如果输入如下：

8
12368745

程序输出将为：

12345678

注意事项

• 确保在编译和运行代码时，使用支持 long long 类型的编译器。
• 冒泡排序的时间复杂度为 (O(n^2))，在 (n < 10) 的情况下，这个算法是可以接受的。对于更大的数据集，可以考虑使用更高效的排序算法，如快速排序或归并排序。