Java: 插入排序算法交换

Question

亲爱的 Whosebugers，

我的交换方法在 insertionSort 方法中不起作用；它没有交换我的数组元素。

我的插入排序算法有什么问题？

package AlgoExercises;

import java.util.Arrays;

public class InsertionSort {

  static int[] numbersArray = { 5, 2, 4, 6, 1, 3 };

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

  static void insertionSort(int[] numbersArray) {
    for (int i = 1; i < numbersArray.length - 1; i++) {
      int j = i;
      while ((j > 0) && (numbersArray[j] < numbersArray[j - 1])) {
        swap(numbersArray[j], numbersArray[j - 1]);
        j = j - 1;
        System.out.println(Arrays.toString(numbersArray));
      }
    }
  }

  public static void main(String args[]) {
    insertionSort(numbersArray);
  }
}

解决方案：

修复参数中包含 int[] 的 swap 方法后，swap 现在可以工作了！我还将 numbersArray.length-1 编辑为 numbersArray.length.

谢谢大家的帮助！

package AlgoExercises;

import java.util.Arrays;

public class InsertionSort {

  static int[] numbersArray = { 5, 2, 4, 6, 1, 3 };

  static void swap(int i, int j) {
    int temp = numbersArray[j];
    numbersArray[j] = numbersArray[i];
    numbersArray[i] = temp;
  }

  static void insertionSort(int[] numbersArray) {
    for (int i = 1; i < numbersArray.length; i++) {
      int j = i;
      while ((j > 0) && (numbersArray[j] < numbersArray[j - 1])) {
        swap(j, j - 1);
        j = j - 1;
        System.out.println(Arrays.toString(numbersArray));
      }
    }
  }

  public static void main(String args[]) {
    insertionSort(numbersArray);
  }
}

Answer 1

Java 是一种按值传递的语言，因此交换传递给 swap 方法的 int 变量没有区别。应该将数组本身+要交换的两个索引传递给方法，并在交换方法中修改数组。

static void swap(int[] arr, int i, int j) {
    int temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
}

并称之为

swap(numbersArray, j, j-1);

请注意，我没有检查您的插入排序实现的逻辑。此答案仅涉及交换问题。

Answer 2

只是给你另一种思考为什么你现有的 swap 方法不起作用的方法：如果你写这样的代码：

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

void callSwap() {
  int x = 1;
  int y = 2;

  swap(x, y);

  System.out.println(x + ", " + y);
}

您可以'inline' swap 方法，基本上是将其复制到callSwap 方法中。语义上等效的代码是：

void callSwap() {
  int x = 1;
  int y = 2;

  // Start of inlined swap method.
  {
    int a = x;
    int b = y;

    int t = a;
    a = b;
    b = t;
  }
  // End of inlined swap method.

  System.out.println(x + ", " + y);
}

希望您不会期望 x 和 y 交换值。

请注意，此行为与变量名称 a 和 b 与 x 和 y 不同这一事实无关；我只是选择它们不同。如果 swap 的参数称为 x 和 y，则在内联时有必要将它们重命名为其他名称，因为它们与 x 和 [= 完全分开16=] 在 callSwap.

Java: 插入排序算法交换

Java: Insertion Sort Algorithm Swap

java

algorithm

insertion-sort