使用字符串向量进行插入排序

Question

我正在尝试使用插入排序对字符串向量进行排序。

这是我的代码：

void insertionsort(std::vector<std::string> &strings) 
{
    typedef std::vector<std::string>::size_type size_type;
    for(size_type i = 0;i < strings.size(); i++) 
    {
        std::string const tmp = strings[i];
        size_type j = i - 1;
        while(j >= 0 && tmp < strings[j]) //this is the problem
        {
            strings[j + 1]= strings[j];
            j--;

        }
        strings[j + 1]=tmp;
    }
}

它给我错误：

comparison of unsigned expression >= 0 is always true

如果我使用 j > 0，该函数工作正常。但它完全忽略了字符串的第一行。

如果我有：

2 line1
3 line2
4 line3
5 line4
1 line5

然后它给了我：

2 line1
1 line5
3 line2
4 line3
5 line4

Answer 1

vector<T>::size_type 是 by definition 无符号的，所以 j >= 0 不可能是假的。你应该使用 vector<T>::difference_type.

Answer 2

class 模板 std::vector 的类型别名 size_type 总是非负整数类型。所以压抑

j >= 0

总是正确的。

您需要的是在功能实现上做一些小的改动。很明显，只包含一个元素的向量总是被排序的。所以你应该开始索引等于 1 的外循环。

给你

#include <iostream>
#include <vector>
#include <string>

void insertionSort( std::vector<std::string> &strings ) 
{
    typedef std::vector<std::string>::size_type size_type;

    for ( size_type i = 1; i < strings.size(); ++i ) 
    {
        std::string tmp = strings[i];

        size_type j = i;

        for ( ; j !=  0 && tmp < strings[j-1]; --j )
        {
            strings[j] = strings[j-1];
        }

        if ( j != i ) strings[j] = tmp;
    }
}

int main() 
{
    std::vector<std::string> v = { "E", "D", "C", "B", "A" };

    for ( const auto &s : v ) std::cout << s << ' ';
    std::cout << std::endl;

    insertionSort( v );

    for ( const auto &s : v ) std::cout << s << ' ';
    std::cout << std::endl;
}

程序输出为

E D C B A 
A B C D E

注意这条添加的语句

if ( j != i ) strings[j] = tmp;

如果一个元素已经在向量中占据了所需的位置，那么将它分配给自己是没有意义的。这使函数更加高效。

并且将类型difference_type与类型size_type混合是一个坏主意，即成员函数size().[=19的return类型=]

使用字符串向量进行插入排序

Insertion sort with a string vector

c++

vector

insertion-sort