插入排序使用2个数组java。

I am trying to figure out how to use insertion sort to sort an array of ints. I need to take values from the original array and put them into the new array. I will show what code I have, but I have hit a brick wall and cannot figure out how this sorting method works.`

我想弄明白如何使用插入排序来对int数组进行排序。我需要从原始数组中获取值并将它们放入新的数组中。我将展示我有哪些代码，但我遇到了障碍，无法理解这种排序方法是如何工作的。

import java.util.Arrays;
public static void main(String[] args)
{
int[] orgArray = {5,4,1,6,3,144,2,14};
    int[] newArray = new int[orgArray.length];
    int currentNum=0;
    for(int x=1; x<orgArray.length; x++)
    {
        if(x==1)
            newArray[0]=orgArray[0];
        else
            for(int y=x;y>0; y--)
            {
                currentNum = orgArray[x];
                if(newArray[y]<currentNum)
                {
                    for(int z=orgArray.length-2;z>y;z--)
                        newArray[z]=newArray[z+1];
                    newArray[x]=orgArray[x];
                }

            }
    }
    System.out.println("Ascending order : " + Arrays.toString(newArray));
}

The output is:

的输出是:

Ascending order : [5, 0, 14, 14, 14, 14, 14, 14]

1 个解决方案

#1

When looking at Insertion Sort, first consider the algorithm -

在研究插入排序时，首先考虑算法-

From the animation, you should be able to tell that it's in-place. With that in mind, I think you wanted something like this -

从动画中，您应该可以看出它是正确的。考虑到这一点，我认为你想要这样的东西。

int[] orgArray = { 5, 4, 1, 6, 3, 144, 2, 14 };
int[] newArray = new int[orgArray.length];
// Copy the original array.
System.arraycopy(orgArray, 0, newArray, 0,
    orgArray.length);
for (int x = 1; x < newArray.length; x++) {
  int currentNum = newArray[x]; // <-- the current number changes on every loop
  int y = x;

  // The actual condition on which to shift up!
  for (; y > 0 && newArray[y - 1] > currentNum; y--) {
    newArray[y] = newArray[y - 1];
  }
  // All shifts done, insert the correct place.
  newArray[y] = currentNum;
}
System.out.println("Ascending order : "
    + Arrays.toString(newArray));

Which outputs,

输出,

Ascending order : [1, 2, 3, 4, 5, 6, 14, 144]