权重结构的加权排序算法
权重结构的加权排序算法
开始算法之前，⾸先介绍⼀下向量中的排序⽅式，这⾥使⽤的是STL中的std::sort排序⽅式，具体使⽤的代码如下：//定义加权排序的结构
template<typename T>
struct _sortStru
{
T _data1;
T _data2;
T _data3;
T _data4;
int nWeight[4];
_sortStru()
{
memset(this, 0, sizeof(_sortStru));
}
};
bool _sort_sample(const _sortStru<int> &l, const _sortStru<int> &r)
{
return l._data1 < r._data1;
}
int main()
{
/
/ 初始化⼀个vector，成员类型为_sortStru<int>
vector< _sortStru<int> > vec;
int i = 0;
for (i = 0; i < MAXNUM; i++)
{
_sortStru<int> sort;
sort._data1 = Random();
sort._data2 = Random();
sort._data3 = Random();
sort._data4 = Random();
vec.push_back(sort);
}
// 输出
for (i = 0; i < MAXNUM; i++)
{
_sortStru<int> out;
out = vec.at(i);
cout<< out._data1<<""<<out._data2<<""<<out._data3<<""<<out._data4<<"";
cout<<endl;
}
cout<<endl;
// 简单排序，最结构体中的第⼀个成员进⾏排序
std::sort(vec.begin(), d(), _sort_sample);
for (i = 0; i < MAXNUM; i++)
{
_sortStru<int> out;
out = vec.at(i);
cout<< out._data1<<""<<out._data2<<""<<out._data3<<""<<out._data4<<"";
cout<<endl;
}
cout<<endl;
return0;
}
正⾯代码段时对vec中的_sortStru<int>成员，按照结构体中第⼀个成员进⾏排序。
下⾯给出的是对这个的加权排序
每⼀个结构体的成员都有⼀个⾃⼰的权重，结构体的定义如下：
//定义加权排序的结构
template<typename T>
struct _sortStru
T _data2;
T _data3;
T _data4;
int nWeight[4];
_sortStru()
{
memset(this, 0, sizeof(_sortStru));
}
};
在这个结构中有四个成员变量，分别任_data1 - _data4，这个四个成员都有⾃⼰的权重，⽐如_data1的权重是30，_data2的权重是20，_data3的权重是40，_data4的权重是10。然后根据这些权重对⼀组数据进⾏排序。然后将排序后的结果从⼤到⼩排列出来。
具体的排序⽅法是：
⾸先，对这组数据中的每个成员从⼩到⼤排序，具体的先对第⼀个成员进⾏从⼩到⼤排序，排好序后给这些成员添加上⾃⼰的位置权重，最⼩的为0，然后依次增加，循环的给所有的成员都添加上位置权重。
然后，对这些具有位置权重的数据进⾏加权排序。
具体代码如下：
1 #include <iostream>
2 #include <vector>
3 #include <assert.h>
4 #include <algorithm>
5#define Random() (rand()%100)
6using namespace std;
7#define MAXNUM 10
8
9//定义加权排序的结构
10 template<typename T>
11struct _sortStru
12 {
13 T _data1;
14 T _data2;
15 T _data3;
16 T _data4;
17int nWeight[4];
18 _sortStru()
19 {
20 memset(this, 0, sizeof(_sortStru));
21 }
22 };
23
24
25bool _sort_sample(const _sortStru<int> &l, const _sortStru<int> &r)
26 {
27return l._data1 < r._data1;
28 }
29
30
31class _sort
32 {
33public:
34 _sort() : pos(0){}
35 _sort(int nPos) : pos(nPos){}
36bool operator()(const _sortStru<int> &l, const _sortStru<int> &r)
37 {
38switch (pos)
39 {
40case0:
41return l._data1 < r._data1;
42case1:
43return l._data2 < r._data2;
44case2:
45return l._data3 < r._data3;
46case3:
47return l._data4 < r._data4;
48default:
49return l._data1 < r._data1;
50 }
51 }
52
53private:
54int pos;
55 };
56
57 template<class T>
58class Add_Weight
61 Add_Weight(int type, int start)
62 : ntype(type), nstart(start), nLastValue(0), nLastWeight(0)
63 {
64 }
65
66void operator()(_sortStru<T> &_F)
67 {
68switch (ntype)
69 {
70case0: default:
71if (_F._data1 == nLastValue)
72 {
73 _F.nWeight[ntype] = nLastWeight;
74 }
75else
76 {
77 _F.nWeight[ntype] = nstart;
78 nLastValue = _F._data1;
79 nLastWeight = nstart;
80 }
81break;
82case1:
83if (_F._data2 == nLastValue)
84 {
85 _F.nWeight[ntype] = nLastWeight;
86 }
87else
88 {
89 _F.nWeight[ntype] = nstart;
90 nLastValue = _F._data2;
91 nLastWeight = nstart;
92 }
93break;
94case2:
95if (_F._data3 == nLastValue)
96 {
97 _F.nWeight[ntype] = nLastWeight;
98 }
99else
100 {
101 _F.nWeight[ntype] = nstart;
102 nLastValue = _F._data3;
103 nLastWeight = nstart;
104 }
105break;
106case3:
107if (_F._data4 == nLastValue)
108 {
109 _F.nWeight[ntype] = nLastWeight;
110 }
111else
112 {
113 _F.nWeight[ntype] = nstart;
114 nLastValue = _F._data4;
115 nLastWeight = nstart;
116 }
117break;
118 }
119 nstart++;
120 }
121private:
122int ntype;
123int nstart;
124 T nLastValue;
125int nLastWeight;
126 };
127
128
129
130// 四个参数的权重类
131class CWeight
132 {
133public:
134 CWeight()
135 {
136 weight_1 = 0;
137 weight_1 = 0;
138 weight_1 = 0;
139 weight_1 = 0;
140 };
141
145 };
146
147void Check()
148 {
149 assert(weight_1 + weight_2 + weight_3 + weight_4 == 100);
150 }
151
152public:
153int weight_1;
154int weight_2;
155int weight_3;
156int weight_4;
157 };
158
159 template<class T>
160class Compare_Weight
161 {
162public:
163 Compare_Weight(CWeight *pF)
164 : pweight(pF)
165 {
166 }
167
168bool operator()(const _sortStru<T> &_F, const _sortStru<T> &_L)
169 {
170 T t1 = _F.nWeight[0] * pweight->weight_1
171 + _F.nWeight[1] * pweight->weight_2
172 + _F.nWeight[2] * pweight->weight_3
173 + _F.nWeight[3] * pweight->weight_4;
174
175 T t2 = _L.nWeight[0] * pweight->weight_1
176 + _L.nWeight[1] * pweight->weight_2
177 + _L.nWeight[2] * pweight->weight_3
178 + _L.nWeight[3] * pweight->weight_4;
179
180return t1 > t2;
181 }
182
183private:
184 CWeight *pweight;
185 };
结构体sizeof186
187int main()
188 {
189// 初始化⼀个vector，成员类型为_sortStru<int>
190 vector< _sortStru<int> > vec;
191int i = 0;
192for (i = 0; i < MAXNUM; i++)
193 {
194 _sortStru<int> sort;
195 sort._data1 = Random();
196 sort._data2 = Random();
197 sort._data3 = Random();
198 sort._data4 = Random();
199 vec.push_back(sort);
200 }
201
202// 输出
203for (i = 0; i < MAXNUM; i++)
204 {
205 _sortStru<int> out;
206out = vec.at(i);
207 cout<< out._data1<<""<<out._data2<<""<<out._data3<<""<<out._data4<<""; 208 cout<<endl;
209 }
210 cout<<endl;
211
212// 简单排序，最结构体中的第⼀个成员进⾏排序
213 std::sort(vec.begin(), d(), _sort_sample);
214for (i = 0; i < MAXNUM; i++)
215 {
216 _sortStru<int> out;
217out = vec.at(i);
218 cout<< out._data1<<""<<out._data2<<""<<out._data3<<""<<out._data4<<""; 219 cout<<endl;
220 }
221 cout<<endl;
222
223// 简单排序，最结构体中的第N个成员进⾏排序
224 std::sort(vec.begin(), d(), _sort(2));
225for (i = 0; i < MAXNUM; i++)
228out = vec.at(i);
229 cout<< out._data1<<""<<out._data2<<""<<out._data3<<""<<out._data4<<""; 230 cout<<endl;
231 }
232 cout<<endl;
233
234// 加权排序
235for (i = 0; i < 4; i++)
236 {
237 std::sort(vec.begin(), d(), _sort(i));
238 std::for_each(vec.begin(), d(), Add_Weight<int>(i, 0));
239 }
240 CWeight *weight = new CWeight(50, 50, 0, 0);
241 weight->Check();
242 std::sort(vec.begin(), d(), Compare_Weight<int>(weight));
243for (i = 0; i < MAXNUM; i++)
244 {
245 _sortStru<int> out;
246out = vec.at(i);
247 cout<< out._data1<<""<<out._data2<<""<<out._data3<<""<<out._data4<<""; 248 cout<<endl;
249 }
250 cout<<endl;
251
252return0;
253 }
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论