降序插入排序

Question

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

下面是我写的代码

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 时进行处理。

降序插入排序

InsertionSort in descending order

c++

algorithm

insertion-sort