给定一个数组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。
有没有一种有效的方法可以让我们获得排列索引？
谢谢
问问题
15969 次
8 回答
48
创建一个索引数组，用数字 0..N-1 填充它，并使用自定义比较器对其进行排序。比较器应比较原始数组中索引lhs和处的项目rhs。以这种方式对索引数组进行排序会将它们重新排序为排列：
vector<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
注意：您可以使用按排序顺序index检索：data
for (int i = 0 ; i != index.size() ; i++) {
cout << data[index[i]] << endl;
}
于 2013-07-09T17:16:55.363 回答
6
为什么不放一些卫星数据？无需对数字进行排序，只需对成对的数字及其索引进行排序。由于排序首先在该对的第一个元素上完成，因此这不应破坏稳定的排序算法。
对于不稳定的算法，这会将其更改为稳定的算法。
但请注意，如果您尝试以这种方式排序，它会在排序时生成索引，而不是在排序之后。
此外，由于知道排列索引会导致 O(n) 排序算法，所以你不能比 O(nlogn) 更快。
于 2013-07-09T17:14:52.930 回答
4
好吧，在 C++ 中，我们可以使用对数据类型轻松地做到这一点。下面的示例代码；
arr = {5, 16, 4, 7};
vector<pair<int,int> >V;
for(int i=0;i<4;i++){
pair<int,int>P=make_pair(arr[i],i);
V.push_back(P);
}
sort(V.begin(),V.end());
所以 V[i].first 是第 i 个值，V[i].second 是第 i 个索引。所以要打印排序数组中的索引。
for(int i=0;i<4;i++)cout<<V[i].second<<endl;
请注意，在对包含对项的数组（或向量）进行排序时，数组首先根据第一个值进行排序。如果两对具有相同的第一个值，则根据它们的第二个值对它们进行排序。
于 2013-07-09T17:48:29.507 回答
1
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;
}
于 2015-12-19T11:50:56.327 回答
1
对于那些正在研究@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 链接，请删除执行策略争论。
于 2021-05-07T20:49:41.580 回答
0
我最近不得不在 PHP 中解决类似的问题。您创建一个本地比较函数供 PHP 的 UASORT 排序算法使用。在排序后的数组上调用 array_keys() ，这应该会吐出你的排列数组。
// 测试数组
$tArray = array('2', '10', '1', '23', '8', '3');
// 排序数组；维护索引关联，使用 uasort；否则使用 usort 等
uasort($tArray, 'compareSize');
// 结果键是您的排列索引（如果在上一步中使用了 uasort）
$Keys = array_keys($tArray);
// 局部比较函数
函数比较大小（$a，$b）{
if($a == $b) { 返回 0; } 其他 { 返回 ($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）
于 2017-02-18T17:31:09.957 回答
-1
是的，有一个时间。O(NlogN)由于排序O(NlogN)无论如何都需要时间，这不会影响整体时间复杂度。
时间复杂度：O(NlogN)
空间复杂度：O(N)
其中N = 输入数组中的元素数
算法：
- 制作输入数组（P）的副本，将其称为 Q。
- 对输入数组 P 进行排序。
- 对于 Q 中的每个数字，进行二进制搜索以找到 P 中该元素的索引。
于 2013-07-09T17:21:53.483 回答
-1
我认为我们可以在不使用向量的情况下解决这个问题。我是新手，老实说，我不明白你上面写的内容，你们都使用了我稍后会学习的矢量:)))（我很懒）这是我的方式：
// 首先，将数组 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]<<" ";
}
于 2017-09-26T14:50:28.770 回答