可以使这种算法更好吗? [英] Could this algorithm be made better?
问题描述
我有一个问题,在我写的一种算法中,要分离出左边的所有偶数和右边的奇数.
I have a question, in one of the algorithms, I had written, to seperate out, all the even numbers to the left and odd numbers to the right.
示例:输入:
{12,10,52,57,14,91,34,100,245,78,91,32,354,80,13,67,65}
{ 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}
{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)或更好?
Anybody, have any suggestions, for it make it to O(n) or better ?
推荐答案
您的代码为O(n),但比所需的要复杂一些.这是一个改进.
Your code is O(n), but it's a bit more complicated than it needs to be. Here's an improvement.
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
.
By the way, the operation is more of a partition than a sort. I think a better function name would be partitionEvenOdd
.
这篇关于可以使这种算法更好吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!