Java有序陣列插入元素並保持排序完整實現

給定一個已排序的整數陣列，插入新元素並維持升序。本文示範標準插入排序邏輯：尋找插入位置、後移元素、放入新值。

核心演算法步驟

1. 判斷新值是否大於最後一個元素，若是則直接置於末尾
2. 從頭遍歷，找到第一個大於新值的位置 `k`
3. 將 `k` 及其後所有元素向後移動一格
4. 在 `k` 處放入新值

完整程式碼（含測試流程）

import java.util.Random;

public class SortedArrayInsert {
    public static void main(String[] args) {
        int[] arr = new int[12]; // 保留一個空位供插入
        Random r = new Random();
        // 產生 10 個隨機數並排序
        for (int i = 1; i <= 10; i++) arr[i] = r.nextInt(1000);
        // 簡易氣泡排序（教學用）
        for (int i = 1; i <= 9; i++)
            for (int k = i + 1; k <= 10; k++)
                if (arr[i] > arr[k]) { int t=arr[i]; arr[i]=arr[k]; arr[k]=t; }
        System.out.println("排序後："); printArr(arr, 10);

        // 插入新隨機數
        arr[11] = r.nextInt(1000);
        int val = arr[11];
        int k = 1;
        while (k <= 10 && arr[k] <= val) k++; // 找到插入位置
        // 後移
        for (int j = 11; j >= k+1; j--) arr[j] = arr[j-1];
        arr[k] = val;
        System.out.println("插入後："); printArr(arr, 11);
    }
    static void printArr(int[] a, int len) {
        for (int i = 1; i <= len; i++) System.out.print(a[i] + ",");
        System.out.println();
    }
}

效能與改進

• 時間複雜度 O(n)，空間 O(1)
• 生產環境建議使用 `Arrays.binarySearch` 定位 + `System.arraycopy` 移動，或直接改用 `ArrayList` / `TreeSet`
• 陣列下標從 1 起碼為教學示意，實務請從 0 開始