用字符串向量插入排序

我想使用插入排序來排序字符串向量。用字符串向量插入排序

這是我的代碼：

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

它給我的錯誤：如果我使用J>時0

comparison of unsigned expression >= 0 is always true

功能工作正常，但它完全忽略該字符串的第一行。

舉例來說，如果我有：

2 line1 
3 line2 
4 line3 
5 line4 
1 line5

然後它給了我：

2 line1 
1 line5 
3 line2 
4 line3 
5 line4

來源

2017-03-04 Lame Fanello

使用簽名類型。（這不是無可爭議的，但標準委員會的幾位知名成員都與我一起參與）。 –

vector<T>::size_type是by definition簽名所以j >= 0不可能是假的。您應該使用vector<T>::difference_type。

來源

2017-03-04 01:12:09

謝謝！代碼現在按預期工作。 –

類模板std::vector的類型別名size_type始終是非負整數類型。因此，epression

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()的返回類型的類型size_type混合是一個壞主意。

來源

2017-03-04 01:45:07

用字符串向量插入排序

回答

相關問題