删除插入内部的重复项排序 [英] Removing Duplicates Inside Insertion Sort

问题描述

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

I am basically dealing with the following problem where i am trying to alter the insert sort so that it can also delete duplicates it counters. The following is the insert sort.

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循环开始时，它将对数组进行排序，并且所有重复项将在开头一起堆叠。

I am not quire sure if i have understood the approach correctly. IF i am understanding this correctly(please tell me if i am wrong or not) the approach suggests that i should iterate through the entire array before the inner while loop begins and label any duplicate with a arbitrary number such as -1. And then when the inner while loop starts it will sort out the array and all the duplicates will be stacked up at the beginning together.

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

If this is the case then i can simply compare every element in the array with each other right before the insert sort begins and label any duplicates - 1 and then the insert sort will take care of the sorting part. After which i can reduce arraySize.

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

However i feel i have not understood it correctly so can someone please make any suggestions regarding this?

推荐答案

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

You only need to add a single line to your while loop.

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

    j--;
}

您可以将阵列视为包含两部分。第一部分从0到i-1并进行排序。第二部分从i到数组的末尾，未分类。
在循环的每次迭代中，您将获取第一个未排序的元素（即[i]）并将其置于temp中。这是您要插入已排序部分的元素。然后，将已排序部分的所有元素向上移动，直到找到要插入temp的位置。
如果将temp更改为-1，那么您现在尝试插入的元素将变为-1。排序算法将继续尝试在正确的位置插入-1，这是数组的开头。

You can think of the array as having two parts. The first part goes from 0 to i-1 and is sorted. The second part goes from i to the end of the array and is unsorted. In each iteration of the loop you take the first of the unsorted elements (which is a[i]) and place it into temp. This is the element you want to insert into the sorted part. Then you shift all the elements of the sorted part up until you find the place to insert temp. If you change temp to -1, your element that you are trying to insert now has become -1. The sorting algorithm will go on to try and insert -1 at the right place, which is the beginning of the array.

这篇关于删除插入内部的重复项排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！