Сортировка массива непрерывно

Question

У меня есть пользователь, который дает мне случайный массив объектов, я хочу сделать некоторую проверку ошибок, и в основном я хочу, чтобы нулевые объекты были в конце массива, чтобы середина массива состояла только ненулевые объекты (сортировка объектов не имеет значения).

Вот что у меня есть, оно не работает. Может кто-нибудь, пожалуйста, помогите.

private void properArray(){
    int i = 0;
    int j;
    int cap = theHeap.length;
    for(; i < (cap-1); i++){
        if (theHeap[i] == null){
            j = i + 1;
            while(j < (cap-1)){
                if(theHeap[j] != null){
                    theHeap[i] = theHeap[j];
                    theHeap[j] = null;
                }
                j++;  
            }
        }
    } 
}

Answer 1

Вот более простой способ сортировки такого массива:

Arrays.sort(theHeap, new Comparator() {
  public int compare(Object o1, Object o2) {
    // nulls are "greater" than non-nulls
    if (o1 == null && o2 != null) return 1;
    // non-nulls are "smaller" than nulls
    if (o1 != null && o2 == null) return -1;
    // in all other comparisons, we don't care
    return 0;
  }
});

Или с Java 8:

Arrays.sort(theHeap, (o1, o2) -> (o1 == null && o2 != null) ?  1
                               : (o1 != null && o2 == null) ? -1
                               :                               0);

Если у вас есть Коллекции Apache Commons на вашем пути к классам, вы можете написать это с еще меньшим кодом:

Arrays.sort(theHeap, new NullComparator());

Как упоминает Тед, это выполняется в O(n log n) и создает клон вашего массива для сортировки ... Таким образом, это не самое быстрое решение ...

Answer 2

Нет необходимости дважды повторять массив. Если вас не волнует порядок ненулевых объектов (в частности, если они не должны оставаться в одном и том же относительном порядке), вы можете сделать это очень просто:

int end = theHeap.length;
for (int i = 0; i < end; ++i) {
    while (theHeap[i] == null && i < end) {
        --end;
        theHeap[i] = theHeap[end];
        theHeap[end] = null;
    }
}

Поскольку каждая итерация цикла (внешняя или внутренняя) уменьшает (end - i) на единицу и цикл заканчивается, когда они встречаются, это алгоритм O (N).

РЕДАКТИРОВАТЬ Пересмотренная версия, которая позволяет не менять местами нули (возможно, немного более эффективно):

int end = theHeap.length;
for (int i = 0; i < end; ++i) {
    if (theHeap[i] == null) {
         while (--end > i && theHeap[end] == null) {
             // loop
         }
         if (i < end) {
             theHeap[i] = theHeap[end];
             theHeap[end] = null;
         }
    }
}

EDIT 2 Гораздо более простая версия, которая также поддерживает начальный порядок сортировки ненулевых элементов:

int next = 0;
for (int i = 0; i < theHeap.length; ++i) {
    if (theHeap[i] != null) {
        if (i > next) {
            theHeap[next] = theHeap[i];
            theHeap[i] = null;
        }
        ++next;
    }
}

Answer 3

Попробуйте:

int j = array.length;
for (int i = 0; i < j; ++i) {
  if (array[--j] == null) {
    continue;
  }
  // array[j] is not null.
  if (array[i] == null) {
    array[i] = array[j];
    array[j] = null;
  }
}