数组的常见操作（排序、查找）

数组排序和查找是最常用的操作。

Arrays工具类

Arrays.sort排序

import java.util.Arrays;

int[] arr = {5, 2, 8, 1, 9};

// 默认升序排序
Arrays.sort(arr);
// arr变为：{1, 2, 5, 8, 9}

// 排序部分元素
int[] arr2 = {5, 2, 8, 1, 9};
Arrays.sort(arr2, 1, 4);  // 只排序索引1-3
// arr2变为：{5, 1, 2, 8, 9}

Arrays.binarySearch二分查找

int[] arr = {1, 2, 5, 8, 9};

// 二分查找（数组必须已排序）
int index = Arrays.binarySearch(arr, 5);  // 2（找到，返回索引）
int index2 = Arrays.binarySearch(arr, 3);  // -2（未找到，返回负数）

Arrays.fill填充

int[] arr = new int[5];

// 全部填充为10
Arrays.fill(arr, 10);
// arr: {10, 10, 10, 10, 10}

// 填充部分
int[] arr2 = new int[5];
Arrays.fill(arr2, 1, 3, 5);  // 索引1-2填充为5
// arr2: {0, 5, 5, 0, 0}

Arrays.copyOf复制

int[] arr = {1, 2, 3, 4, 5};

// 复制数组
int[] copy = Arrays.copyOf(arr, 3);  // 复制前3个
// copy: {1, 2, 3}

int[] copy2 = Arrays.copyOf(arr, 10);  // 扩展长度
// copy2: {1, 2, 3, 4, 5, 0, 0, 0, 0, 0}

// 指定范围复制
int[] copy3 = Arrays.copyOfRange(arr, 1, 4);  // 索引1-3
// copy3: {2, 3, 4}

Arrays.equals比较

int[] arr1 = {1, 2, 3};
int[] arr2 = {1, 2, 3};
int[] arr3 = {1, 2, 4};

// 比较数组内容是否相同
boolean same = Arrays.equals(arr1, arr2);  // true
boolean same2 = Arrays.equals(arr1, arr3);  // false

冒泡排序

冒泡排序原理

相邻元素比较，大的后移，每轮确定一个最大值。

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int[] arr = {5, 2, 8, 1, 9};
bubbleSort(arr);
// arr: {1, 2, 5, 8, 9}

冒泡排序优化

public static void bubbleSortOptimized(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 temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;  // 无交换，已排序完成
    }
}

冒泡排序过程示例

原始: {5, 2, 8, 1, 9}

第1轮: {2, 5, 1, 8, 9}  9已确定
第2轮: {2, 1, 5, 8, 9}  8已确定
第3轮: {1, 2, 5, 8, 9}  5已确定
第4轮: {1, 2, 5, 8, 9}  完成

选择排序

选择排序原理

每轮找到最小元素放到当前位置。

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;  // 当前最小索引
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int[] arr = {5, 2, 8, 1, 9};
selectionSort(arr);
// arr: {1, 2, 5, 8, 9}

线性查找

线性查找（顺序查找）

逐个遍历查找目标元素。

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;  // 找到返回索引
        }
    }
    return -1;  // 未找到返回-1
}

int[] arr = {5, 2, 8, 1, 9};
int index = linearSearch(arr, 8);  // 2
int index2 = linearSearch(arr, 3);  // -1

线性查找特点

• 不需要数组有序
• 时间复杂度O(n)
• 适合小数组或无序数组

二分查找

二分查找原理

有序数组中，每次比较中间元素，缩小查找范围。

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] == target) {
            return mid;  // 找到
        } else if (arr[mid] < target) {
            left = mid + 1;  // 目标在右边
        } else {
            right = mid - 1;  // 目标在左边
        }
    }
    
    return -1;  // 未找到
}

int[] arr = {1, 2, 5, 8, 9};  // 必须有序
int index = binarySearch(arr, 5);  // 2
int index2 = binarySearch(arr, 3);  // -1

二分查找过程示例

数组: {1, 2, 5, 8, 9}
查找: 5

第1次: mid=2(元素5) → 找到!
返回索引2

数组: {1, 2, 5, 8, 9}
查找: 3

第1次: mid=2(元素5) > 3 → right=1
第2次: mid=0(元素1) < 3 → left=1
第3次: mid=1(元素2) < 3 → left=2
left > right → 未找到，返回-1

二分查找特点

• 数组必须有序
• 时间复杂度O(log n)
• 适合大数组有序查找

查找方法对比

线性查找 vs 二分查找

// 线性查找：适合无序数组
int[] unsorted = {5, 2, 8, 1, 9};
int index = linearSearch(unsorted, 8);  // 无需排序

// 二分查找：适合有序大数组
int[] sorted = {1, 2, 5, 8, 9};
int index2 = binarySearch(sorted, 5);   // 必须先排序

其他数组操作

数组反转

public static void reverse(int[] arr) {
    for (int i = 0, j = arr.length - 1; i < j; i++, j--) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

int[] arr = {1, 2, 3, 4, 5};
reverse(arr);
// arr: {5, 4, 3, 2, 1}

查找最大/最小值

public static int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

int[] arr = {5, 2, 8, 1, 9};
int max = findMax(arr);  // 9

数组求和

public static int sum(int[] arr) {
    int total = 0;
    for (int num : arr) {
        total += num;
    }
    return total;
}

int[] arr = {1, 2, 3, 4, 5};
int total = sum(arr);  // 15

要点总结

• Arrays.sort()数组升序排序
• Arrays.binarySearch()二分查找（需先排序）
• Arrays.fill()填充数组元素
• Arrays.copyOf()复制数组
• Arrays.copyOfRange()指定范围复制
• Arrays.equals()比较数组内容
• 冒泡排序：相邻比较，大者后移
• 选择排序：每轮找最小放到当前位置
• 线性查找：逐个遍历，O(n)
• 二分查找：折半查找，O(log n)，需有序
• Arrays.toString()输出数组内容
• 小数组/无序用线性查找
• 大有序数组用二分查找