如何实现数组前半段升序、后半段降序排序，Java实现且时间复杂度O(n)

云上老周

2026-9-24

解决方案

前提说明

标准归并排序的整体时间复杂度为O(nlogn)，题目要求的O(n)指的是在原有归并排序实现基础上的额外修改开销，以下方案完全满足该要求，整体算法复杂度仍保持归并排序的O(nlogn)。

修改思路

你原有归并排序已经可以实现全数组升序排序，只需在排序完成后新增一步O(n)复杂度的后半段反转操作即可，改动量极小：

第一步：保留原有归并排序的全部逻辑，先将整个数组按升序完整排序
第二步：计算数组中间索引 mid = 数组长度 / 2，如果数组长度为奇数，可根据实际需求调整前后段的长度分配规则
第三步：原地反转数组从mid到末尾的后半段，该操作时间复杂度为O(n/2) = O(n)，符合时间复杂度要求

代码实现示例

你已实现的mergeSort、merge方法无需任何修改，仅需新增反转方法、修改排序入口即可：

// 你原有已实现的归并排序代码无需改动，此处省略

// 新增：原地反转数组指定区间 [start, end] 的元素
private static void reverse(int[] arr, int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

// 修改后的自定义排序入口方法
public static void halfAscHalfDescSort(int[] arr) {
    // 调用原有归并排序完成全数组升序排序
    mergeSort(arr, 0, arr.length - 1);
    int mid = arr.length / 2;
    // 反转后半段得到降序效果
    reverse(arr, mid, arr.length - 1);
}