删除插入排序中的重复项

Question

我基本上是在处理以下问题，我试图改变插入排序，以便它也可以删除它计数器的重复项。下面是插入排序。

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

    }

我不确定我是否正确理解了该方法。如果我理解正确（请告诉我我是否错了），该方法建议我应该在内部 while 循环开始之前遍历整个数组，并使用任意数字（例如 -1）标记任何重复项。然后当内部 while 循环开始时，它将整理数组，所有重复项将在开始时堆叠在一起。

如果是这种情况，那么我可以在插入排序开始之前简单地将数组中的每个元素相互比较，并标记任何重复项 - 1，然后插入排序将处理排序部分。之后我可以减少arraySize。

但是我觉得我没有正确理解它，所以有人可以就此提出任何建议吗？

Answer 1

您只需要在 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 到数组的末尾并且未排序。在循环的每次迭代中，您将第一个未排序的元素（即 a[i]）放入 temp 中。这是您要插入已排序部分的元素。然后将排序部分的所有元素向上移动，直到找到插入 temp 的位置。如果将 temp 更改为 -1，则您现在尝试插入的元素已变为 -1。排序算法将继续尝试在正确的位置插入 -1，即数组的开头。