排序并插入新元素

题目

对 10 个数进行排序。

扩展要求：生成 10 个随机数进行排序，然后输入一个新整数，将其插入数组后重新排序并输出。

说明

本题基础要求是对 10 个数进行排序，常见的排序算法包括冒泡排序、选择排序、插入排序等。题目提示使用选择排序法：

第 1 轮：从全部 10 个数中找出最小值，与第 1 个位置交换；
第 2 轮：从后 9 个数中找出最小值，与第 2 个位置交换；
依此类推，共进行 9 轮即可完成排序。

运行示例

45	67	23	89	12	34	78	56	91	2	
Please Input a int number:50
2	12	23	34	45	50	56	67	78	89	91

👈点击左箭头查看答案（一定要在自己思考并实现后再看参考答案哦！）

规律分析

选择排序核心思想：每一轮确定一个最值（最小或最大）的位置；
时间复杂度为 $O(n^2)$ ，空间复杂度 $O(1)$ ，属于不稳定排序；
而 Arrays.sort() 对基本类型使用双轴快速排序，平均时间复杂度为 $O(n \log n)$ ，性能更优；
插入新元素后再排序，等价于将新元素“合并”进已排序数组——更高效的做法是使用插入排序思想：在有序数组中找到合适位置插入，避免全量重排（时间复杂度可降至 $O(n)$ ）。

程序实现

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class Demo {
    public static void main(String[] args) {
        int arr[] = new int[11]; // 预留11个位置（10个随机 + 1个输入）
        Random r = new Random();
        
        // 生成10个1~100的随机整数
        for (int i = 0; i < 10; i++) {
            arr[i] = r.nextInt(100) + 1;
        }
        
        // 对前10个数排序
        Arrays.sort(arr, 0, 10); // 更严谨：仅排序前10个
        
        // 输出初始排序结果
        for (int i = 0; i < 10; i++) {
            System.out.print(arr[i] + "\t");
        }
        
        // 输入新数字
        System.out.print("\nPlease Input a int number: ");
        Scanner in = new Scanner(System.in);
        arr[10] = in.nextInt();
        
        // 对全部11个数重新排序
        Arrays.sort(arr);
        
        // 输出最终结果
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}

源本科技 | 码上会

题目

说明

运行示例

规律分析

程序实现