首页 文章

排序数组的偶数和奇数部分

提问于
浏览 次
2

我有点坚持这种逻辑 . 让我说我有 int 的数组 . 我需要的是将偶数和奇数分开，即所有偶数应按排序顺序排在第一位，然后按排序顺序排列所有奇数 .
This needs to be done with array only not collection.
输入将是 .

int[] a ={3,2,5,6,4,9,11,7}

输出应为

{2,4,6,3,5,7,9,11}

我的方法是： -
1.首先分开偶数和奇数 .
2.然后找到last_index-of_even_number .
3.然后首先对数组进行排序 0-last_index-of_even_number ，然后对 last_index-of_even_number- arr.length 进行排序 .

但我认为这不是一个好方法 . 任何人都可以通过算法和代码示例帮助我理解这个逻辑 .

java

5 回答

  • 2

    应用任何排序算法并将比较器用作比偶数“小于”奇数的偶数 . 这使您可以使用良好的排序算法，同时仍按您希望的方式对元素进行排序 .

    这是我的gnome排序实现和我的比较功能：

    private static void sort(int[] arr) {
    int index = 0;
    int n = arr.length;
    while (index < n) {
        if (index == 0)
            index++;
        if (compare(arr[index], arr[index - 1]))
            index++;
        else {
            int temp = arr[index];
            arr[index] = arr[index - 1];
            arr[index - 1] = temp;
            index--;
        }
    }
}

private static boolean compare(int a, int b) {
    if (a % 2 == b % 2) return a > b;
    return a % 2 == 1;
}

public static void main(String[] args) {
    int[] a = {3, 2, 5, 6, 4, 9, 11, 7};

    sort(a);

    for (int i : a) {
        System.out.print(i + " ");
    }
}

    工作良好 . 尝试其他排序算法 .

    TL; DR：使用函数，而不是使用“<”和“>”比较项目 .

    回复于
  • 1

    简单解决方案

    • 对输入数组进行排序 .

    • 创建一个具体的 List . 使用您想要的任何实现; LinkedList 似乎适合 .

    • 运行输入数组一次 . 对于每个偶数，将其添加到 List .

    • 再次运行输入数组 . 对于每个添加号码，将其添加到 List .

    • 将 List 转换为数组（为此读取Java API页面） .

    如果您认为排序是 n*log(n) ，它现在变为 n*log(n) + 2 ，我相信，它会缩减回 n*log(n) .

    小丑限制的解决方案（或者，也许是未承认的学生作业限制）

    • 对输入数组进行排序 .

    • 创建一个与输入数组大小相同的新数组（将其称为目标数组） .

    • 运行输入数组（按索引） . 对于每个偶数，将其添加到目标数组 .

    • 运行输入数组（按索引） . 对于每个奇数，将其添加到目标数组 .

    • 使用目标数组执行您想要的操作（可能将其复制到输入数组） .

    如果使用快速排序排序，则与 List 相同的Big-O .

    回复于
  • 4

    移动数组中的东西并不是那么有效，因为数据是按顺序存储的 . 如果你不想使用其他结构，你可以改为排序第一个O（nlogn） . 虽然排序你可以轻松计算你有多少偶数，所以你知道第一个奇数的位置 . 然后创建第二个数组，让我们说b并添加从0开始的所有偶数和从第一个奇数的位置开始的奇数 . 你可以在O（n）中执行此操作，一个解析

    //sort a first
//find odd_index --> 3 in your case

int even_index=0;
for(int i=0; i<a.length; i++){
    if(a[i]%2==0){
        b[even_index]=a[i];
        even_index++;
    }else{
        b[odd_index]=a[i];
        odd_index++;
    }
}
    回复于
  • 2

    看看这个解决方案：

    public class Test 
 {
   static int [] oddEvenSort(int arr[]){
     int temp[] = new int [arr.length];
     int evenIndex = 0;
     int oddIndex = arr.length - 1;
    arr = sort(arr);
     for(int i = 0;i<arr.length;i++)
     {

         if((arr[i] & 1) == 0){
             temp[evenIndex] = arr[i];
             evenIndex += 1;
         }else
         {
             temp[oddIndex] = arr[i];
            oddIndex -= 1;
         }
     }
    return temp;
 }

 static  int [] sort(int arr[]){
      for(int i=0; i< arr.length;i++)
     {
         for(int j = i;j < arr.length;j++)
         {
         if(arr[j] < arr[i]){
             int temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
         }
         }
     }
     return arr;
 }

public static void main(String[] args)
{
    int arr[] = {1, 3, 2, 7, 5, 4};

    oddEvenSort(arr, arr.length);

    System.out.println(Arrays.toString(arr));
 }
}
    回复于
  • 2

    你可以做的是在java中使用两个treemap . 一个用于偶数，一个用于奇数 . 迭代数字时偶数树图中的偶数和奇数树图中的奇数 . 在合并之后，两个树形图首先在一个列表中然后是奇数 .

    我认为这适用于您的情况 .

    回复于

相关问题