在你的3个条件限制下，数组不行，链表可以。

看了一下题目，简单的想了一下，思路如下：

如果是给出的数组，则没有办法能保持相对顺序不变。 下面代码只能满足条件2和3：

for (i=0, j= 2n-1; i<n, j>n; ){
    if((n[i] % 2 == 1) && (n[j] % 2==0)){
        i++;
        j--;
    }
    
    if((n[i] % 2 == 0) && (n[j] % 2)==1){
           swap(n[i],n[j]);
           i++;
           j--;
    }
    
    if((n[i] %2 == 0) && (n[j] %2 == 0)){
        j--;
    }
    
    if((n[i] %2 == 1) && (n[j] %2 == 1)){
        i++;
    }
}

就是分别从最开始和最后面进行检查，四种情况，分别判断一下。

如果给出的是链表，上述的3个条件很容易满足。

另：莫名其妙的被踩。。。

感觉是无解的。

即便是这篇文章也做了一个假设，比较两个数的f-value是常数时间，可以理解为每个数字自带位置信息。
http://www.diku.dk/~jyrki/Paper/KP1992bJ.pdf

下面是对无解我自己的分析：

这个数列是一个置换群，我们知道从一个长度为n的序列通过数字的两两置换变成另一个序列，最多需要n-1次置换操作，前提是我们知道每个数字所需要置换到的位置。但是由于没有办法知道每个数字要置换到的位置（知道也没地方储存），也没有显而易见的能够对每个数字在常数时间内求得其置换位置的方法（其实我更倾向于不存在这样的方法）。所以这应该是不可能的。

有额外空间可以用辅助数组。
有额外时间可以用类似归并排序的方法，非递归实现，因为是只分奇偶，可以原地交换。

原题的要求翻译下
1） 时间复杂度为线性
2） 空间复杂度O(k)
3) 稳定的
时间复杂度为 O(n)的话，意味着已经不能是比较排序了，比较排序的平均时间复杂度最好也就是好O(nlgn)，比如快速排序等。
这个已经是《算法导论》的被数学证明的结论了。
时间为线性的只有计数、桶和基数，见https://www.byvoid.com/blog/sort-radix
也就是排序只有
1） 计数 - 时间复杂度 O(n) 空间复杂度O(k+n)

http://www.geeksforgeeks.org/counting-sort/

2) 桶排序 - O(n) 空间复杂度 O(k+n)
http://www.growingwiththeweb.com/2015/06/bucket-sort.html

3） 基数排序 O(n) 和 O(n+k)

所以个人觉得这题无解。
BTW： 建议楼主好好看看下面这个链接
http://bigocheatsheet.com/

本人学校毕业已久，这些结论性的东西记得不是很清楚了，也就是本人不对上述结论性的东西负责 :-)
楼主可以基于上面文章再佐证下。

但基于比较的时间复杂度平均不超过O(nlogn) 这个本人是肯定的，所以建议从基数、桶排序、基数这3者里找找，看看哪个更接近你的要求。

用链表还是很容易的吧，只是改变指针就可以了，遍历一次搞定，遇到偶数插入队尾（只改指针不申请内存），奇数就不管它，但如果还要对奇偶数各自排序基本不会有O(n)的算法

L = [1, 2, 3, 4, 5, 6]
index = 0
for _ in range(len(L)):
    if L[index] % 2 == 1:
        index += 1
    else:
        L.append(L.pop(index))
print(L)

#include <iostream>
#include <list> 

using namespace std;

int main() {
    list<int> L;
    int n = 3; 
    // 初始化链表
    for(int i = 1; i <= n * 2; i++)
        L.push_back(i);
    // 划分奇偶数
    for(list<int>::iterator it = L.begin(); 0 < n; ++it){
        if(*it % 2 == 0){  // 如果是偶数
            L.push_back(*it); // 插入尾节点 O(1)
            L.erase(it); // 删除节点 O(1)
            n -= 1;
        }      
    }
    // 打印链表
    for(list<int>::iterator it = L.begin(); it != L.end(); ++it)
        cout << *it << ' ';
    cout << endl;
        
    return 0;
}

已经很多人说了， 用链表是很容易实现的，但是用数组却不行（保持稳定性，时间O(n)，空间O(1)），如果谁可以，show your code，让我们膜拜你。

初看无解的问题，貌似也有解决的办法的，待我整理一下。

def Foo(L):
    # L = [0, 2, 4, 1, 3, 5]
    length = len(L)
    sk = max(*L, length) + 1# secret key
    # 32位的话最多是支持4万多的数据量，且最大值也不超过46340
    assert sk < 46340, 'sk must be less than 46340' 
    li = 0                  # left index
    ri = length - 1         # right index
    uli = li                # unsorted left index
    uri = ri                # unsorted right index
    lli = length // 2 - 1   # left last index
    rfi = lli + 1           # right first index
    # 第一个循环先区别就位和未能就位的元素，同时将index信息加密到未能就位的元素数据中
    # 这里用的加密文法是number = -(num + sk * indnx),将其变成一个负值
    # 解密可以用index, num = divmod(abs(number), sk)来解密
    while li <= ri:
        # 左边扫描到奇数
        if L[li] % 2 == 1:
            L[li], L[uli] = L[uli], L[li]
            li += 1
            uli += 1
        # 右边扫描到偶数
        elif L[ri] % 2 == 0:
            L[ri], L[uri] = L[uri], L[ri]
            ri -= 1
            uri -= 1
        # 当左为偶，且右为奇
        else:
            L[li], L[ri] = L[ri], L[li]
            L[li] = -(L[li] + sk * lli) # 加密乱序的元素
            lli -= 1
            L[ri] = -(L[ri] + sk * rfi) # 加密乱序的元素
            rfi += 1
            li += 1
            ri -= 1
    print(L) # 加密后 [-39, -20, -1, -89, -70, -51]
    # 解密
    for i in range(uli, uri):
        if L[i] < 0:
            index, number = divmod(abs(L[i]), sk)
            next_num = L[index]
            while next_num < 0:                
                L[index] = number
                index, number = divmod(abs(next_num), sk)
                next_num = L[index]
    print(L) # 解密 [1, 3, 5, 0, 2, 4]
    return L

