c++ - 插入排序问题？

Question

我现在正在尝试不同的排序算法以了解它们的工作原理。

我正在看这个:

template< typename Iterator >
void insertion_sort( Iterator First, Iterator Last )
{
    Iterator min = First;
    for( Iterator i = First + 1; i < Last; ++i )
        if ( *i < *min )
            min = i;

    std::iter_swap( First, min );
    while( ++First < Last )
        for( Iterator j = First; *j < *(j - 1); --j )
            std::iter_swap( (j - 1), j );
}

这是插入排序，它将它们从小到大排序，但是我有 2 个问题:

1. 反转任何比较符号不会将排序顺序更改为降序。
2. 用我自己的容器实现它时，它从不对最后一个元素进行排序。也许我不明白 Begin 和 End 应该如何为容器工作？这就是我制作它们的方式:

如果我有一个具有 unsigned int 大小和 T* 数据的动态数组容器，Begin 返回一个指向 data[0] 的迭代器，End 返回一个指向 data[size - 1] 的迭代器.如果我最终改为返回数据[大小]，它工作正常，但是如果大小等于分配的容量，那将溢出缓冲区。那么所提出的插入排序算法是不正确的吗？我从这个网站得到它:

http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Insertion_sort#C.2FC.2B.2B

Answer 1

关于问题 1:我认为如果你反转所有涉及取消引用迭代器的比较符号应该可以工作，即替换

if ( *i < *min )

通过

if ( *i > *min )

(为了避免混淆，也可以将名称“min”替换为“max”)，以及

for( Iterator j = First; *j < *(j - 1); --j )

通过

for( Iterator j = First; *j > *(j - 1); --j )

这些是对比实际数据的对比。

关于问题 2:通常，“结束”迭代器指的是您要排序的最后一个实际项目后面的位置。标准算法(例如您的算法)永远不会取消引用此迭代器，因此不会发生溢出。