前言
优先级排序是根据优先级对数组进行排序而非对数组的值排序，这不是什么新颖的排序。
比如：数组A = { 1, 2, 3, 4 }，优先级P = { 36, 3, 62, 19 };优先级越小就排在越前面，比如优先级中3最小，对应的数字是2，则2排在最前面。优先级中第二小是19，对应的数字是4，因此排序后第二个元素为4。依此类推，得到排序 { 2, 4, 1, 3 }。
方法一 vector+pair组合排序
注意的是vector排序是按照pair的first排序的，因此我们要将优先级放到first，将值放到second，让std::sort顺手牵羊。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int n = 4;
int A[n] = { 1, 2, 3, 4 };
int P[n] = { 36, 3, 62, 19 };
int main() {
vector< pair<int, int> > table;
for (int i = 0; i < n; ++i) {
table.push_back(make_pair(P[i], A[i]));
}
sort(table.begin(), table.end());
for (int i = 0; i < n; ++i) {
printf("%d ", table[i].second);
}
return 0;
}
|
方法二 改写比较函数
写class或者struct，重写比较运算符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int n = 4;
int A[n] = { 1, 2, 3, 4 };
int P[n] = { 36, 3, 62, 19 };
int main() {
struct PermutePair {
int a, p;
bool operator< (PermutePair &pp) {
return p<pp.p;
}
} table[n];
for (int i = 0; i < n; ++i) {
table[i].a = A[i];
table[i].p = P[i];
}
sort(table, table+n);
for (int i = 0; i < n; ++i) {
printf("%d ", table[i].a);
}
return 0;
}
|
