对数组连续排序

我有一个用户给我一个随机的对象数组，我想做一些错误检查，基本上我想让空对象位于数组的末尾，这样数组的中间是仅由非空对象组成（对象的排序无关紧要）。对数组连续排序

这是我有，它不工作。任何人都可以请帮忙。

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++; 
      } 
     } 
    } 
}

来源

2012-03-15 marcwho

这里有一个简单的方法，你如何排序这样一个数组：

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 Collections，你可以这样写用更少的代码：

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

正如Ted提到的，这在O(n log n)中执行，并创建了用于排序的阵列克隆...因此它不是最快的解决方案...

来源

2012-03-15 16:40:17

为什么O（N log N）操作更高效？该任务可以在O（N）中完成。 – 2012-03-15 16:46:03

@TedHopp：很好，你说得对。 – 2012-03-15 16:48:46

有没有必要遍历数组两次。如果你不关心非空对象的顺序（特别是如果他们不需要保持在相同的相对顺序），你可以这样做很干脆：

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

来源

2012-03-15 16:40:25

这会失败，输入：'[“x”，null，“y”，null]' – 2012-03-15 16:43:23

谢谢先生！很好地工作 – marcwho 2012-03-15 16:49:23

@DilumRanatunga我修改了代码，但是原始代码如何失败？（我只是用你的输入运行它，它工作得很好。） – 2012-03-15 16:54:29

尝试：

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

来源

2012-03-15 16:42:15

这会失败，并返回'[null，“x”，“y”，null]' – 2012-03-15 16:59:35

对数组连续排序

回答

相关问题