按顺序排列偶数和奇数

我试图在一次通过时分别将偶数和奇数分别分离到左侧和右侧。此外，我想确保这些数字按照顺序排序，这样整个逻辑将具有O（n）的复杂性。按顺序排列偶数和奇数

例如，如果我的输入是{9,8,2,3,11,10,1};

这个逻辑我实现了o/p为{10 8 2 3 11 9 1}，但我想确保我的输出在同一遍中排序为{2,8,10,1,3,9,11} 。

static void segregateEvenOdd(int arr[]) { 
    /* Initialize left and right indexes */ 
    int left = 0, right = arr.length - 1; 
    while (left < right) { 
     /* Increment left index while we see 0 at left */ 
     while (arr[left] % 2 == 0 && left < right) 
      left++; 

     /* Decrement right index while we see 1 at right */ 
     while (arr[right] % 2 == 1 && left < right) 
      right--; 

     if (left < right) { 
      /* Swap arr[left] and arr[right] */ 
      int temp = arr[left]; 
      arr[left] = arr[right]; 
      arr[right] = temp; 
      left++; 
      right--; 
     } 
    } 
}

来源

2016-01-20 skanda

你的问题究竟是什么？ – Skam

对O（n）中的数组进行排序 - 你不是要求太多吗？ –

给定的数组是否已经排序？ –

使用比较整数排序算法最好的算法中能做到这一点的O(nlgn)这样你就可以用比较整数排序不能达到O(n)。

你可以做什么是：你可以使用非比较整数排序算法。像：

这将整理您的O(n)与你输入一些条件阵列。查看更多细节的例子。

来源

2016-01-20 06:41:21

这是不可能的一次。你真的有两种不同的种类。一个用于偶数，另一个用于赔率。

这是我会建议的。

解决方法1.

，如果你被允许引入新的数据结构采取以下方法创建两个的ArrayList（一个连一个的奇）他们适当地分开。两个都运行Collections.Sort。以迭代方式重新初始化您的初始数组。

解决方案2.

使用你上面妥善独立埃文斯和赔率的方法。统计列表中的平均数。构建一个典型的排序例程，比如mergesort，并在数组的两个不同的段上调用例程。上面的例子可以这样调用

merge(arr, 0, 2); 
merge(arr, 3, 6);

这两种解决方案都具有整体时间复杂度：O（nlogn）。空间复杂度：O（n）。解决方案一更容易实施，但解决方案二允许您进行更多就地排序。其他排序例程的最佳情况是O（n）时间，但不保证它。

来源

2016-01-20 09:42:58

我会用一个快速排序或其它任何标准算法，但限定元件之间的比较为：a小于b如果a是偶数和b是奇数还是它们都是偶数或奇数和a<b。

这不会给你O（n），这是不可能的，但通过重用已知的算法可以达到最佳性能。

来源

2016-01-20 11:46:33 manuBriot

使用Sort overload可让您通过Comparator。比较函数应该像下面这样（伪代码）：

Comparison(a, b) 
{ 
    if (Even(a) && !Even(b)) 
     return -1; // a < b 
    if (Even(b) && !Even(a)) 
     return 1; // a > b 
    // both are even, or both are odd. 
    if (a < b) return -1; 
    if (a > b) return 1; 
    return 0; 
}

来源

2016-01-20 15:31:34

按顺序排列偶数和奇数

回答

相关问题