Insertion sort在Java中未正确排序。

huangapple go评论74阅读模式
英文:

Insertion sort Java not properly sorting

问题

我正在尝试自己编写冒泡排序、选择排序和插入排序算法。然而,我在插入排序部分遇到了问题。我将提供我的代码以及每行代码的作用。

public void sortMethod() {
    int count = 1;
    for (int j = 0; j < Unsorted.length - 1; j++) {
        int index = 0;
        if (Unsorted[count] < Unsorted[count - 1]) {
            int temp = Unsorted[count];
            for (int i = count; i > 0; i--) {
                if (Unsorted[i] > Unsorted[count]) {
                    index = i;
                    Unsorted[i] = Unsorted[i - 1];
                }
            }
            Unsorted[index] = Unsorted[count];
        }
        count = count + 1;
    }
}

好的,int count 是用来确定已排序数组从哪里开始的。然后我声明了 index 以找到在已排序数组后面插入元素的位置,并且声明了一个临时整数用于未排序数组的第一个元素,如果它小于已排序数组的最后一个元素。然后它将数组反转直到第一个元素,如果大于我要添加的元素,将索引赋值给它的索引。基本上,这样我就知道在哪里放置它。然后 Unsorted[I] = Unsorted[I - 1] 用于将已排序数组从未排序数组的第一个元素应该在的位置开始向后移动。然后将未排序数组的第一个元素赋值到它应该在的位置。每次增加计数。

数组:31 27 45 23 22 3 1 13 1 42
排序后的数组:27 1 1 3 22 23 1 1 1 42
构建成功(总时间:0秒)

英文:

I'm trying to program bubble sort, selection sort and insertion sort MYSELF. However, I'm having trouble with insertion sort. I'll provide my code and what each line is doing

public void sortMethod() {
    int count = 1;
    for (int j = 0; j &lt; Unsorted.length - 1; j++) {
        int index = 0;
        if (Unsorted[count] &lt; Unsorted[count - 1]) {
            int temp = Unsorted[count];
            for (int i = count; i &gt; 0; i--) {
                if (Unsorted[i] &gt; Unsorted[count]) {
                    index = i;
                    Unsorted[i] = Unsorted[i - 1];
                }
            }
            Unsorted[index] = Unsorted[count];
        }
        count = count + 1;
    }
}

Okay so int count is to figure out where the sorted array starts from. Then I declared index to find where to put the element after the sorted array and declared a temporary int for the first element of the unsorted array, if it's less than the last element of the sorted array. Then it reverses the array till the first element, and if it's greater than the element I'm adding, to assign index to its index. Essentially so I know where to place it. Then unsorted[I] = unsorted[I - 1] to shift the sorted array from where the first element of the unsorted array belongs. Then assign the first element of the unsorted array, to where it belongs. Increase the count each time

Array: 31 27 45 23 22 3 1 13 1 42 
Array after sort: 27 1 1 3 22 23 1 1 1 42 
BUILD SUCCESSFUL (total time: 0 seconds)

答案1

得分: 0

这是我修改您的代码以使其执行插入排序的最小更改量,按照我理解中的插入排序方法进行操作。请注意,您使用的整数值比必要的多,而且存在一个多余的 if 条件。我添加了许多注释来反映我修复代码时的思路,这样您就可以希望理解代码在做什么:

public class Test {
    private static int[] Unsorted = {444, 7, 22, 4, 3, 2, 1, -34, -999};

    public static void sortMethod() {

        // 我们将依次考虑数组中的每个位置。对于每一轮,
        // 'j' 指向我们已知已正确排序部分的最后一项。
        // 'j' 后面的第一项是下一个候选项。
        // 我们希望将其插入到已排序部分的正确位置。
        // 注意:第一个项永远不是候选项,因为只有一个元素的数组总是有序的。
        for (int j = 0; j < Unsorted.length - 1; j++) {
            // 保存下一个候选值,即可能无序的第一个值
            int temp = Unsorted[j + 1];

            // 将已排序部分中大于候选值的所有项向上移动一位。
            // 我们知道我们可以向上移动,因为我们已经保存了候选位置的值。
            int i = j;
            while (i >= 0 && Unsorted[i] > temp) {
                Unsorted[i + 1] = Unsorted[i];
                i = i - 1;
            }
            // 将候选项放入留下的空位中。
            // 这样插入它,使得它下面的所有元素都比它小,上面的所有元素都比它大。
            Unsorted[i + 1] = temp;

            // 现在数组已经排序到 j 指向的位置以及 j 后面的一个位置,
            // 所以我们将 j 推进一个位置,以进行下一轮操作。
        }
    }

    public static void main(String[] args) {
        sortMethod();
        for (int i = 0; i < Unsorted.length; i++)
            System.out.println(Unsorted[i]);
    }
}

结果:

-999
-34
1
2
3
4
7
22
444
英文:

Here's the minimum amount I had to change your code to get it to do an insertion sort as I understood such a sort to work. Notice that you had more integer values you were using than were necessary, and there was an extra if in there you didn't need. I put lots of comments to mirror what I was thinking as I fixed it, so you can hopefully understand what the code is doing:

public class Test
    private static int[] Unsorted = {444, 7, 22, 4, 3, 2, 1, -34, -999};

    public static void sortMethod() {

        // We&#39;ll consider each position in the array in order.  For each round,
        // &#39;j&#39; is pointing at the last item in the part of the array that we know is
        // correctly sorted.  The first item after &#39;j&#39; is the next candidate.  We
        // want to INSERT it into the right place in the part of the array that
        // is already sorted. NOTE: The first item is never a candidate because
        // an array with one element is always sorted.
        for (int j = 0; j &lt; Unsorted.length - 1; j++) {
            // save off next candidate value, the first value that may be out of order
            int temp = Unsorted[j + 1];

            // Move all the items in the sorted part of the array that are greater
            // than the candidate up one spot.  We know we have room to shift up
            // because we&#39;ve saved off the value at the candiate position.
            int i = j;
            while (i &gt;= 0 &amp;&amp; Unsorted[i] &gt; temp) {
                Unsorted[i + 1] = Unsorted[i];
                i = i - 1;
            }
            // Put the candidate in the hole that is left.  This inserts it such
            // that everything below it has a value smaller than it, and everything
            // above it has a value greater than it.
            Unsorted[i + 1] = temp;

            // Now the array is sorted up to  the position j is pointing to and one
            // beyond, so we&#39;ll advance j by one position for the next round
        }
    }

    public static void main(String[] args) {
        sortMethod();
        for (int i = 0 ; i &lt; Unsorted.length ; i++)
            System.out.println(Unsorted[i]);
    }
}

Result:

-999
-34
1
2
3
4
7
22
444

huangapple
  • 本文由 发表于 2020年9月23日 07:57:06
  • 转载请务必保留本文链接:https://go.coder-hub.com/64019164.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定