Эффективный способ упорядочить нечетные и четные данные последовательно

Question

У меня есть данные типа (1,2,3,4,5,6,7,8). Я хочу расположить их таким образом, как (1,3,5,7,2,4,6,8)) в свопе n / 2-2 без использования какого-либо массива, и цикл должен использовать 1 или менее.

Обратите внимание, что я должен сделать своп в существующем массиве числа. Если есть другой способ, как без свопа ибез дополнительного использования массива,

Пожалуйста, дайте мне несколько советов.

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) раз.[мы можем найти лучшую границу, но это не нужно].сложность пространства тривиальна O(1), мы выделяем постоянный объем пространства: только 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);
    }
}