对数组进行排序。输入--> [3,4,5,1,2]预期输出--->[5,2,3,1,4]

Question

Input: nums = [3, 4, 5, 1, 2]

Output: nums = [5, 2, 3, 1, 4]

说明：在此示例中，偶数

[4, 2]

位于位置

[1, 4]

。

它们按升序排序并放回原来的位置。奇数

[3, 1, 5]

原来在位置

[0, 2, 3]

，保持原来的位置，按降序排列。

我尝试过，但我成功了

[5,2,3,4,1]

如何获得预期的输出

[5,2,3,1,4]

import java.util.ArrayList;
import java.util.Arrays;

public class BubbleSorting {
    
    static void bubbleSort(ArrayList<Integer> list, Boolean Bool) {
        int n = list.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if(Bool==true) {
                if (list.get(j) > list.get(j + 1)) {
                    // Swap elements if they are in the wrong order
                    int temp = list.get(j);
                    list.set(j, list.get(j + 1));
                    list.set(j + 1, temp);
                }
                }
                else {
                    if (list.get(j) < list.get(j + 1)) {
                        // Swap elements if they are in the wrong order
                        int temp = list.get(j);
                        list.set(j, list.get(j + 1));
                        list.set(j + 1, temp);
                }
            }
          }
        
      }
    }

    
    public static void main(String[] args) {
        int[] num = {3,4,5,1,2};
        ArrayList<Integer> even = new ArrayList<>();
        ArrayList<Integer> odd = new ArrayList<>();
        for(int i=0; i<num.length; i++) {
            if (num[i]%2==0) {
                even.add(num[i]);
            }
            else {
                odd.add(num[i]);
            }
        }
        System.out.println("Before_sort"+odd);
        System.out.println("Before_sort"+even);
        bubbleSort(odd, false);
        bubbleSort(even, true);
        System.out.println("after_sort"+odd);
        System.out.println("after_sort"+even);
        
        int[] combinedArray = new int[5];
        int currentIndex = 0;
        for (int i = 0; i < Math.max(odd.size(), even.size()); i++) {
            if (i < odd.size()) {
                combinedArray[currentIndex++] = odd.get(i);
            }
            if (i < even.size()) {
                combinedArray[currentIndex++] = even.get(i);
            }
        }
        System.out.println(Arrays.toString(combinedArray));
    }

}

Answer 1

您所做的是非常正确的做法。首先将奇数和偶数元素分离到列表中，并分别按升序和降序排序。然后合并它们，同时保留原始数组的轨迹。这是我使用 Java Collection 排序的方法（尽管不使用冒泡排序）：

int[] sort(int[] nums) {
    List<Integer> evens = new ArrayList<>(), odds = new ArrayList<>();

    // Separating odd and even elements
    for (int num : nums) {
      if (num % 2 == 0) {
        evens.add(num);
      } else {
        odds.add(num);
      }
    }

    // even numbers ascending
    Collections.sort(evens);

    // odd numbers descending
    Collections.sort(odds, Collections.reverseOrder());

    // merging odd and even to a new array according to 
    // their occurence in the original array
    int[] result = new int[nums.length];
    int evenIndex = 0, oddIndex = 0;

    for (int i = 0; i < nums.length; i++) {
      if (nums[i] % 2 == 0) {
        result[i] = evens.get(evenIndex);
        evenIndex++;
      } else {
        result[i] = odds.get(oddIndex);
        oddIndex++;
      }
    }
    return result;
 }

在合并过程中，我为奇数和偶数列表保留了不同的索引（为此目的，您使用了单个索引“i”）。

Answer 2

for (int i = 0; i < Math.max(odd.size(), even.size()); i++) {
        if (i < odd.size()) {
            combinedArray[currentIndex++] = odd.get(i);
        }
        if (i < even.size()) {
            combinedArray[currentIndex++] = even.get(i);
        }
    }

此代码不允许您维护偶数奇数值的实际顺序，而只是在循环中添加 1 个奇数、1 个偶数

所以解决这个问题，你需要做 -

int[] combinedArray = new int[5];
    int oddIndex = 0;
    int evenIndex = 0;
    for (int i = 0; i <combinedArray.length ; i++) {
        if (num[i]%2==1) {
            combinedArray[i] = odd.get(oddIndex++);
        }
        else {
            combinedArray[i] = even.get(evenIndex++);
        }
    }

您的冒泡排序已经在维持顺序了。然后，如果任何索引包含 odd，则将 odd 放在该位置，反之亦然。这也将维持索引顺序。