按顺序排列奇数和偶数的有效方法

我有类似于（1,2,3,4,5,6,7,8）的数据。我想以类似于（1,3,5， 7,2,4,6,8）在n/2-2交换中不使用任何数组，循环必须使用1或更少。按顺序排列奇数和偶数的有效方法

注意，我必须做的number.If现有阵列交换还有其他的方式就像没有交换，没有额外的阵列中使用，

请给我一些建议。

来源

2011-11-18 Robel Sharma

家庭作业？请标记，如果是这样:) [编辑：]，你的意思是“没有任何额外的数组”？否则，数据的格式是什么？ – Yuri

字符和数组。 –

保持两个指针：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从头到尾，采用相同的算法原则。

来源

2011-11-18 12:17:01 amit

请注意，订单类似于：0 6 2 4 3 5 1 7或8 2 6 4 5 3 7 1（0..7）和（1..8）输入数据范围 – MBo

@MBO：正确。如果OP希望输出排序：如果数据按示例排序，则可以每隔一个元素收集，反向并追加到每个“子列表”的末尾。这可以在'O（n）'中完成。如果数据没有排序，你不能避免'O（nlogn）'。我没有在我的答案中输入数据。 – amit

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

来源

2011-11-18 15:42:34 wildplasser

按顺序排列奇数和偶数的有效方法

回答

相关问题