所以我有一个数组,里面有偶数和奇数。我必须先用奇数排序,然后用偶数排序。这是我的方法:
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复杂度表
这一切是如何运作的?在第一个for循环中,我遍历循环,将所有奇数放在偶数之前。但既然它没有对它们进行排序。在下一个for循环中,它有插入排序。我基本上只使用if语句在数组中只对奇数进行排序。当i==奇数时,嵌套的for循环不会遍历所有奇数,而是只计算偶数,然后对它们进行排序。
我假设您知道分区(比如A
(和排序算法(我们称之为B
(的复杂性。
首先对n
元素数组进行分区,然后对m
元素进行排序,最后对n - m
元素进行排序。因此,总的复杂性是:
A(n) + B(m) + B(n - m)
根据A
和B
的实际情况,您可能能够进一步简化它。
编辑:顺便说一句,除非你的代码的目标是尝试实现分区/排序算法,否则我相信这会更清楚:
#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
保持元素的相对顺序。事实并非如此。修复了代码示例。