Расположите 0 и 1's в массиве

Выделите второй массив (O (N)). Выполните итерации через первый массив и переместите все 1's в порядок, они появляются к второму массиву. Выполните итерации снова и переместите 0, которые оставляют в том же порядке второму массиву. Все операции O (N). Это не на месте (на месте) решение. Нестабильное решение на месте получено путем выполнения Quicksort, делящего алгоритм однажды.

После проведения некоторого исследования кажется, что известные O (N) решения без любой дополнительной памяти не стабильны. Существует научное исследование на эффективной стабильной сортировке 0-1 на месте (на месте), но решения требуют некоторой дополнительной памяти. Интересно, не был ли исходный проблемный оператор воспроизведен точным способом. Без требования устойчивости проблема очень легка; это также легко без требования на месте. С ОБОИМИ из требований (на месте, стабильный) решение, кажется, неуловимо.

Среди ответов здесь существует алгоритм, который работает в O (N) и на месте, но только если поле ключа изменяемо (2) (1) изменяемый и (2) может содержать целое число вместо единственного бита. Это работает, но не является стабильной сортировкой 0-1 на месте, потому что предполагается, что существует O (зарегистрируйте N), перезаписываемая память, доступная на элемент массива.

Вот мой (полный) удар в нем в C#. Это генерирует список и всовывает случайных сотрудников, поэтому сделайте numberOfEmployees независимо от того, что Вам нравится. Я понимаю, что существует, вероятно, более простой способ сделать это, потому что исходный плакат указал, что существует равное количество сотрудников с 0 отделами как сотрудники с 1 отделом, но я не мог помочь мне.

struct Employee
{
    public Employee(string name, int dept)
    {
        this.name = name;
        this.dept = dept;
    }

    public string name;
    public int dept;
}

class Program
{
    static void Main(string[] args)
    {
        int numberOfEmployees = 100;
        Random r = new Random();

        Employee[] emps = new Employee[numberOfEmployees];
        var empBuf = new Employee[numberOfEmployees];
        int nextAvail = 0;

        // Initialize array of employees with random data
        for (int i = 0; i < numberOfEmployees; i++)
        {
            emps[i] = new Employee("x" + i.ToString(), r.Next(0, 2));
        }

        Console.WriteLine("Old list:");
        foreach (var e in emps)
        {
            Console.WriteLine("Name: {0}, Dept: {1}", e.name, e.dept);
        }

        // throw employees with dept == 1 in first
        for (int i = 0; i < numberOfEmployees; i++)
        {
            if (emps[i].dept == 1)
            {
                empBuf[nextAvail] = emps[i];
                nextAvail++;
            }
        }

        // stick the employees with dept == 0 in last
        for (int i = 0; i < numberOfEmployees; i++)
        {
            if (emps[i].dept == 0)
            {
                empBuf[nextAvail] = emps[i];
                nextAvail++;
            }
        }


        Console.WriteLine("New list:");
        foreach (Employee e in empBuf)
        {
            Console.WriteLine("Name: {0}, Dept: {1}", e.name, e.dept);
        }

    }
}

Легкий:

function sort(array):
    new_array = new Array(array.length)
    x = 0
    for(i : array): if(i): new_array(x++) = 1
    return new_array

И если Вы на самом деле хотите иметь ту же 1 с и 0s:

function sort(array):
    new_array = new Array(array.length)
    x, y = 0, array.length / 2
    for(i : array):
        if(i): new_array(x++) = i
        else:  new_array(y++) = i
    return new_array

Моя реализация в Perl с помощью простого взвешивания.

use Modern::Perl;

my @data;
{
  use List::MoreUtils qw'natatime';
  my $iter = natatime 2, qw'
    X1  0
    X2  1
    X3  0
    X4  1
    X5  0
  ';

  while( my($a,$b) = $iter->() ){
    push @data, [$a,$b]
  }
}

my @sorted = sort {
  ($a->[1] <=> $b->[1]) * -2 + # gives more weight to second element
  ($a->[0] cmp $b->[0])
} @data;

say "Name\tDept\n";
say join "\t", @$_ for @sorted;

Name    Dept

X2      1
X4      1
X1      0
X3      0
X5      0

Вывод <=> и cmp сравнения являются значением -1,0,1.
Путем умножения одного из camparisons два мы получаем один из -2,0,2.
После добавления значения другого оператора мы получаем один из -3,-2,-1,0,1,2,3

Я хотел видеть, сколько сравнений это сделает так, я добавил некоторую отладочную информацию и придумал это.

 a           b        a1      b1     a0     b0
X1,0   ->   X2,1      0   --> 1      X1 <-  X2
X3,0   ->   X4,1      0   --> 1      X3 <-  X4
X2,1  <-    X4,1      1   -   1      X2 <-  X4
X4,1  <-    X1,0      1 <--   0      X4  -> X1
X1,0  <-    X3,0      0   -   0      X1 <-  X3
X2,1 <<-    X5,0      1 <--   0      X2 <-  X5
X5,0   ->>  X4,1      0   --> 1      X5  -> X4
X5,0   ->   X1,0      0   -   0      X5  -> X1
X5,0   ->   X3,0      0   -   0      X5  -> X3

