求高手帮忙，c++数组排序后怎么输出原先编号

Question

输入一串数组如：56 12 1 99 1000 234 33 55 99 812，进行从小到大排序
然后怎么输出排序后那个数的原先的编号即：3 2 7 8 1 4 9 6 10 5

Answer 1

1.你把数组的下标也保存到一个结构体数组中，对原数组进行排序的同时，也对那个临时数组进行同样的调换，等目标数组排序好，你的下标数组自然也排好了。


2.例如：

struct
{
int data;
size_t index;
};
排序后的index依然不变。参考代码：
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <cstdlib>
using namespace std;
struct element{
int data;
size_t index;
}array[10];
int compare(const void *a, const void *b)
{
return (*(const element*)a).data > (*(const element*)b).data;
}
int main()
{
int input[] = {56, 12, 1, 99, 1000, 234, 33, 55, 99, 812};
for (size_t i = 0; i < sizeof(input)/sizeof(input[0]); i++) {
array[i].data = input[i];
array[i].index = i + 1;
}
qsort(array, sizeof(input)/sizeof(input[0]), sizeof(array[0]), compare);
for (size_t i = 0; i < sizeof(input)/sizeof(input[0]); i++)
cout << array[i].data << "\t" << array[i].index << endl;
return 0;
}
1 3
12 2
33 7
55 8
56 1
99 4
99 9
234 6
812 10
1000 5

Answer 2

你把数组的下标也保存到一个临时数组中，对原数组进行排序的同时，也对那个临时数组进行同样的调换，等目标数组排序好，你的下标数组自然也排好了。你如过需要代码+20分我给你写，这个是最简单的方法。本回答被提问者采纳

Answer 3

这个要具体看你的数字和数组元素的多少
要是数字不太大,并且数组元素不是很多你就可以用移位计算
要是数组元素数字很大或是有很多元素就要用二维数组或是结构了
二维数组的第一行为原数组,第二行为序号
如:A[2][n]的数组其中A[0][]为原数组A[1][]编号
交换时就要
int nTemp;
for (int i=0;i<n-1;i++)
for (int j=i+1;j<n;j++)
{
if(A[0][i]>A[0][j])
{
nTemp = A[0][i];
A[0][i] = A[0][j];
A[0][j] = nTemp;
nTemp = A[1][i];
A[1][i] = A[1][j];
A[1][j] = nTemp;
}
}
排完后输出A[1][]就可以,上面的排序只是说明一下你也可以换为比较快速的方法

结构也是一样的要两个元素,一个是 数值,一个是 编号
(这个原理很简单,基本上和上面的一样,就不多说了)

可是在C++中,要是32位机int是4字节的大多的数字是不会超过大小的所以这个你可能会用到的
你的数组是int nA[n];的一个数组,
元素不超过256个,元素的数值大小不大于2^23
或是
元素不超过65536个,元素的数值大小在-32767~32768之间

为了方便我只说元素不超过256个,元素的数值大小不大于2^23 一个情况了,后面的和这个一样,你可以改一下就好了(0<n<256 && nA[i]<2^23 && nA[i]>=-2^23时可以这样)
注:这个方法不支持有重复的数字的随机输出,就是你要是有两个相同的数,先出现的一定会排前面

for(int i=0;i<n;i++)
{
nA[i]=(nA[i]<<8)+i;//为你的排序做铺垫
}
//下面你就可以对nA[n]排序了,用什么都可以
//我这里为了写来方便就先这样先了,没有优化
int nTemp;
for(int i=0;i<n-1;i++)
{
for(int j=i;j<n;j++)
{
if(nA[i]>nA[j])
{
nTemp = nA[i];
nA[i] = nA[j];
nA[j] = nA[i];
}
}
}
//然后是输出,你可以这样(只输出后8位)
for(int i=0;i<n;i++)
cout<<(nA[i]&0xff)<<endl;

这样就可以了

Answer 4

看你数组怎么定义了，最好结构题数组，例如：

struct
{
int data;
size_t index;
};

排序后的index依然不变。参考代码：

[95@~]$ cat test.cpp
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <cstdlib>
using namespace std;

struct element{
int data;
size_t index;
}array[10];

int compare(const void *a, const void *b)
{
return (*(const element*)a).data > (*(const element*)b).data;
}
int main()
{
int input[] = {56, 12, 1, 99, 1000, 234, 33, 55, 99, 812};
for (size_t i = 0; i < sizeof(input)/sizeof(input[0]); i++) {
array[i].data = input[i];
array[i].index = i + 1;
}

qsort(array, sizeof(input)/sizeof(input[0]), sizeof(array[0]), compare);

for (size_t i = 0; i < sizeof(input)/sizeof(input[0]); i++)
cout << array[i].data << "\t" << array[i].index << endl;

return 0;
}
[96@~]$ g++ -Wall test.cpp
[97@~]$ ./a.out
1 3
12 2
33 7
55 8
56 1
99 4
99 9
234 6
812 10
1000 5
[98@~]$

Answer 5

#include<iostream>
using namespace std;
void main()
{
int a[10]={56,12,1,99,1000,234,33,55,99,812};
int b[10];
int i,j,k;
for(i=k=0;i<10;i++)
{
for(j=0;j<10;j++)
{
if(a[j]<a[k])
k=j;
}
a[k]+=1000000;
b[i]=k;
}
for(i=0;i<10;i++)
{
cout << b[i]+1 << " ";
}
for(i=0;i<10;i++)
{
a[i]=a[i]%1000000;
}//还原a数组
}