如何在C ++中对向量进行排序和排名(不使用C ++ 11) [英] How to sort and rank a vector in C++ (without using C++11)
问题描述
我正在尝试构建一个函数take take a vector,对它进行排序,对其进行排序并输出已排序和排序的向量以及值的原始位置。例如:输入:[10,332,42,0.9,0]输出:[3,5,4,2,1]
I am trying to construct a function take takes a vector, ranks it, sorts it and outputs the sorted and ranked vector with the original positioning of the values. For example: Input: [10,332,42,0.9,0] Output: [3, 5, 4, 2, 1]
我使用此堆栈溢出问题(特别是马吕斯的回答)作为参考指南,但我现在仍然坚持我的代码,不明白问题出在哪里。
我正在运行C ++ 03。
I used this stack overflow question (specifically Marius' answer) as a reference guide, however I am stuck with my code now and do not understand where the issue is. I am running a C++03.
我得到的一个错误是
错误:对于我的
的类型'const float * [float]'无效。 if
语句,数组下标'对于数组下标
error: invalid types ‘const float*[float]’ for array subscript’ for array subscript
on my if
statement.
//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());
}
推荐答案
你的问题是一个误解排名。数组索引是 size_t
而不是 float
,所以你需要返回一个向量< size_t>
不是向量< float>
。
Your problem is a misconception on rankings. Array indices are of size_t
not float
, so you'll need to return a vector<size_t>
not a vector<float>
.
那说你的排序是为O(n 2 )。如果您愿意使用更多内存,我们可以将时间缩短到 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;
}
编辑:
是的,当采用向量< float>
而不是 float [] $时,这实际上变得更简单了c $ c>:
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;
}
这篇关于如何在C ++中对向量进行排序和排名(不使用C ++ 11)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!