时间戳

首页 > 解决方案 > 这个算法可以做得更好吗？

algorithm - 这个算法可以做得更好吗？

问题描述

我有一个问题，在我写的一个算法中，要分离出左边的所有偶数和右边的奇数。

示例：输入：

{ 12, 10, 52, 57, 14, 91, 34, 100, 245, 78, 91, 32, 354, 80, 13, 67, 65 }

输出：

{12,10,52,80,14,354,34,100,32,78,91,245,91,57,13,67,65}

下面是算法

public int[] sortEvenAndOdd(int[] combinedArray) {
  int endPointer = combinedArray.length - 1;
  int startPointer = 0;
  for (int i = endPointer; i >= startPointer; i--) {
    if (combinedArray[i] % 2 == 0) {
      if (combinedArray[startPointer] % 2 != 0) {
        int temp = combinedArray[i];
        combinedArray[i] = combinedArray[startPointer];
        combinedArray[startPointer] = temp;
        startPointer = startPointer + 1;
      } else {
        while (combinedArray[startPointer] % 2 == 0 &&
          (startPointer != i)) {
          startPointer = startPointer + 1;
        }
        int temp = combinedArray[i];
        combinedArray[i] = combinedArray[startPointer];
        combinedArray[startPointer] = temp;
        startPointer = startPointer + 1;
      }
    }
  }
  return combinedArray;
}

任何人，有什么建议，让它达到 O(n) 或更好吗？

标签： algorithm

解决方案

您的代码是 O(n)，但它比它需要的要复杂一些。这是一个改进。

startPointer = 0;
endPointer = a.length - 1;
while (startPointer < endPointer)
{
    if (a[startPointer] % 2 != 0)
    {
        // move endPointer backwards to even number
        while (endPointer > startPointer && a[endPointer] % 2 != 0)
        {
            --endPointer;
        }
        swap(a[startPointer], a[endPointer]);
    }
    ++startPointer;
}

顺便说一句，该操作更像是一个分区而不是排序。我认为更好的函数名称是partitionEvenOdd.

推荐阅读