Microsoft : One special sort problem

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

不能有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

复制代码