c ++选择排序与单独的最小索引函数

Question

你好我正在为我的 c++ class 做一个问题，我们要为所有类型创建一个通用选择排序函数，并使用单独的函数找到最小索引。我试图通过将两个 for 循环分成两个单独的函数来修改使用两个 for 循环的选择排序函数。我尝试了不同的方法来解决这个问题，但我只是不明白我做错了什么。请帮忙。

#include <vector>
#include <random>
#include <iostream>
#include<stdexcept>
#include<time.h>
#include <valarray>

using namespace std;

template <typename T>
unsigned min_index(const vector<T> &vals, unsigned index){
    auto min = index;
    for(auto i = index +1; i != vals.end();i++){
        if(*i < *min)
            min = i;
    }
    return min;
}

template <typename T>
void selection_sort(vector<T> &vals){
    for(auto i=vals.begin(); i!=vals.end(); i++){
        auto min = min_index(vals, i);
        swap(*i, *min);
    }
}

Answer 1

您正在尝试开发一个基于 positional-index 的 min_index（它本身已经严重损坏），然后在 iterator-based 选择排序中使用它。

template <typename T>
unsigned min_index(const vector<T> &vals, unsigned index)
{
    auto min = index; // min is 'unsigned' like 'index'

    // this loop is nonsense.
    //  'i' is unsigned (because 'index' is unsigned)
    //  'vals.end()' is an iterator, not an unsigned, therefore...
    //  'i != vals.end()` is nonsense.
    //  'min' is also unsigned, therefore...
    //  both *i and *min are nonsense.
    for(auto i = index +1; i != vals.end();i++)
    { 
        if(*i < *min)
            min = i;
    }
    return min;
}

稍后，在您的 selection-sort...

template <typename T>
void selection_sort(vector<T> &vals){
    // here 'i' is an iterator
    for(auto i=vals.begin(); i!=vals.end(); i++)
    {
        // here you're trying to pass an iterator to a function
        // expecting an unsigned. 
        auto min = min_index(vals, i);

        // and the above function is returning an unsigned
        // therefore *min is nonsense.
        swap(*i, *min);
    }
}

简而言之，这些函数 都不可能编译，更不用说工作了。

你需要选择其中之一并坚持下去。这是 C++，因此最容易实现的可能是迭代器版本。作为奖励，它最终也成为最通用的（在现代 C++ 中，迭代器字面上 无处不在 ）。例如，重写为 min_iter 的 min_index 可能如下所示：

template<class Iter>
Iter min_iter(Iter beg, Iter end)
{
    auto min = beg;
    for (; beg != end; ++beg)
    {
        if (*beg < *min)
            min = beg;
    }
    return min;
}

现在您也可以在 iterator-based selection-sort 中使用 that:

template <class Iter>
void selection_sort(Iter beg, Iter end)
{
    for (; beg != end; ++beg)
        std::iter_swap(beg, min_iter(beg, end));
}

最后，您可以通过使用标准库中的通用 std::begin 和 std::end 函数，使用通用序列抽象来解决此问题：

template<class Seq>
void selection_sort(Seq& seq)
{
    selection_sort(std::begin(seq), std::end(seq));
}

现在您可以传递向量、双端队列、数组等。几乎任何序列容器实例都可以工作，只要底层元素类型支持 operator < 本机或通过重载。

基于位置

针对您的容器类型（向量）和顺序位置而不是迭代器的类似解决方案如下所示：

template <typename T>
unsigned min_index(const std::vector<T> &vals, unsigned index)
{
    unsigned min = index;
    for (unsigned i = index + 1; i < vals.size(); i++)
    {
        if (vals[i] < vals[min])
            min = i;
    }
    return min;
}

template <typename T>
void selection_sort(std::vector<T> &vals)
{
    for (unsigned i = 0; i < vals.size(); i++)
        std::swap(vals[i], vals[min_index(vals, i)]);
}

Answer 2

这是我现在拥有的，但我在评分网站上遇到了未知错误（在我的编译器上运行良好）。使用 int 向量和双精度向量时出现未知错误，使用字符串向量时出现错误值。有人看到我应该解决的问题吗？

对于字符串：

预期：b edmb ghnh irlwv ko kuc ngpo ogrme qgls qlk rgj ryy sos uchfm uwk wus x

实际：b edmb ghnh irlwv ko qlk kuc ngpo ogrme qgls rgj ryy sos uchfm uwk x wus

template <typename T>
unsigned min_index(const vector<T> &vals, unsigned index){
    T min = vals[index];
    unsigned mindex;
    for(unsigned i = index +1; i < vals.size();i++){
        if(vals[i] < min){
            min = vals[i];
            mindex=i;
        }
    }
    
    return mindex;
}

template <typename T>
void selection_sort(vector<T> &vals){
    for(unsigned i=0; i < vals.size();  i++){
        unsigned min = min_index(vals, i);
        swap(vals[i],vals[min]);
    }
}

c ++选择排序与单独的最小索引函数

c++ selection sort with separate minimum index function

c++

sorting

minimum

data-structures

selection-sort