java - 去除插入排序中的重复项

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 插入正确的位置，即数组的开头。