最好不要用大于length数字来测试，如果数据不大的话，应该没问题的，否则就要考虑溢出的问题了。

作为一般的排序问题来看，会让人觉得不可能，但是这个题目虽然3个条件很苛刻。
也有一些有利条件可以利用，重要的2点就是：

1. 奇数和偶数一样多，所有数组长度就是 n + n

2. 奇数和偶数保持原有顺序，不需要按大小进行排序

我用golang实现如下：

package main

import "fmt"

func main() {
    var n = 4
    // var intArr = []int{12, 2, 4, 6, 5, 1, 7, 3}
    // var intArr = []int{1, 2, 3, 4, 5, 6, 7, 8}
    var intArr = []int{1, 2, 4, 6, 8, 3, 5, 7}
    var odd = 0
    var even = 2*n - 1

    for i := 0; i < len(intArr); i++ {
        if i > even {
            break
        }

        // fmt.Printf("before: %v\n", intArr)
        if intArr[i]%2 == 0 { // even number
            intArr[even], intArr[i] = intArr[i], intArr[even]
            even--
        } else { // odd number
            intArr[odd], intArr[i] = intArr[i], intArr[odd]
            odd++
        }
        // fmt.Printf("after : %v\n", intArr)
    }

    // print result
    for i := 0; i < odd; i++ {
        fmt.Println(intArr[i])
    }
    for i := even; i > odd-1; i-- {
        if intArr[i]%2 != 0 {
            fmt.Println(intArr[i])
        }
    }
    for i := 2*n - 1; i > even; i-- {
        fmt.Println(intArr[i])
    }
    for i := odd; i < even+1; i++ {
        if intArr[i]%2 == 0 {
            fmt.Println(intArr[i])
        }
    }
}

看了评论，开始我也以为这个题目无解，但是今天下班路上突然灵机一动，想到一个方法，简单验证了一下，发现确实可以。
这个算法只需要O(1)的空间，O(n)的时间，并且不会改变原数组中奇数和偶数之间的相对顺序，完全符合题目要求。今天先说一下算法思路，明天抽空把程序补上。

简单来说就是从前到后扫描各个元素，扫描时使用2个指针，一个用来进行常规遍历（就是平时我们遍历数组使用的i）；另一个始终指向数组中的第一个偶数，这里称为偶数指针，初始化为-1。

遍历开始，对于每一个元素，分为以下几种情况：

1. 该元素为奇数，并且它之前有偶数（偶数指针大于等于0），交换这两个数

2. 该元素为奇数，并且它之前没有偶数（偶数指针为-1），不做任何操作，继续下一轮遍历

3. 该元素为偶数，并且它的前一个元素为偶数（注意是前一个元素，不是偶数指针指向的那个元素），交换这两个数

4. 该元素为偶数，并且它的前一个元素为奇数，此时偶数指针一定是-1，将其赋值为当前元素的索引（即i）

如此一直重复到倒数第二个元素，而对于最后一个元素需要特殊处理：如果它是奇数则按照上面1的步骤来处理；如果它是偶数，则不做任何处理，遍历完成。

举个例子，1 2 3 4 5 6，下面是每一轮遍历之后数组的状态（[]表示当前遍历到的元素和偶数指针指向的元素）：

[1] 2 3 4 5 6
1 [2] 3 4 5 6
1 3 [2] 4 5 6
1 3 [4] [2] 5 6
1 3 5 [2] [4] 6
1 3 5 [2] 4 [6] // 完成

再举个例子，1 2 4 6 8 5 7 3：

[1] 2 4 6 8 5 7 3
1 [2] 4 6 8 5 7 3
1 [4] [2] 6 8 5 7 3
1 [4] 6 [2] 8 5 7 3
1 [4] 6 8 [2] 5 7 3
1 5 [6] 8 2 [4] 7 3
1 5 7 [8] 2 4 [6] 3
1 5 7 3 [2] 4 6 [8] // 完成

卧槽，瞬间体现 JavaScript 是世界上最好的语言了

数组即链表，支持各种操作，屌吧

补：别睬我了，PHP 是世界上最好的语言，我错了

再补：说我不懂数据结构的大概都没 get 到我调侃的语气吧...

我觉得是不可能的，其实归根结底，这是一个排序问题。
我们假设使用快排(当然不满足稳定性问题，这里只是随便说，想要稳定性可以用二叉树来排序)，那么只要把比较条件设为奇数比偶数大就可以了。
但是很明显排序问题只有在某些特殊情况下才能O(n)。
所以我觉得不可能。

我是這樣想拉，不知道你覺得怎麼樣:

就從數組的頭開始走，碰到奇數不動，碰到偶數就把它放到數組的最後，直到搬動了 n 個偶數為止。

1. 奇數偶數各自順序不變
2. 只需要一個整數記目前搬動幾個了
3. 就最差 2n 步(偶數都在後面的情況)

P.S. 為什麼給負分呢? 如果覺得答案有任何不妥的地方，可以先評論、討論之後再給別人負分，我不覺得有必要踩在這裡認真討論的人，對於負分充滿著疑惑...