C++中使用insertion sort对vector排序后返回原未排序序列如何解决

核心问题原因 #

• 你当前的insertionSort函数对vector参数采用值传递，函数内部操作的是原vector的临时副本，不会对外部的原vector产生任何修改，且你调用函数时没有接收排序后返回的vector，因此输出内容和输入完全一致。
• 你之前在数组上能运行成功是因为数组传参时会自动退化为指针，函数操作的是原数组的内存空间，和vector值传递的逻辑完全不同。

注：你当前实现的是插入排序逻辑，不是你提到的选择排序，若要实现选择排序需要调整算法逻辑，下述修改针对你现有插入排序逻辑适配vector使用

修复方案 #

方案1：接收函数返回值 #

你当前的排序函数已经返回了排序后的vector，只需要在main函数中调用时将返回值赋值给原vector即可：

// 把原来的 insertionSort(v,n); 替换为下面的代码
v = insertionSort(v,n);

方案2：修改为引用传递（更高效） #

将函数的vector参数改为引用传递，函数内部直接操作原vector，不需要额外拷贝也不需要接收返回值：

// 修改函数定义的参数为引用，也可以将返回值改为void更合理
void insertionSort(vector<int>& v, int n)
{
    for(int i=1;i<=n-1;i++)
    {
        int currentEle = v[i];
        int prevEle = i-1;
        while(prevEle>=0 and v[prevEle]>currentEle){
            v[prevEle+ 1] = v[prevEle];
            prevEle = prevEle-1;
        }
       v[prevEle+1] = currentEle;
    }
}

// main中调用方式不变
insertionSort(v,n);

内容的提问来源于stack exchange，提问作者Ram Kishore