對數組連續排序

我有一個用戶給我一個隨機的對象數組，我想做一些錯誤檢查，基本上我想讓空對象位於數組的末尾，這樣數組的中間是僅由非空對象組成（對象的排序無關緊要）。對數組連續排序

這是我有，它不工作。任何人都可以請幫忙。

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

對數組連續排序

回答

相關問題