将一个数组按照奇偶数分组

Question

我实现了一个算法，将数组中的所有偶数移到数组的开头，让原始数字位于数组的末尾。以下是我的程序：-

#include <iostream>
using namespace std;

void print(int arr[], int size) {
    for(int i=0;i<size;i++) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

void segregate(int arr[], int size) {
    int l=0, h=size-1;

    while(l<h) {

        while(!(arr[l]%2) && l<size) {
            l++;
        }
        while((arr[h]%2) && h >=0) {
            h--;
        }
        swap(arr[l], arr[h]);
    }
}

int main() {

    int arr[] = {1,2,3,4,5,6,7,8,9};
    int size = 9;

    print(arr,size);

    segregate(arr,size);

    print(arr,size);

    return 0;
}

我没有得到预期的结果。

1 2 3 4 5 6 7 8 9 
8 2 6 5 4 3 7 1 9 

我错过了什么？

- Jane Jose

---

建议：使用 sizeof(arr) 查找数组的 size。 - iammilind

请注意，sizeof(arr) 返回的是数组的大小（以字节为单位），而不是元素个数。使用 sizeof(arr) / sizeof(*arr) 来获取元素个数。 - Joey Adams

Answer 1

你试图做的也被称为分区。标准库提供了两个算法来实现这一点：std::partition和std::stable_partition。

int main()
{
   int arr[] = {1,2,3,4,5,6,7,8,9};

   auto split = std::partition( std::begin(arr), std::end( arr ),
         []( int a ) { return ! a%2; } );

   // [ begin, split ) are all even
   // [ split, end ) are all odd
}

http://ideone.com/kZI5Zh

如果您仍然对编写自己的代码感兴趣，cppreference中std::partition的描述包括等效代码。
您的版本在交换之前缺少一个if语句。只有左侧存在奇数时才应该进行交换。

- deft_code

Answer 2

简单易懂：

void partitionEvenOdd(int array[], int arrayLength, int &firstOdd)
{
    firstOdd = 0;
    for (int i = 0; i < arrayLength; i++) {
        if (array[i]%2 == 0) {
            swap(array[firstOdd], array[i]);
            firstOdd++;
        }
    }
}

- Thijs van Dien

Answer 3

问题1：

只有当l没有越过h时，才需要调用swap函数，但你总是在调用它。

考虑已经被分离的数组{2,1}。 现在，在两个内部while循环之后，l将是1，h将是0。在你的情况下，你会继续进行交换，但实际上并不需要交换，因为l已经越过了h。 当这种情况发生时，数组已经被分离。

所以修改为

swap(arr[l], arr[h]);

为了

if(l<h) {
    swap(arr[l], arr[h]);
}

问题2：

同时，您内部while循环中的条件顺序必须反转。您正在检查

while(number at index l is even AND l is a valid index) {
    l++;
}

这是不正确的。考虑一个数组{2,4}，现在在上述while循环中的某个时刻，l将变成2，然后你试图访问arr[2]，但实际上它并不存在。

你需要做的是：

while(l is a valid index AND number at index l is even) {
    l++;
}

- codaddict

Answer 4

你不能使用标准排序吗？

像这样：

#include <stdio.h>
#include <stdlib.h>

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  // return -1 a-even and b-odd
  //        0  both even or both odd 
  //        1  b-even and a-odd
}

qsort (values, 6, sizeof(int), compare);

- Elalfer

---

除非qsort()进行三向划分，否则您将浪费大量时间。 - Per

但它易于理解和维护。而且根据数组的大小，实际上可能并不重要。 - Tobias Langner

是的，“可维护性”和易用性是我的首要目标。关于性能 - 对于小数组来说应该差不多，作者没有提到大小。 - Elalfer