插入排序算法未按预期工作

Question

我的插入排序代码是：

class insertionsort
{
    public static void main(String s[])
    {
        int []A={12,5,8,87,55,4};
        int []R=sort(A);
        for(int i=0;i<A.length;i++)
        {
            System.out.println(R[i]);
        }
    }
    static int[] sort(int A[])
    {
        int key,i,j;
        for(j=1;j<A.length;j++)
        {
            key=A[j];
            i=j-1;
            while(i>=0 && A[j]<A[i])
            {
                A[j]=A[i];
                i--;
            }
            A[i+1]=key;
        }
        return A;
    }
}

但是结果不正确。但是，如果我在 while 循环条件中将 A[j] 替换为 key 并在 while 循环主体中将 A[j] 替换为 A[i+1]，代码将生成正确的结果。 A[j]和key和A[j]和A[i+1]有区别吗？

Answer 1

正确代码：

    static void sort(int A[])
    {
         for(int j = 1; j < A.length; j++)
         {
            int key = A[j];
            int i = j;
            while(i > 0 && A[i-1] > key)
            {
                A[i] = A[i-1];
                i--;
            }
            A[i] = key;
         }
    }

请注意，您不必 return 任何操作，因为该方法本身会更改输入数组。

Q: Is there any difference in A[j] and key or A[j] and A[i+1]?

当然可以。插入排序算法的全部要点在于它将当前元素与左侧所有大于它的元素交换。把它想象成重新排列你手中的牌。在您的原始版本中，j 固定在内部循环中，不会发生重新排列。

插入排序算法未按预期工作

Insertion Sort algorithm not working as expected

java

sorting

insertion-sort