如何在 C++ 中对向量进行排序和排序（不使用 C++11）

Question

我正在尝试构建一个函数，获取一个向量，对其进行排序，对其进行排序，然后输出排序和排序后的向量以及值的原始位置。例如：输入：[10,332,42,0.9,0] 输出：[3, 5, 4, 2, 1]

我使用这个堆栈溢出 question（特别是 Marius 的回答）作为参考指南，但是我现在被我的代码困住了，不明白问题出在哪里。我是运行 C++03。

我得到的错误之一是

error: invalid types ‘const float*[float]’ for array subscript’ for array subscript 在我的 if 声明中。

//Rank the values in a vector
std::vector<float> rankSort(const float *v_temp, size_t size)
{
    vector <float> v_sort;
    //create a new array with increasing values from 0 to n-1
    for(unsigned i = 0; i < size; i++)
    {
        v_sort.push_back(i);
    }
    bool swapped = false;
    do
    {
        for(unsigned i = 0; i < size; i++)
        {
            if(v_temp[v_sort[i]] > v_temp[v_sort[i+1]]) //error line
            {
                float temp = v_sort[i];
                v_sort[i] = v_sort[i+1];
                v_sort[i+1] = temp;
                swapped = true;
            }
        }
    }
    while(swapped);
    return v_sort;
}

std::vector<float> rankSort(const std::vector<float> &v_temp)
{
    return rankSort(&v_temp[0], v_temp.size());
}

Answer 1

v_sort[i]是一个float（它只是v_sort向量的一个元素），而只有整数类型可以用作数组下标。

可能您的意思是 v_sort 作为索引数组，因此，您应该将其声明为 std::vector<size_t> 或 std::vector<int> 类似的东西。

UP: 此外，鉴于您更改了传递的数组的值，这不是通过 const 引用传递它的优雅方式。

总而言之，以下代码在我的机器上编译正确：

std::vector<unsigned> rankSort(float *v_temp, size_t size)
{
    vector <unsigned> v_sort;
    //create a new array with increasing values from 0 to n-1
    for(unsigned i = 0; i < size; i++)
    {
        v_sort.push_back(i);
    }
    bool swapped = false;
    do
    {
        for(unsigned i = 0; i < size; i++)
        {
            if(v_temp[v_sort[i]] > v_temp[v_sort[i+1]]) //error line
            {
                unsigned temp = v_sort[i];
                v_sort[i] = v_sort[i+1];
                v_sort[i+1] = temp;
                swapped = true;
            }
        }
    }
    while(swapped);
    return v_sort;
}

std::vector<unsigned> rankSort(std::vector<float> &v_temp)
{
    return rankSort(&v_temp[0], v_temp.size());
}

Answer 2

//Rank the values in a vector
std::vector<size_t> rankSort(const std::vector<float> &v_temp)
{
    vector <size_t> v_sort;
    //create a new array with increasing values from 0 to size-1
    for(size_t i = 0; i < v_temp.size(); i++)
        v_sort.push_back(i);

    bool swapped = false;
    do
    {
        swapped = false; //it's important to reset swapped
        for(size_t i = 0; i < v_temp.size()-1; i++) // size-2 should be the last, since it is compared to next element (size-1)
            if(v_temp[v_sort[i]] > v_temp[v_sort[i+1]]) 
            {
                size_t temp = v_sort[i]; // we swap indexing array elements, not original array elements
                v_sort[i] = v_sort[i+1];
                v_sort[i+1] = temp;
                swapped = true;
            }
    }
    while(swapped);

    return v_sort;
}

Answer 3

你的问题是对排名的误解。数组索引是 size_t 而不是 float，所以你需要 return 一个 vector<size_t> 而不是 vector<float>.

也就是说你的排序是 O(n²)。如果您愿意使用更多内存，我们可以将时间减少到 O(n log(n)):

vector<size_t> rankSort(const float* v_temp, const size_t size) {
    vector<pair<float, size_t> > v_sort(size);

    for (size_t i = 0U; i < size; ++i) {
        v_sort[i] = make_pair(v_temp[i], i);
    }

    sort(v_sort.begin(), v_sort.end());

    pair<double, size_t> rank;
    vector<size_t> result(size);

    for (size_t i = 0U; i < size; ++i) {
        if (v_sort[i].first != rank.first) {
            rank = make_pair(v_sort[i].first, i);
        }
        result[v_sort[i].second] = rank.second;
    }
    return result;
}

