c++ - 冒泡排序使用相同的输入返回不同的结果(不是基于跟踪的越界错误)

Question

我遇到了一个有趣的问题，我在处理冒泡排序问题时似乎无法解决这个问题。接受最多 25 个整数并将它们从最低值到最高值排序，然后重新打印数组。这是我编写的代码，在逻辑上可以在纸上运行:

#include <iostream>

void bubbleSort (int unsorted[25], int sorted[25], int numItems);
void getInput   (int unsorted[25], int toSort[25], int& numItems);
void printArray (int toPrint[25], int& numItems);

int main () {
  int numItems = 25;
  int unsorted[25];
  int sorted[25];

  getInput(unsorted, sorted, numItems);
  printArray(unsorted, numItems);

  bubbleSort(unsorted, sorted, numItems);

  printArray(sorted, numItems);

  return 0;
}

void bubbleSort (int unsorted[25], int sorted[25], int numItems) {
  int temp;
  for (int i = 0; i < numItems; i++)
    for (int j = 0; j < numItems - i; j++)
      if (sorted[j] > sorted[j+1]) {
        temp = sorted[j];
        sorted[j] = sorted[j+1];
        sorted[j+1] = temp;
      }
}

void getInput (int unsorted[25], int toSort[25], int& numItems) {
  int val;
  cout << "Please enter up to 25 integers, one at a time\n"
       << "If less than 25 are to be added, enter '-999' to stop\n";

  for (int i = 0; i < 25; i++) {
    cin >> val;
    if (val == -999) {
      numItems = i;
      break;
    }
    unsorted[i] = val;
    toSort[i]   = val;
  }
  cout << "\nUser input complete\n";
} 

void printArray (int toPrint[25], int& numItems) {
  for (int i = 0; i < numItems; i++)
    cout << " [" << toPrint[i] << "] ";
  cout << endl;
}

我遇到的问题是，给定相同的输入，在我的例子中，我使用 [3, 2, 4, 1, 5] 因为它是最初提示我发现错误的原因，我可以获得不同的输出。特别是这两个中的一个，我看不出有任何韵律或原因:

User input complete
[3]  [2]  [4]  [1]  [5] -> entered numbers

[0]  [1]  [2]  [3]  [4] -> sorted numbers

或:

User input complete
[3]  [2]  [4]  [1]  [5] -> entered numbers

[1]  [2]  [3]  [4]  [5] -> sorted numbers

两个输出都来自同一个编译程序，似乎只是随机决定它是否会砍掉我的最高值并将其替换为 0。我知道它实际上不是随机的，但我不知道是什么原因造成的这对我的生活。

Answer 1

在你的排序函数中，改变 for (int j = 0; j < numItems - i; j++)到 for (int j = 0; j < numItems - i - 1; j++)

因为如果i为0，就会有j < numItems , 和 sorted[j] = sorted[j+1]将超出范围。