c++ - 降序插入排序

Question

我一直在尝试按降序进行 InsertionSort，但一直失败得很惨。

下面是我写的代码

void InsertionSortInDecrementing(int arr[], const size_t size) {
  for (size_t i = 1; i < size; ++i) {
    int currentElement = arr[i];
    size_t previousElementIndex = i - 1;
    while (previousElementIndex > 0 && currentElement > arr[previousElementIndex]) {
      arr[previousElementIndex + 1] = arr[previousElementIndex];
      --previousElementIndex;
    }
    arr[previousElementIndex + 1] = currentElement;
  }
}

对于示例数组，最大元素确实向左移动，但最大元素卡在位置 1 并且不会移动到位置 0，如果我将 while 语句中的条件更改为 >=它会导致 C++ 中的段错误。

将不胜感激任何帮助!谢谢

Answer 1

假设你有一个像 {1, 2} 这样的数组. previousElementIndex将从 0 开始但是您的内部循环不会执行，因为第一个条件 previousElementIndex > 0在这种情况下是错误的。这就是为什么您的元素卡在位置一的原因。要解决此问题，您必须更改 >至>= ，但您还必须更改 previousElementIndex的类型为 int当它变为-1时处理。