从vector末尾开始的插入排序实现（存在越界错误）

你的反向插入排序思路是可行的，但代码里有几个关键错误导致了越界和逻辑失效：

1. 直接导致越界的原因 #

你最后一行的赋值a[i+1] = aTemp会在i等于数组最后一个索引（a.size()-1）时，访问a[a.size()]，这超出了vector的有效索引范围（vector的索引是从0到size()-1），从而触发越界错误。

2. 核心逻辑错误 #

元素移动方向搞反 #

原代码中a[i] = a[i+1]是将右侧元素覆盖到当前位置，这会丢失当前位置的原始值，完全不符合插入排序"移动元素腾出插入位置"的逻辑。正确的做法应该是将右侧的元素向左移动一位（即a[j-1] = a[j]），这样才能为当前元素腾出向右插入的空间。

while循环条件错误 #

• 原条件i < a.size() - 1限制了遍历只能到倒数第二个元素，无法检查到最后一个元素，应该改为j < a.size()（这里我把循环变量改成j更清晰，避免混淆）；
• 比较逻辑错误：你要实现升序排列，当当前元素（key）大于右侧序列中的元素时，才需要移动该元素，这样才能让key找到正确的插入位置。原代码的aTemp < a.at(i)完全搞反了这个逻辑。

修正后的代码 #

#include <iostream>
#include <vector>
using namespace std;

void sort(vector<double> &a) {
    int n = a.size();
    // 从倒数第二个元素开始向左遍历每个未排序元素
    for (int i = n - 2; i >= 0; --i) {
        double key = a[i];
        int j = i + 1;
        // 在右侧已排序的升序序列中，找到key的插入位置
        // 将所有比key小的元素向左移动，为key腾出空间
        while (j < n && key > a[j]) {
            a[j - 1] = a[j];
            j++;
        }
        // 将key插入到正确的位置
        a[j - 1] = key;
    }
}

int main() {
    vector<double> a = {3, 2, 5, 8, 1, 9};
    sort(a);
    for (double num : a) {
        cout << num << ' ';
    }
    return 0;
}

代码运行结果 #

执行后会输出：1 2 3 5 8 9，完全符合升序要求。

这个修正后的代码遵循了反向插入排序的核心逻辑：从右往左处理每个元素，将其插入到右侧已排序的升序序列中，通过移动比当前元素小的元素腾出位置，最终完成整个数组的升序排列。

内容的提问来源于stack exchange，提问作者Erik S.