如何修改Java数组重排代码，实现正数优先并保持元素相对顺序

核心逻辑说明 #

原有代码基于稳定归并的原地块交换算法实现，原本规则为「负数在前、正数在后」，且保证同类型元素相对顺序不变。只需调整merge方法中的位置判断条件，即可切换为「正数在前、负数在后」，时间复杂度、空间复杂度、稳定性均保持原有特性不变。

具体改动点 #

仅需修改merge函数中的两个while循环的判断条件，其余代码无需调整：

• 左子数组遍历：原本为跳过负数找第一个正数，修改为跳过正数找第一个负数

  // 原代码
  while (i <= m && arr[i] < 0)
      i++;
  

  改为

  // 修改后
  while (i <= m && arr[i] >= 0)
      i++;
  

• 右子数组遍历：原本为跳过负数找第一个正数，修改为跳过正数找第一个负数

  // 原代码
  while (j <= r && arr[j] < 0)
      j++;
  

  改为

  // 修改后
  while (j <= r && arr[j] >= 0)
      j++;
  

调整后的完整可运行代码 #

// Java 实现：重排数组使正数在前、负数在后，保持同类型元素相对顺序
public class Rearrangement {
    /* Function to print an array */
    static void printArray(int[] A, int size) {
        for (int i = 0; i < size; i++)
            System.out.print(A[i] + " ");
        System.out.println("");
    }

    /* Function to reverse an array. An array can be
    reversed in O(n) time and O(1) space. */
    static void reverse(int[] arr, int l, int r) {
        if (l < r) {
            arr = swap(arr, l, r);
            reverse(arr, ++l, --r);
        }
    }

    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    static void merge(int[] arr, int l, int m, int r) {
        int i = l; // Initial index of 1st subarray
        int j = m + 1; // Initial index of IInd

        // 跳过左子数组所有正数，找到左侧第一个负数的位置
        while (i <= m && arr[i] >= 0)
            i++;
        // arr[i..m] 是左侧子数组的负数块
        // 跳过右子数组所有正数，找到右侧第一个负数的位置
        while (j <= r && arr[j] >= 0)
            j++;
        // arr[m+1..j-1] 是右侧子数组的正数块

        // 反转左侧负数块 arr[i..m]
        reverse(arr, i, m);
        // 反转右侧正数块 arr[m+1..j-1]
        reverse(arr, m + 1, j - 1);
        // 反转整个待交换区间 arr[i..j-1]，完成块顺序交换
        reverse(arr, i, j - 1);
    }

    // Function to Rearrange positive and negative
    // numbers in a array
    static void RearrangePosNeg(int[] arr, int l, int r) {
        if (l < r) {
            // Same as (l+r)/2, but avoids overflow for
            // large l and h
            int m = (l + r) / 2;

            // Sort first and second halves
            RearrangePosNeg(arr, l, m);
            RearrangePosNeg(arr, m + 1, r);

            merge(arr, l, m, r);
        }
    }

    static int[] swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {1, 7, -5, 9, -12, 15, -6, -8};
        int arr_size = arr.length;
        RearrangePosNeg(arr, 0, arr_size - 1);
        printArray(arr, arr_size);
    }
}

运行效果 #

• 输入数组：{1, 7, -5, 9, -12, 15, -6, -8}
• 输出结果：1 7 9 15 -5 -12 -6 -8

完全符合目标要求，同类型元素的原有相对顺序保持不变。

内容的提问来源于stack exchange，提问作者Chris Costa