插入排序的实现差异

Question

我正在尝试通过使用不同语言实现不同算法来练习编程。我有两个关于插入排序的 C++ 实现的问题。首先，为什么大多数 C++ 实现都包含一个长度参数，而其他实现，例如 java，只是在 for 循环中访问数组长度？下一个问题是为什么大多数实现在 while 循环内交换变量，而不是在最后交换？我已经包含了两个实现，以便于讨论。

Java 实施：

void insertionSort(int[] arr) {
      int i, j, newValue;
      for (i = 1; i < arr.length; i++) {
            newValue = arr[i];
            j = i;
            while (j > 0 && arr[j - 1] > newValue) {
                  arr[j] = arr[j - 1];
                  j--;
            }
            arr[j] = newValue;
      }
}

C++ 实现：

void insertionSort(int arr[], int length) {
      int i, j, tmp;
      for (i = 1; i < length; i++) {
            j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                  tmp = arr[j];
                  arr[j] = arr[j - 1];
                  arr[j - 1] = tmp;
                  j--;
            }
      }
}

由于 while 循环中的交换，c++ 实现的性能似乎会更差。具体来说，是否有 C++ 不直接访问数组大小的原因，是否有必要像那样实现 while 循环，或者它只是草率的编程？先感谢您。

Answer 1

First, why do most implementations in c++ include a length parameter, while others, such as java, just access the arrays length in the for loop?

C++ 没有任何直接method/field 来访问数组的长度。在Java中，原始数组被视为对象并具有长度字段，可用于确定数组的长度。

The next question is why do most implementations swap the variable inside the while loop, instead of just swapping at the very end?

是否在循环中交换值完全取决于实现。您始终可以编写一个将移动元素的实现，然后最后将新元素放在正确的位置。这与任何特定的编程语言无关。

这是不在循环内进行交换的 C++ 实现。

void insertionSort(int arr[], int length) {
    int i, j, newValue;
    for (i = 1; i < length; i++) {
      newValue = arr[i];
      j = i;
      while (j > 0 && arr[j - 1] > newValue) {
        arr[j] = arr[j - 1];
        j--;
      }
      arr[j] = newValue;
    }
}

插入排序的实现差异

Difference in implementation for Insertion Sort

java

c++

insertion-sort