插入排序使用2个数组java

Question

我试图弄清楚如何使用插入排序来排序一组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));
}

输出是:

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

Answer 1

在查看插入排序时,首先考虑算法 -

从动画中,你应该能够知道它是就地的.考虑到这一点,我想你想要这样的东西 -

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

哪个输出,

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