偶数和奇数分开的数组函数的复杂性

Question

所以我有一个数组，其中包含偶数和奇数。我必须先用奇数排序，然后再用偶数排序。这是我的方法：

 int key,val;
int odd = 0;
int index = 0;

for(int i=0;i<max;i++)
{
    if(arr[i]%2!=0)
    {
        int temp = arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
        index++;
        odd++;
    }
}

首先，我将偶数和奇数分开，然后对其进行排序。对于排序，我有这个代码：

for (int i=1; i<max;i++)
{
    key=arr[i];
    
    if(i<odd)
    {
       val = 0;
    }
    if(i>=odd)
    {
        val = odd;
    }
    
    for(int j=i; j>val && key < arr[j-1]; j--)
    {
        arr[j] = arr[j-1];
        arr[j-1] = key;
    }
}

我面临的问题是我找不到上述排序代码的复杂性。就像插入排序应用于第一个奇数。当他们完成后，我跳过那部分并开始对偶数进行排序。如果我对数组进行排序，这是我的排序方法，例如：3 5 7 9 2 6 10 12 complexity table

这一切是如何运作的？在第一个 for 循环中，我遍历循环并将所有奇数放在偶数之前。但是因为它没有对它们进行排序。在下一个具有插入排序的 for 循环中。我基本上所做的只是喜欢使用 if 语句在数组中首先排序奇数。然后当 i == odd 时，嵌套的 for 循环不会遍历所有奇数，而是只计算偶数，然后对它们进行排序。

Answer 1

我假设您知道分区（假设 A）和排序算法（我们称之为 B）的复杂性。

您首先对 n 元素数组进行分区，然后对 m 元素进行排序，最后对 n - m 元素进行排序。所以总的复杂度是：

A(n) + B(m) + B(n - m)

根据 A 和 B 的实际情况，您应该可以进一步简化。

编辑： 顺便说一句，除非你的代码的目标是尝试实现 partitioning/sorting 算法，否则我相信这更清楚：

#include <algorithm>
#include <iterator>

template <class T>
void partition_and_sort (T & values) {
  auto isOdd = [](auto const & e) { return e % 2 == 1; };
  auto middle = std::partition(std::begin(values), std::end(values), isOdd);
  std::sort(std::begin(values), middle);
  std::sort(middle, std::end(values));
}

本例中的复杂度为 O(n) + 2 * O(n * log(n)) = O(n * log(n))。

编辑 2： 我错误地认为 std::partition 保持元素的相对顺序。事实并非如此。修复了代码示例。

偶数和奇数分开的数组函数的复杂性

Complexity of function with array having even and odds numbers separate

c++

sorting

time-complexity

code-complexity

insertion-sort