按順序排列奇數和偶數的有效方法

Question

我有類似於（1,2,3,4,5,6,7,8）的數據。我想以類似於（1,3,5， 7,2,4,6,8）在n/2-2交換中不使用任何數組，循環必須使用1或更少。

注意，我必須做的number.If現有陣列交換還有其他的方式就像沒有交換，沒有額外的陣列中使用，

請給我一些建議。

Answer 1

保持兩個指針：p1，p2。 p1從頭到尾，p2從頭到尾，並交換不匹配的元素。

僞代碼：

specialSort(array): 
    p1 <- array.start() 
    p2 <- array.end() 
    while (p1 != p2): 
    if (*p1 %2 == 0): 
     p1 <- p1 + 1; 
     continue; 
    if (*p2 %2 == 1): 
     p2 <- p2 -1; 
     continue; 
    //when here, both p1 and p2 need a swap 
    swap(p1,p2); 

注意，複雜性是O(n)，在每一個第二次迭代P1或P2的至少一個變化，因此該循環不能重複以上的2*n=O(n)倍。 [我們可以找到更好的界限，但不需要]。空間複雜度是微不足道的，我們分配一個恆定的空間量：只有2個指針。注2：如果你的語言不支持指針[即java，ml，...]，它可以用索引代替：i1從頭到尾，i2從頭到尾，採用相同的算法原則。

Answer 2

#include <stdio.h> 
#include <string.h> 

char array[26] = "ABcdEfGiHjklMNOPqrsTUVWxyZ" ; 
#define COUNTOF(a_) (sizeof(a_)/sizeof(a_)[0]) 
#define IS_ODD(e) ((e)&0x20) 
#define IS_EVEN(e) (!IS_ODD(e)) 

void doswap (char *ptr, unsigned sizl, unsigned sizr); 
int main(void) 
{ 
unsigned bot,limit,cut,top,size; 

size = COUNTOF(array); 
printf("Before:%26.26s\n", array); 

    /* pass 1 count the number of EVEN chars */ 
for (limit=top=0; top < size; top++) { 
    if (IS_EVEN(array[top])) limit++; 
    } 

    /* skip initial segment of EVEN */ 
for (bot=0; bot < limit;bot++) { 
    if (IS_ODD(array[bot])) break; 
    } 

    /* Find leading strech of misplaced ODD + trailing stretch of EVEN */ 
for (cut=bot;bot < limit; cut = top) { 
     /* count misplaced items */ 
    for ( ;cut < size && IS_ODD(array[cut]); cut++) {;} 
     /* count shiftable items */ 
    for (top=cut;top < size && IS_EVEN(array[top]); top++) {;} 

     /* Now, [bot...cut) and [cut...top) are two blocks 
     ** that need to be swapped: swap them */ 
    doswap(array+bot, cut-bot, top-cut); 
    bot += top-cut; 
    } 

printf("Result:%26.26s\n", array); 
return 0; 
} 

void doswap (char *ptr, unsigned sizl, unsigned sizr) 
{ 
if (!sizl || !sizr) return; 
if (sizl >= sizr) { 
    char tmp[sizr]; 
    memcpy(tmp, ptr+sizl, sizr); 
    memmove(ptr+sizr, ptr, sizl); 
    memcpy(ptr, tmp, sizr); 
    } 
else { 
    char tmp[sizr]; 
    memcpy(tmp, ptr, sizl); 
    memmove(ptr, ptr+sizl, sizr); 
    memcpy(ptr+sizl, tmp, sizl); 
    } 
}