Question

c++ 排序 给出排序后的序号

比如有一个数组[ 0.2 0.1 0.3 ]
我要的结果是[ 1 0 2 ]
即不移动原数组，只是给出排序的序号

因为我的数组数量很大，与偶20万个，所以需要一种快速算法

希望大家帮助，谢谢啦！！！！！

Answer 1

有一个想法, 之前用过, 不知道对你好不好用, 你可以参考
首先你的数组数量大, 最好一次遍历,就排好序, 这样比较节省时间
我的方案如下:
第一, 把你的数组的最小数拿出来, 扩大相应的倍数, 变成整数, 比如你的数组最小0.1, 扩大10倍,变成1, 其他类似, 变成2, 3, 这样你的数组就变成了array_pre = [2,1,3]
第二, 创建一个同样大小的数组, 这里例子为3, array[3] = [ ]{3个元素大小}
第三, 访问你原来的数组array_pre, 第一个为2, 放在你的array中的第二位位置, 然后依次访问,
最后你把所有的内容都放入你创建的array中. 这样你排好了所有的内容

最后, 你这里是需要排序的序号, 而不是排序的结果,你可以再创建一个二维的数组, 存储你刚第三步的时候, 把原来的序号放在二维的数组里面, 这样也是一次遍历, 就可以得到你想要的序号了

希望能帮到你,谢谢

追问

您这是把元素当做下标使用了，但是0.2 0.2 0.3只是举个例子，实际数组是很0.0214345这样的数。

追答

没有办法做映射吗? 数据之间的差别有多少呀

追问

么办法~~~

Answer 2

 #include "stdafx.h"
#include <Windows.h>
#include <time.h>
#include <iostream>
using namespace std;
/*上面的有些是多余的*/
#define LEN   200000
#define LINE_LEN 20
#define MAX_NUM  1000000
 void Sort(int a[], int n, int id[], int m); 
  int main(int argc, char* argv[])
 {
     int *a = new int[LEN];
     int *id = new int[LEN];  //存索引
     srand(time(NULL));
     //初始化
     for (int i=0; i<LEN; ++i)
     {
          id[i] = i;
          a[i] = rand() % MAX_NUM + MAX_NUM/10;
     } 
     DWORD s = GetTickCount();
     Sort(a, LEN, id, LEN);  //用快排
     DWORD e = GetTickCount();
     printf("\r\ntime = %d \r\n", e - s);
     return 0;
 }
 //快排
 void Sort(int a[], int n, int id[], int m)
{
 if ( m > 1)
 {
  int i = 0; 
  int j = m-1;
  int tmp = id[i];
  while(i<j)
  {
       while(j > i && a[id[j]] > a[tmp]) 
            --j;
       if (j > i)
            id[i++] = id[j];  //只改变索引顺序
       while(j > i && a[id[i]] < a[tmp])
            ++i;
       if (j > i)
            id[j--] = id[i];  //只改变索引顺序
  }
  id[i] = tmp;
  Sort(a, n, id, i);
  Sort(a, n, id + i + 1, m - i - 1);
 }
}

Answer 3

以前做图像加密的程序，也用到过排序索引；
当然用的比较笨的办法，二万数据就要3秒钟，你这20万，不行呀，会急死

Answer 4

你可以定义一个二维数组，一维里放排序数组，二维里放序号，比较排序，最后输出二维序号不就好了吗？

追问

嗯，但是过程中会移动原数组中的元素，这样很费时。
我想保持原数组不动，只移动下标。