The arrows point at the earlier value.

Какого черта, вот целое решение: прибытие является списком объектов, item.id 0 или 1, сохранен как интервал.
Этот код перемещает 0s в переднюю сторону.

count = { 0:0, 1:len(arr)/2 }
for ii in range(len( arr )):
  id = arr[ii].id
  arr[ii].id = count[id]
  count[id] += 1
for ii in range(len( arr )):
  while arr[ii].id != ii:
    T = arr[ii]
    arr[ii] = arr[arr[ii].id]
    arr[T.id] = T
for ii in range(len( arr )):
  arr[ii].id = (ii >= len(arr)/2)

В абстрактных понятиях Вы могли использовать измененный вид вставки, подкачивая все нулевые значения направо и все, что каждый оценивает налево. Это имело бы сложность больше, чем O (n), как бы то ни было.

Я немного смущен, почему, заказывая вопросы, как отправлено ранее, байты неразличимы.

Править: Новый пример помогает. Преимущество моего алгоритма, даже при том, что это медленнее, чем линейное время в худшем случае, то, что это только O (n) в использовании памяти. Начиная с тех и нулей только ключи для больших объектов (который может быть произвольно большим), память может быть беспокойством.

использование std::stable_partition вместе с std::equal_to и std::binder1st должен добиться цели хорошим, функциональным, подобным STL способом:

using namespace std
stable_partition(&array[0], &array[N], binder1st(equal_to(), 1));

Конечно, это предполагает, что элементы массива имеют некоторый определенный оператор сравнения (т.е. можно сказать array[i]==1...). Если бы они - просто целые числа, не имело бы никакого смысла поддерживать порядок...

Относительно сложности: Чтобы быть O (N), stable_partition дополнительная память потребностей. Если алгоритму не удается выделить ту дополнительную память, он работает в O (N, регистрируют N).

Это будет первым шагом вида основания.

Используемый ints вместо битов для простоты, но базового понятия является тем же. Не то, чтобы порядок другая 1 с и 0s заканчивается в вопросах!

var emps = new[] 
           {
               new Employee(X1, 0),
               new Employee(X2, 1),
               new Employee(X3, 0),
               new Employee(X4, 1),
               new Employee(X5, 0),
               new Employee(X6, 1)
           };

var sortedEmps = new Employee[bits.Length];

var oneIndex = 0;
var zeroIndex = bits.Length/2;

foreach (var employee in employees)
{
    if (employee.Dept  == 1)
        sortedEmps[oneIndex++] = employee;
    else
        sortedEmps[zeroIndex++] = employee;
}

Обновленный, чтобы сделать проблему сотрудников. Добавленный дополнительный сотрудник как исходный вопрос, сказанный там, был N/2 каждого, таким образом, должно быть четное число для этого, чтобы быть верным. Иначе это - то же.

Не уверенный это компилирует теперь, так рассматривайте его как псевдо код!

Исходный проблемный текст не упоминал никакие другие поля кроме целого числа (был отредактирован с тех пор).

В таком случае устойчивость не имеет никакого смысла, так как два равных количества в других отношениях неразличимы. Решение состоит в том, чтобы просто пересечь массив и поместить 1's n/2 времена и затем n/2 времена 0.

Вот решение, которое работает для массива int . Вы можете его изменить.

sort (int [] a) {
   int pos = 0;
   for (int i = 1; i < a.length; i++) {
       if (a[i] == 0 && a[pos] == 1) {
           swap(a, pos, i);   // this makes all 0's go to the left.
           pos++;
       }
   } 
}

#include<stdio.h>
//#include<conio.h>

int main()
{
  int i,a[20]={0};
  int *ptr1,*ptr2;
  //clrscr();
  //a[2]=a[4]=a[6]=a[8]=a[16]=1;
  a[19]=a[18]=1;

  for(i=0;i<20;i++)
    printf("%d",a[i]);

  printf("\n\nafter");

  ptr1=ptr2=a;
  for(i=0;i<20;i++)
  {
    if(*ptr1==0&&*ptr2==1)
    {
      int temp=*ptr1;*ptr1=*ptr2;*ptr2=temp;
      ptr1++;ptr2++;
    }
    else if(*ptr1==1&&*ptr2==0)
    {
      ptr1++;ptr2++;
    }
    else if(*ptr1==0&&*ptr2==0)
    {
      ptr2++;
    }
    else
    {
      if(ptr1<ptr2)
        ptr1++;
      else
      {
        ptr1++;ptr2++;
      }
    }
  }

  for(i=0;i<20;i++)
  {
    printf("%d",a[i]);
  }

 // getch();

  return 0;
}