删除重复内侧插入排序

我基本上处理以下问题，在我试图改变插入排序，这样也可以将其删除计数器复制品。以下是插入排序。

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

删除重复内侧插入排序

回答

相关问题