Microsoft : One special sort problem

There is an array of odd and even numbers. Now, sort them in such a way that the top portion of
the array contains odd numbers, bottom portion contains even numbers. The odd numbers are to be sorted
in descending order and the even numbers in ascending order. You are not allowed to use any extra array
and it has to use a conventional sorting mechanism and should not do any pre or post processing.

给出最"neat"的解决办法

如果全是正数的话，比较的时候奇数加个符号，按升序排就可以了吧

修改正常的比较逻辑：

奇数比偶数小，奇数中数值上小的比大的大，偶数正常
代码：

class CLess
{
public:
        bool operator() (int a, int b)
        {
                if(a%2 == 0 && b%2 == 1)
                        return false;

                if(a%2 == 1 && b%2 == 0)
                        return true;

                if (a%2 == 0 && b%2 == 0)
                        return a>b;

                return a<b;
        }
};

sort(a, a+n, CLess());

不能有pre or post processing。。。难道是奇偶和排序在遍历的时候同时进行么？
我觉得先把奇偶分出来挺靠谱的啊。。。

Use quick sort. When comparing numbers any odd number is presented as its negative. O(N log N)
This is equivalent to:
1. Preprocess an array so that all odd numbers are negative to the original
2. Sort the whole array
3. Post-process the array so that all odd numbers are negative to the current (which are all negative)

For example
1234567
when comparing, all odd numbers are in its negative presentation
-1 2 -3 4 -5 6 -7
After Sort:
-7 -5 -3 -1 2 4 6
But the number itself is not actually inverted
7 5 4 1 2 4 6

It fits the requirement of top portion of the array contains odd numbers, bottom portion contains even numbers. The odd numbers are to be sorted in descending order and the even numbers in ascending order.

bubble sort (sentinel at index 0):

1. def bsort(l):
   
2.   n = len(l) - 1
   
3.   while n > 1:
   
4.     l[0] = l[1]
   
5.     i = 1
   
6.     while i < n:
   
7.       left = l[i]
   
8.       right = l[i + 1]
   
9.       if left % 2 == 0 and right % 2 == 1 or \
   
10.           (left % 2 == 0 and right % 2 == 0 and right < left) or \
    
11.           (left % 2 == 1 and right % 2 == 1 and left < right):
    
12.         l[0] = l[i + 1]
    
13.         l[i + 1] = l[i]
    
14.         l[i] = l[0]
    
15.       i += 1
    
16.     if l[0] == l[1]:
    
17.       break
    
18.     n -= 1

复制代码