给定一个数组
arr = {5, 16, 4, 7}sort(arr, arr+sizeof(arr)/sizeof(arr[0]))arr = {4, 5, 7, 16}{2, 0, 3, 1}arr[2]0有没有一种有效的方法可以让我们得到排列索引？
创建一个索引数组，用数字 0..N-1 填充它，并使用自定义比较器对其进行排序。比较器应比较原始数组中索引
lhsrhsvector<int> data = {5, 16, 4, 7};
vector<int> index(data.size(), 0);
for (int i = 0 ; i != index.size() ; i++) {
index[i] = i;
}
sort(index.begin(), index.end(),
[&](const int& a, const int& b) {
return (data[a] < data[b]);
}
);
for (int i = 0 ; i != index.size() ; i++) {
cout << index[i] << endl;
}
此打印
2, 0, 3, 1这是 ideone 上的演示。
注意：您可以使用
indexdatafor (int i = 0 ; i != index.size() ; i++) {
cout << data[index[i]] << endl;
}
为什么不放一些卫星数据呢？无需对数字进行排序，只需对数字对及其索引进行排序即可。由于排序首先对该对的第一个元素进行，因此这不应破坏稳定的排序算法。
对于不稳定的算法，这会将其更改为稳定的算法。
但请注意，如果您尝试以这种方式排序，它会在排序时生成索引，而不是排序后。
此外，由于知道排列索引将导致 O(n) 排序算法，所以你不能比 O(nlogn) 更快。
C++ 中的一个可能的解决方案是创建一个首先包含值和索引的容器。然后对容器进行排序。您可以使用内置的
pair<int, int>下面的示例代码；
arr = {5, 16, 4, 7};
int arr_len = sizeof(arr) / sizeof(arr[0]);
vector<pair<int,int> > value_index_pairs;
for(int i = 0; i < arr_len; ++i) {
pair<int, int> value_index_pair = make_pair(arr[i], i);
value_index_pairs.push_back(value_index_pair);
}
sort(value_index_pair.begin(), value_index_pair.end());
请注意，对首先根据其第一个值进行排序。如果出现平局，则根据第二个值对它们进行排序。
对于那些正在研究 @Sergey Kalinichenko 解决方案的类似 C++17 接口的人，下面的代码片段可能会很有用。
template <class ExecutionPolicy, typename RandomIt>
auto sort_permutation(ExecutionPolicy&& policy, RandomIt cbegin, RandomIt cend) {
auto len = std::distance(cbegin, cend);
std::vector<size_t> perm(len);
std::iota(perm.begin(), perm.end(), 0U);
std::sort(policy, perm.begin(), perm.end(),
[&](const size_t& a, const size_t& b)
{
return *(cbegin+a) < *(cbegin+b);
});
return perm;
}
你可以这样使用：
std::vector<int> a {2, 3, 1, 2, 3, 6, 8, 5};
auto r = sort_permutation(std::execution::par, a.cbegin()+1, a.cend()-1);
如果您不想与 tbb 链接，请删除执行策略争论。
Multimap 可以拯救你
template<typename TIn, typename TOut>
sortindex(const TIn &first, const TIn &last, TOut &out) {
using ValT = typename std::decay<decltype(*first)>::type;
std::multimap<ValT, size_t> sindex;
for(auto p=first; p != last; p++)
sindex.emplace(*p, std::distance(first, p));
for(auto &&p: sindex)
*out++ = p.second;
}
可以这样使用：
std::vector<size_t> a{32, 22, 45, 9, 12, 15};
std::vector<size_t> indexes;
sortindex(a.begin(), a.end(), std::back_inserter(indexes));
如果需要排序值和索引之间的耦合，则可以直接返回多重映射，而不是将索引写入输出迭代器。
template<typename TIn>
auto
sortindex(const TIn &first, const TIn &last)
--> std::multimap<typename std::decay<decltype(*first)>::type, size_t>
{ // return value can be commented out in C++14
using ValT = typename std::decay<decltype(*first)>::type;
std::multimap<ValT, size_t> sindex;
for(auto p=first; p != last; p++)
sindex.emplace(*p, std::distance(first, p));
return sindex;
}
是的，有一个需要
O(NlogN)O(NlogN)O(NlogN)O(N)算法：
我最近不得不在 PHP 中解决类似的问题。 您创建一个本地比较函数以供 PHP 的 UASORT 排序算法使用。在排序后的数组上调用 array_keys() ，这应该会输出你的排列数组。
//测试数组
$tArray = 数组('2', '10', '1', '23', '8', '3');
//对数组进行排序；维护索引关联，使用uasort；否则使用 usort 等
uasort($tArray, 'compareSize');
// 结果键是您的排列索引（如果在上一步中使用了 uasort）
$Keys = array_keys($tArray);
// 本地比较函数
函数compareSize($a, $b) {
if($a == $b) { 返回 0; } else { 返回 ($a < $b) ? -1 : 1; }
}
====================================================== ===================== 结果：
排序 =：数组 ( [2] => 1 [0] => 2 [5] => 3 [4] => 8 [1] => 10 [3] => 23 )
键 =：数组 ( [0] => 2 [1] => 0 [2] => 5 [3] => 4 [4] => 1 [5] => 3 )
我认为我们可以不使用向量来解决这个问题。 我是新手，说实话，我不明白你上面写的是什么，而且你们都使用了向量，我稍后会学习:)））（我很懒） 这是我的方法：
//首先将数组a[]复制到数组b[]
void copyarray(double b[],double a[],int n){
for(int i=0;i<n;i++)b[i]=a[i];
}
// 其次，对数组a[]进行排序（减少）
/*第三，“sorter”数组a[]，意思是：数组a[]中，如果存在相同的值，则将它们合并为一个！ 我将设置数组 o[] 为“排序数组 a[] ” */
void sorter(double o[],double a[],int n,int &dem){
int i;
o[0]=a[0];
for(i=1;i<n;i++){
if(a[i]!=a[i-1]){
dem++; o[dem]=a[i];
}
}
dem++;
}
/* 第四，我们的主要目标：获取索引：我将把索引放入数组 c[] */
void index_sort(double o[],double b[], double c[], int dem, int n){
int i,j,chiso=0;
for(j=0;j<dem;j++){
for(i=0;i<n;i++){
if(b[i]==o[j]){
c[chiso]=i;
chiso++;
}
}
}
}
// DONE!
int main(){
int n,dem=0;
double a[100],b[100],c[100],o[100];
cin>>n;
input(a,n);
copyarray(b,a,n);
copyarray(c,a,n);
sort(a,n);
sorter(o,a,n,dem);
index_sort(o,b,c,dem,n);
for(int i=0;i<n;i++) cout<<c[i]<<" ";
}