Di bawah tiga syarat anda, tatasusunan tidak boleh dilakukan, tetapi senarai terpaut boleh dilakukan.

Sangat mudah untuk menggunakan senarai terpaut. Hanya tukar penunjuk. Jika anda menemui nombor genap, masukkannya ke penghujung baris gilir (hanya tukar penunjuk dan jangan gunakan untuk ingatan). . Abaikan nombor ganjil Tetapi jika anda masih perlu memisahkan nombor ganjil dan genap pada dasarnya tiada algoritma O(n) untuk mengisih

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;
}

Ramai orang mengatakan bahawa ia mudah untuk dilaksanakan menggunakan senarai terpaut, tetapi tidak dengan tatasusunan (mengekalkan kestabilan, masa O(n), ruang O(1) Jika sesiapa boleh, tunjukkan kod anda dan izinkan kami Sembah anda .

Pada pandangan pertama, nampaknya ada penyelesaian kepada masalah yang kelihatan tidak dapat diselesaikan.

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 = pmod(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 = pmod(abs(L[i]), sk)
            next_num = L[index]
            while next_num < 0:                
                L[index] = number
                index, number = pmod(abs(next_num), sk)
                next_num = L[index]
    print(L) # 解密 [1, 3, 5, 0, 2, 4]
    return L

Sebaik-baiknya jangan gunakan nombor yang lebih besar daripada panjang untuk menguji Jika data tidak besar, ia sepatutnya baik, jika tidak, anda perlu mempertimbangkan isu limpahan.

Saya ingin menariknya begitu banyak, saya tidak tahu apa yang anda fikirkan:

Cuma mulakan dari kepala tatasusunan, dan jangan bergerak apabila anda menemui nombor ganjil Jika anda menemui nombor genap, letakkannya di hujung tatasusunan, sehingga n nombor genap telah dialihkan.

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

P.S. Kenapa nak bagi markah negatif kalau korang rasa ada yang tak kena dengan jawapan tu, korang boleh komen dan bincang dulu sebelum bagi markah negatif kat orang lain rasanya tak perlulah pijak mereka yang serius ni . Saya penuh dengan tanda-tanda negatif...

Saya fikir ia adalah mustahil Dalam analisis akhir, ini adalah masalah pengisihan.
Kami mengandaikan jenis quick sort digunakan (sudah tentu ia tidak menepati masalah kestabilan, saya cuma katakan di sini secara santai, jika anda mahukan kestabilan, anda boleh menggunakan pokok binari untuk menyusun), kemudian tetapkan syarat perbandingan kepada nombor ganjil lebih besar daripada nombor genap.
Tetapi adalah jelas bahawa masalah pengisihan hanya boleh menjadi O(n) dalam beberapa kes khas.
Jadi saya fikir ia adalah mustahil.

Melihat ia sebagai masalah pengisihan umum, ia mungkin kelihatan mustahil, tetapi soalan ini mempunyai tiga syarat yang sangat mendesak.
Terdapat juga beberapa syarat yang baik yang boleh diambil kesempatan daripada dua perkara penting ialah:

1. Terdapat banyak nombor ganjil seperti nombor genap, dan panjang semua tatasusunan ialah n n

2. Nombor ganjil dan genap mengekalkan susunan asalnya dan tidak perlu diisih mengikut saiz

Saya menggunakan golang untuk melaksanakan perkara berikut:

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])
        }
    }
}

Keperluan soalan asal diterjemahkan di bawah
1) Kerumitan masa adalah linear
2) Kerumitan ruang ialah O(k)
3) Kerumitan masa yang stabil
kerumitan masa ialah O( n) , yang bermaksud bahawa pengisihan perbandingan tidak lagi mungkin Kerumitan masa purata terbaik bagi pengisihan perbandingan ialah O(nlgn), seperti pengisihan cepat, dsb.
Ini sudah pun merupakan kesimpulan matematik yang terbukti secara matematik bagi "Pengenalan kepada Algoritma".
Satu-satunya yang mempunyai masa linear ialah mengira, baldi dan tapak, lihat https://www.byvoid.com/blog/sort-radix
, iaitu, pengisihan hanyalah
1) Pengiraan - kerumitan masa O(n) kerumitan ruang O(k n )

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

