java - 即使在奇数之前，也使用递归按升序排列

Question

我需要能够有一个整数数组，将偶数整数放在奇数整数之前，然后按升序对数组进行排序。例如，给定数组 [1,2,3,4,5]，最终产品应类似于 [2,4,1,3,5]，因为您可以看到该数组在赔率之前都有偶数，然后将它们放置按升序排列。

正如您在代码中看到的，我正在使用数组 [10,9,8,7,6,5,4,3,2,1]。我得到的输出是 [1,2,3,4,5,6,7,8,9,10]，但这是不正确的 - 它应该是 [2,4,6,8,10,1,3 ,5,7,9]。我无法使用任何内置函数或库。这是我到目前为止所拥有的:

public class EBOMain {

static int[] Array  = { 10,9,8,7,6,5,4,3,2,1};
static int n;

public static void main(String[] args) {


    System.out.print("Array before sort: "  );
    for (int i = 0; i < Array.length; i++)
        System.out.print(Array[i] +" ");
    n = Array.length;
    EvenBeforeOdd(Array, n);

    int[] Array2 = new int[Array.length];
    MergeSort(Array2, 0,Array.length - 1);

    System.out.print("\nArray after sort: "  );
    for (int i = 0; i < Array.length; i++)
        System.out.print(Array[i] +" ");        
}

public static void EvenBeforeOdd(int []Array,int n){
      if (n==0)
        return;
    else if(Array[n-1]%2==0) {
        for(int i=0;i<n-1;i++) {
            if(Array[i]%2!=0) {      
                int temp = Array[i];
                Array[i]= Array[n-1];
                Array[n-1] = temp;

                EvenBeforeOdd(Array,n-1);
            }
        }
    }
    else
        EvenBeforeOdd(Array,n-1);
 }

 static void MergeSort(int[] Combine, int LowerIndex, int UpperIndex) {

    if (LowerIndex == UpperIndex){
           return;

    }

    else {    // locate Pivot
           int Pivot = (LowerIndex + UpperIndex) / 2;
           MergeSort(Combine, LowerIndex, Pivot);
           MergeSort(Combine, Pivot + 1, UpperIndex);
           Merge(Combine, LowerIndex, Pivot + 1, UpperIndex);
    }

 }



    static void Merge(int[] Array2, int Small, int Large, int UpperIndex) {

        int Pivot = Large - 1;
        int LowerIndex = Small;
        int n = UpperIndex - LowerIndex + 1;
        int i = 0;

        while (Small <= Pivot && Large <= UpperIndex)
               if (Array[Small] < Array[Large])
                     Array2[i++] = Array[Small++];
               else
                     Array2[i++] = Array[Large++];

        while (Small <= Pivot)
               Array2[i++] = Array[Small++];

        while (Large <= UpperIndex)
               Array2[i++] = Array[Large++];

        for (i = 0; i < n; i++)
               Array[LowerIndex + i] = Array2[i];

 }







}

Answer 1

您只需要调用 MergeSort 两次即可。确定最后一个偶数在哪里，对偶数调用 MergeSort，然后对赔率调用 MergeSort。应该进行边界检查，以防没有偶数(此处不包括):

EvenBeforeOdd(Array, n);
int lastEven = 0;
for (int i=0; i<Array.length; i++) {
    if (Array[i] % 2 == 0)
        lastEven = i;
}
int[] Array2 = new int[Array.length];
MergeSort(Array2, 0, lastEven);
MergeSort(Array2, lastEven+1, Array.length - 1);