Java 數組與經典算法實戰：線性查找、二分查找、冒泡/選擇/插入排序完整代碼

Java 數組與經典算法實戰

數組是算法實現的基礎容器。本文提供五大經典算法的標準 Java 實現：線性查找、二分查找、冒泡排序、選擇排序、插入排序，附帶時間複雜度分析、適用場景與代碼註釋。

一、線性查找

原理：從頭到尾逐個比對，找到返回索引，否則 -1。複雜度：O(n)。適用：無序數組、小數據量。

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

延伸：求最大/最小值同理，單次遍歷記錄極值索引。

二、二分查找

前提：數組**已升序排序**。原理：取中間元素比較，縮小搜索區間至一半。複雜度：O(log n)。

public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

三、冒泡排序

原理：相鄰比較，大者後移，每輪將最大元素「冒泡」到末尾。複雜度：O(n²)，穩定。優化：若某輪無交換則提前結束。

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

四、選擇排序

原理：每輪在未排序區間找最小元素，換到已排序區間末尾。複雜度：O(n²)，不穩定。特點：交換次數最少（最多 n-1 次）。

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        if (minIdx != i) {
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
}

五、插入排序

原理：構建有序區間，將未排序元素依次插入有序區間合適位置（後移元素騰位）。複雜度：O(n²)，穩定。優勢：近乎有序數組接近 O(n)，適合小規模/部分有序數據。

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

六、算法選型速查表

七、生產環境建議

• 實際開發直接使用 Arrays.sort()（雙軸快排/歸併混合，O(n log n)）或 Collections.sort()。
• 海量數據外部排序、TopK 問題可用堆/歸併/桶排序。
• 並行排序：Arrays.parallelSort()（JDK 8+）利用多核加速。