插入排序 - 处理空列表

Question

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

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); }

它适用于除空向量情况之外的所有情况，因为 "right" 指针将指向向量限制之外。我知道可以通过在开头添加条件来修复它：

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

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

请指教。谢谢

Answer 1

如果您要创建一个起始方法，它将检查数组大小，并且仅当大于 2 时，才会调用原始方法怎么办：

insertionSort(x);

将实施为：

void insertionSort(vector &v){
    if(v.size() < 2) return;
    insertionSort(v, 0);
}

Answer 2

总的来说这个说法

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

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

这个循环

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

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

我建议以下函数定义

#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

插入排序 - 处理空列表

Insertion Sort - Handling empty list

c++

sorting

recursion

vector

insertion-sort