2) Isih baldi - O(n) kerumitan ruang O(k n)
http://www.growingwiththeweb.com/2015/06/bucket-sort.html

3) Isih Radix O(n) dan O(n k)

Jadi saya secara peribadi berpendapat soalan ini tidak mempunyai penyelesaian.
BTW: Saya cadangkan anda lihat baik-baik pautan di bawah
http://bigocheatsheet.com/

Saya sudah lama tamat sekolah, jadi saya tidak ingat perkara-perkara konklusif ini dengan jelas, bermakna saya tidak bertanggungjawab untuk perkara-perkara konklusif di atas :-)
Poster boleh memberikan bukti lanjut berdasarkan artikel di atas.

Tetapi purata kerumitan masa berdasarkan perbandingan tidak melebihi O(nlogn), jadi disyorkan untuk melihat antara tiga radix, bucket sort dan radix untuk melihat yang mana satu lebih dekat dengan anda. keperluan.

Berikut ialah jawapan kepada soalan yang serupa:

https://www.quora.com/Given-an-array-of-integers-how-do-I-re-arrange-the-numbers-such-that-odd-numbers-occupy-odd-position-and-even-numbers-occupy-even-position

Penyelesaian untuk masalah anda adalah sama, kerana hanya terdapat satu perbezaan dalam keperluan: nombor ganjil berada pada kedudukan indeks ganjil, dan nombor genap berada pada kedudukan indeks genap. Jawapan pertama dalam pautan adalah jawapan yang paling hampir dengan perkara yang anda mahukan Sebab mengapa ia hanya dekat ialah ia memerlukan tatasusunan asal boleh menampung sejumlah kecil data tambahan.

Sebenarnya, saya masih ragu-ragu bahawa mungkin terdapat syarat tersirat yang tidak dijelaskan oleh penemuduga dengan jelas kepada anda apabila bertanya soalan kepada anda Contohnya, jika tatasusunan 2n itu sendiri ialah tatasusunan tertib, situasinya akan menjadi sangat berbeza.

Selepas membaca soalan dan memikirkannya secara ringkas, ideanya adalah seperti berikut:

Jika tatasusunan yang diberikan, tiada cara untuk mengekalkan susunan relatif tidak berubah. Kod berikut hanya boleh memenuhi syarat 2 dan 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++;
    }
}

Hanya semak dari awal dan akhir, dan nilai setiap satu daripada empat situasi.

Jika senarai pautan diberikan, tiga syarat di atas mudah dipenuhi.

Satu lagi: Saya dipijak tanpa sebab. . .

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.06.md

Lihat penjelasan untuk membuat inferens daripada satu contoh.

Pautan kertas adalah seperti berikut

《PEMBAHAGIAN RUANG MINIMUM YANG STABIL DALAM MASA LINEAR》

Rasanya tiada jalan penyelesaian.

Malah artikel ini membuat andaian bahawa membandingkan nilai-f dua nombor adalah masa yang tetap Dapat difahami bahawa setiap nombor mempunyai maklumat kedudukannya sendiri.
http://www.diku.dk/~jyrki/Paper/KP1992bJ.pdf

Berikut adalah analisis saya sendiri mengenai No Solution:

Jujukan ini ialah kumpulan pilih atur Kita tahu bahawa daripada jujukan panjang n ke jujukan lain melalui pilih atur berpasangan nombor, sehingga n-1 operasi pilih atur diperlukan . Walau bagaimanapun, kerana tidak ada cara untuk mengetahui kedudukan di mana setiap nombor akan diganti (tidak ada tempat untuk menyimpannya), tidak ada cara yang jelas untuk mencari kedudukan penggantian setiap nombor dalam masa yang tetap (sebenarnya, saya lebih suka itu tidak ada perkara sedemikian) kaedah). Jadi ini tidak sepatutnya berlaku.

Tatasusunan tambahan boleh digunakan jika terdapat ruang tambahan.
Jika anda mempunyai masa tambahan, anda boleh menggunakan kaedah yang serupa dengan pengisihan gabungan, pelaksanaan bukan rekursif, kerana ia hanya membahagi ganjil dan genap, anda boleh menukarnya pada tempatnya.