1118: 数列有序
时间限制: 1 Sec 内存限制: 128 MB
提交: 19364 解决: 8702
[状态] [讨论版] [提交] [命题人:admin]
题目描述
一个非递减有序的整型数组有n个元素，给定一个整数num，将num插入该序列的适当位置，使序列仍保持非递减有序。
要求定义一个函数insert()，将整数num插入在数组a的适当位置上，函数原型如下：
int insert(int a[], int n, int num);
另外函数仍然调用以前定义过的函数PrintArr()输出数组所有元素。
输入
输入有三行。第一行是一个正整数n，n<=1000。第二行是n个整数，第三行是待插入整数num。
输出
输出非递减有序的n+1个整数，数据之间用空格隔开。输出占一行。
样例输入 Copy
5
1 2 4 5 6
3
样例输出 Copy
1 2 3 4 5 6
提示
元素之间有空格，最后一个元素后面没有空格。

import java.util.Scanner;
 
// 插入元素
public class Main {
 
    public static void main(String[] args) {
        // 创建Scanner对象input
        Scanner input = new Scanner(System.in);
        // 输入n
        int n = input.nextInt();
        // 创建数组a
        int [] a = new int[n + 1];
         
        for(int i = 0; i < n; i++) {
            // 输入n个整数，存储在数组a中
            a[i] = input.nextInt();
        }
         
        // 输入待插入整数num
        int num = input.nextInt();
         
        // 调用方法insert插入元素
        insert(a, n, num);
        // 调用方法PrintArr输出数组元素
        PrintArr(a, n);
 
    }
     
     
    // 方法将整数num插入在数组a的适当位置上
    public static void insert(int [] a, int n, int num) {
        for(int i = n - 1; i >= 0; i--) {
            if(num < a[i]) {
                // 后移一位
                a[i + 1] = a[i];
                if(i == 0) {
                    a[i] = num;
                }
            }
            else {
                a[i + 1] = num;
                break;
            }
        }
    }
     
     
    // 方法输出数组元素
    public static void PrintArr(int [] a, int n) {
        for(int i = 0; i < n + 1; i++) {
            System.out.printf("%d ", a[i]);
        }
    }
 
}