c++ - sort a list and return their original order or subscript -

hi using qt writing function, in following action done:

1) sort qlist<double>;

2) return subscript of each element same order of qlist<double> or return each element's original order

for example:

original qlist: 2.3, 1.8, 4.5, 3.6 return value: 1, 0, 3, 2 (because qlist was: 1.8, 2.3, 3.6, 4.5 after sorting)

based on quick sort, have wrote 1 follows, speed slow. time cost about:

10,000 takes 13.9168

100,000 takes 120.387 secs

could give me advice optimize code? in advance.

#include <qstring> #include <qvector> #include <qdebug> #include <qtime> #include "sys/time.h"   void subarrayquicksort(qlist<double> * targetarray, qvector <qint64> * subarray, qint64 min, qint64 max);  int main(){     qlist<double> pvalue;     qvector<qint64> subscript;     qint64 totalnumber = 10000;      struct timeval tpstart,tpend;     for(qint64 =0; i< totalnumber; i++){         qsrand((uint)qtime::currenttime().msec());         double tmpnumber = 1.0 * ( qrand() % 100000 /100000 ) ;          pvalue.append(tmpnumber);         subscript.append(i);     }      qdebug() << "sort start ...";     gettimeofday(&tpstart,null);     subarrayquicksort(&pvalue,&subscript,0,totalnumber-1);      gettimeofday(&tpend,null);     qdebug() << "time cost:" << (1000000*(tpend.tv_sec-tpstart.tv_sec) + tpend.tv_usec-tpstart.tv_usec)/1000000.0;      return 0;  }  // sort subscript of array desc void subarrayquicksort(qlist<double> * targetarray, qvector <qint64> * subarray, qint64 min, qint64 max){     if(min>=max){         return;     }     qint64 first = min;     qint64 last = max;     qint64 refsub = subarray->at(first);     double refsubvalue = targetarray->at(refsub);     while (first < last) {         while (first < last && targetarray->at(subarray->at(last)) <= refsubvalue ) {             last--;         }         subarray->replace(first,subarray->at(last));          while (first < last && targetarray->at(subarray->at(first)) >= refsubvalue ) {             first++;         }         subarray->replace(last,subarray->at(first));     }     subarray->replace(first,refsub);     subarrayquicksort(targetarray,subarray,min,first - 1);     subarrayquicksort(targetarray,subarray,first + 1, max); } 

the task sort keeping track of indexes. using "sort" provided c++ stl algorithm better creating own wheel. 1 possible solution here: c++ sorting , keeping track of indexes.

to take advantage of c++11 lambda in qt, enter

config += c++11

in .pro file.

there several tricks in quick sort can slow code down. better implementation of quick sort can refer "column 11: sorting" in book "programming peals, second edition".