java - 我的插入排序逻辑似乎是正确的，但不起作用

Question

我正在尝试实现插入排序。

public int[] insertionSort(int[] a) {

    for(int i=0; i<a.length;i++) {
        int j=i+1;

        while(a[j] < a[i] && j < a.length) {
            swap(a[j],a[i]);
            j--;
            i--;
        }
    }
    return a;
}

public void swap(int a, int b) {
    int temp;
    temp = a;
    a = b;
    b = temp;
}

从技术上讲，这是否与我说 j = i-1 并在 while 循环中从 j < a.length 替换为 j >= 0 的条件相同(就输出结果而言)？

Answer 1

您无法以这种方式交换另一个方法中的值，因为参数传递的是值，而不是对值的引用。

您可能最好不要使用单独的方法进行交换，如下所示(还必须递增而不是递减 i 和 j 值):

public int[] insertionSort(int[] a) {
    int temp;

    for(int i=0; i<a.length;i++) {
        int j=i;

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

编辑:必须再次更新 - while 循环中的条件顺序错误，因此它会在检查是否已到达数组末尾之前查找数组的下一个索引.

编辑 2:正如评论中提到的，我将展示如何编写一个实际有效的 swap 方法 - 而不是传递您必须传递的值整个数组并在之后返回它。我仍然可能建议按照上述方式进行操作，但仅用于教育目的:

public int[] insertionSort(int[] a) {

    for(int i=0; i<a.length;i++) {
        int j=i;

        while(j > 0 && a[j-1] > a[j]) {
            a = swap(a, j-1, j);
            j--;
        }
    }
    return a;
}


public int[] swap(int[] a, int index1, int index2) {
    int temp = a[index1];
    a[index1] = a[index2];
    a[index2] = temp;
    return a;
}

编辑3:正在做一些愚蠢的事情并且没有完全给出插入排序。现在全部排序(请原谅双关语)。