Java怎么求数组的中间值

Java 中求数组中间值有两种方法：1. 使用排序后取中，对数组排序后取中间索引元素；2. 使用快速选择，将数组划分为三部分，找到比基准元素大且在前半部分（奇数长度）或后半部分（偶数长度）的元素。

Java 求数组中间值的两种方法

开门见山：

Java 中求数组中间值的方法有两种：

详细展开：

万兴喵影

国产剪辑神器

下载

立即学习“Java免费学习笔记（深入）”；

方法 1：使用排序后取中

1. 先对数组进行排序。
2. 如果数组长度为奇数，中间值为排序后的数组中索引为 (n-1)/2 的元素。
3. 如果数组长度为偶数，中间值为排序后的数组中索引为 n/2 和 n/2-1 的元素的平均值。

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

// 对数组进行排序
Arrays.sort(arr);

// 数组长度为奇数
if (arr.length % 2 != 0) {
    int midIndex = (arr.length - 1) / 2;
    int midValue = arr[midIndex];
    System.out.println("中间值为：" + midValue);
}
// 数组长度为偶数
else {
    int midIndex1 = arr.length / 2;
    int midIndex2 = midIndex1 - 1;
    double midValue = (arr[midIndex1] + arr[midIndex2]) / 2.0;
    System.out.println("中间值为：" + midValue);
}

方法 2：使用快速选择

1. 选择一个基准元素（通常是数组的第一个元素）。
2. 将数组中的元素划分为比基准元素小、等于和大的三个部分。
3. 如果数组长度为奇数，中间值是比基准元素大且数目比一半少的元素。
4. 如果数组长度为偶数，中间值是比基准元素大且数目比一半多或等于一半的元素。

// 快速选择算法
int quickSelect(int[] arr, int low, int high, int k) {
    // 递归终止条件
    if (low == high) {
        return arr[low];
    }

    // 选择一个基准元素
    int pivot = arr[high];

    // 将数组划分为三部分
    int partition = partition(arr, low, high, pivot);

    // 找到中间值
    if (k == partition) {
        return arr[partition];
    } else if (k < partition) {
        return quickSelect(arr, low, partition - 1, k);
    } else {
        return quickSelect(arr, partition + 1, high, k);
    }
}

// 划分数组的函数
int partition(int[] arr, int low, int high, int pivot) {
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

// 主函数
public static void main(String[] args) {
    // 数组 arr
    int[] arr = {1, 3, 5, 2, 4};

    // 使用快速选择算法获取中间值
    int midValue = quickSelect(arr, 0, arr.length - 1, (arr.length - 1) / 2);

    // 输出中间值
    System.out.println("中间值为：" + midValue);
}