刪除重複內側插入排序

我基本上處理以下問題，在我試圖改變插入排序，這樣也可以將其刪除計數器複製品。以下是插入排序。

public void insertSort() { 

     for (int i = 1; i < nElems; i++) { 

      int temp = a[i]; 
      int j = i; 

      while (j > 0 && temp <= a[j - 1]) { 

       a[j] = a[j - 1]; 

       j--; 
      } 

      a[j] = temp; 
     } 

    }

我不確定是否正確理解了方法。如果我正確理解這一點（請告訴我，如果我錯了或不），該方法建議我應該在inner while循環開始之前遍歷整個數組，並標記任意數字（如-1）的任何副本。然後當內部while循環啓動時，它將整理數組，並將所有重複項一起堆疊起來。

如果是這種情況，那麼我可以在插入排序開始之前簡單地比較數組中的每個元素，並標記任何重複項 - 1，然後插入排序將照顧排序部分。之後我可以減少arraySize。

但是我覺得我還沒有正確理解，所以有人可以提出任何建議嗎？

來源

2014-07-24 user1010101

什麼是您正在閱讀的書的名稱？ –

Java中的數據結構和算法！ @KickButtowski關於我發佈的問題的任何建議？:) – user1010101

我即將離開我的工作稍後再看看它 –

您只需要在while循環中添加一行。

while (j > 0 && temp <= a[j - 1]) { 
    if(temp == a[j - 1]) temp = -1; 
    a[j] = a[j - 1]; 

    j--; 
}

你可以認爲數組有兩部分。第一部分從0到i-1進行排序。第二部分從我到陣列的末尾，並未排序。在循環的每次迭代中，取第一個未排序的元素（它是[i]）並將其放入temp中。這是要插入排序部分的元素。然後，將所有已排序零件的所有元素都移動到找到插入溫度的位置。如果將temp更改爲-1，那麼您現在嘗試插入的元素已變爲-1。排序算法將繼續嘗試在正確位置插入-1，這是數組的開始。

來源

2014-07-24 22:35:20 SpiderPig

有沒有可能解釋爲什麼這是行得通的？ – user1010101

好吧，我添加了一個解釋 – SpiderPig

是的，這是非常有意義的，非常漂亮。 – user1010101

public void InsertSort() 
{ 
    int t, j; 
    for (int i = 1; i < _leght; i++) 
    { 
     t = _arr[i]; 
     for (j = i; j > 0;) 
     { 
      if (_arr[j - 1] == t) t = -1; 
      if (_arr[j - 1] > t) 
      { 
        _arr[j] = _arr[j - 1]; 
        j--; 
      } 
      else break; 
     } 
     _arr[j] = t; 
    } 
}

來源

2014-10-03 10:38:34 isxaker

刪除重複內側插入排序

回答

相關問題