Live Example

编辑：

是的，当使用 vector<float> 而不是 float[] 时，这实际上变得更简单了：

vector<size_t> rankSort(const vector<float>& v_temp) {
    vector<pair<float, size_t> > v_sort(v_temp.size());

    for (size_t i = 0U; i < v_sort.size(); ++i) {
        v_sort[i] = make_pair(v_temp[i], i);
    }

    sort(v_sort.begin(), v_sort.end());

    pair<double, size_t> rank;
    vector<size_t> result(v_temp.size());

    for (size_t i = 0U; i < v_sort.size(); ++i) {
        if (v_sort[i].first != rank.first) {
            rank = make_pair(v_sort[i].first, i);
        }
        result[v_sort[i].second] = rank.second;
    }
    return result;
}

Live Example

Answer 4

我建议您利用 STL 中的资源，采用更强大的解决方案。为此，我们将首先制作一个 "index vector"，即。一个 std::vector<std::size_t> v 这样对于任何 i，v[i] == i 为真：

// I'm sure there's a more elegant solution to generate this vector
// But this will do
std::vector<std::size_t> make_index_vector(std::size_t n) {
    std::vector<std::size_t> result(n, 0);
    for (std::size_t i = 0; i < n; ++i) {
        result[i] = i;
    }
    return result;
}

现在我们要做的就是根据将使用输入向量的特定比较函数对该向量进行排序。此外，为了采用最通用的方法，我们将为用户提供使用任何比较函子的机会：

template <typename T, typename A, typename Cmp>
struct idx_compare {
    std::vector<T, A> const& v;
    Cmp& cmp;
    idx_compare(std::vector<T, A> const& vec, Cmp& comp) : v(vec), cmp(comp) {}

    bool operator()(std::size_t i, std::size_t j) {
        return cmp(v[i], v[j]);
    }
};

template <typename T, typename A, typename Cmp>
std::vector<std::size_t> sorted_index_vector(std::vector<T, A> const& vec, Cmp comp) {
    std::vector<std::size_t> index = make_index_vector(vec.size());
    std::sort(index.begin(), index.end(),
        idx_compare<T, A, Cmp>(vec, comp));

    return index;
}

在排序后的索引向量中，index[0]是输入向量中最小值的索引，index[1]次小，依此类推。因此，我们需要一个额外的步骤来从中获取排名向量：

std::vector<std::size_t> get_rank_vector(std::vector<std::size_t> const& index) {
    std::vector<std::size_t> rank(index.size());
    for (std::size_t i = 0; i < index.size(); ++i) {
        // We add 1 since you want your rank to start at 1 instead of 0
        // Just remove it if you want 0-based ranks
        rank[index[i]] = i + 1;
    }
    return rank;
}

现在我们把所有的部分组合在一起：

template <typename T, typename A, typename Cmp>
std::vector<std::size_t> make_rank_vector(
    std::vector<T, A> const& vec, Cmp comp) {
    return get_rank_vector(sorted_index_vector(vec, comp));
}

// I had to stop using default template parameters since early gcc version did not support it (4.3.6)
// So I simply made another overload to handle the basic usage.
template <typename T, typename A>
std::vector<std::size_t> make_rank_vector(
    std::vector<T, A> const& vec) {
    return make_rank_vector(vec, std::less<T>());
}

[10, 332, 42, 0.9, 0] 结果：[3, 5, 4, 2, 1]。您可以在 gcc 4.3.6 上找到 Live Demo 来明确此行为。

Answer 5

这是我使用 STL 的代码，以简洁的方式获得排名。

template <typename T>
vector<size_t> calRank(const vector<T> & var) {
    vector<size_t> result(var.size(),0);
    //sorted index
    vector<size_t> indx(var.size());
    iota(indx.begin(),indx.end(),0);
    sort(indx.begin(),indx.end(),[&var](int i1, int i2){return var[i1]<var[i2];});
    //return ranking
    for(size_t iter=0;iter<var.size();++iter){
        result[indx[iter]]=iter+1;
    }
    return result;
}

如何在 C++ 中对向量进行排序和排序（不使用 C++11）

How to sort and rank a vector in C++ (without using C++11)

c++

sorting

indexing

rank

c++03