c++ - 插入排序 - 处理空列表

Question

我正在尝试使用 STL 和 vector 实现插入排序。到目前为止，我想出了这个解决方案:

void insertionSort(vector<int> &v, int splitIndex);

int main() {

    //vector<int> x = {55,33,99,11,22,44};
    //vector<int> x = {55};
    //vector<int> x = {55,11};
    vector<int> x;

    insertionSort(x, 0);

    printVector(x);

    return 0; }

void insertionSort(vector<int> &v, int splitIndex) {

    vector<int>::iterator right = v.begin() + splitIndex + 1;

    if(right == v.end())
        return;

    vector<int>::iterator left = v.begin() + splitIndex;

    while(*right < *left && right != v.begin()) {
        iter_swap(right, left);
        right--;
        left--;
    }

    insertionSort(v, splitIndex+1); }

它适用于除空 vector 情况之外的所有情况，因为“右”指针将指向 vector 限制之外。我知道可以通过在开头添加条件来解决此问题:

if(v.size() < 2) return;

但我不喜欢每次递归调用都会执行此条件。

请指教。谢谢。

Answer 1

大体上是这样的说法

vector<int>::iterator right = v.begin() + splitIndex + 1;

可能会导致未定义的行为，尤其是当 vector 为空时。

这个循环

while(*right < *left && right != v.begin()) {
    iter_swap(right, left);
    right--;
    left--;
}

也可以有未定义的行为，因为在比较取消引用的迭代器之前 *right < *left你首先应该确定 right != v.begin() .否则迭代器 left将超出 vector 的有效迭代器范围。

我建议下面的函数定义

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

void insertionSort( std::vector<int> &v, std::vector<int>::size_type i = 0 )
{
    if ( i < v.size() )
    {
        auto right = std::next( v.begin(), i );
        auto left = right;

        for ( ; right != v.begin() && *right < *--left; --right ) 
        {
            std::iter_swap( right, left );
        }

        insertionSort( v, i + 1 );
    }
}


int main() 
{
    std::vector<int> v0;
    std::vector<int> v1 = { 55 };
    std::vector<int> v2 = { 55, 11 };
    std::vector<int> v3 = { 55, 33, 99, 11, 22, 44 };

    insertionSort( v0 );

    std::cout << "v0:";
    for ( int x : v0 ) std::cout << ' ' << x;
    std::cout << std::endl;

    insertionSort( v1 );

    std::cout << "v1:";
    for ( int x : v1 ) std::cout << ' ' << x;
    std::cout << std::endl;

    insertionSort( v2 );

    std::cout << "v2:";
    for ( int x : v2 ) std::cout << ' ' << x;
    std::cout << std::endl;

    insertionSort( v3 );

    std::cout << "v3:";
    for ( int x : v3 ) std::cout << ' ' << x;
    std::cout << std::endl;

    return 0;
}

程序输出为

v0:
v1: 55
v2: 11 55
v3: 11 22 33 44 55 99