数组索引排序 求优化建议
- C/C++ code
/* 求优化建议 *//* 哪里不足尽管指出 */#include <cstdlib>#include <iostream>#include <vector>#include <stdlib.h>#include <time.h> using namespace std; vector<unsigned long int> a(0); //Index sortvector<unsigned long int> b(0); //Save Indexunsigned long int StartIndex = 0; //The max value's absolute distance in array in accordance with 0unsigned long int N; //The counts of array's elements unsigned long int MaxValueCounts; //The counts of filter max value will beshort int Compare(const unsigned long int &middle);void Insert(const unsigned long int &index);unsigned long int ConvertIndex(const long int index); //Calculate the absolute distance in accordance with StartIndex//fast declare unsigned long int d; //Save the value of a[i] unsigned long int CurFilterUpper; //The upper of array's filter max value unsigned long int i;//end fast declareint main(int argc, char *argv[]){ double t1,t2,duration; bool ifdo = true; unsigned long int LeftIndex,RightIndex,Middle; cout << "Please input the total of enter data value: "; cin >> N; cout << "Please input the counts of filter max value: " ; cin >> MaxValueCounts; a.resize(N + 1); b.resize(MaxValueCounts + 2); srand(time(NULL)); for (i = 1; i <= N; i++) { a[i] = rand(); } t1 = clock(); //-------------Sort data value from max to min-------------// a[0] = 0-1; b[0] = 0; b[1] = 1; for (i = 2; i <= N; ++i) { d = a[i]; LeftIndex = 1; RightIndex = CurFilterUpper = i - 1; //Save the upper of array's filter max value if (CurFilterUpper > MaxValueCounts) { RightIndex = CurFilterUpper = MaxValueCounts; } ifdo = true; do { Middle = (LeftIndex + RightIndex) / 2; switch( Compare(a[ b[ConvertIndex(Middle)] ]) ) { case 1: if (LeftIndex >= RightIndex) { Insert(Middle + 1); ifdo = false; break; } LeftIndex = Middle + 1; break; case -1: if (LeftIndex >= RightIndex) { Insert(Middle); ifdo = false; break; } RightIndex = Middle; break; case 0: Insert(Middle + 1); ifdo = false; break; }; } while (ifdo); } //------------------------Finished sort------------------------// t2 = clock(); duration = t2 - t1; cout << "Use time: " << duration << endl; system("PAUSE"); for (i = 1; i <= MaxValueCounts; i++) cout << a[ b[ConvertIndex(i)] ] << endl; system("PAUSE"); return EXIT_SUCCESS;}short int Compare(const unsigned long int &middle){ if (middle < d) return -1; if (middle > d) return 1; return 0;}void Insert(const unsigned long int &index){ long int k; unsigned long int middle = CurFilterUpper / 2; if (middle < index) { for (k = CurFilterUpper; k >= index; --k) b[ConvertIndex(k + 1)] = b[ConvertIndex(k)]; b[ConvertIndex(index)] = i; } else { b[ConvertIndex(CurFilterUpper + 1)] = b[ConvertIndex(- 1)]; for (k = 0; k <= index - 1; ++k) b[ConvertIndex(k - 1)] = b[ConvertIndex(k)]; b[ConvertIndex(index - 1)] = i; StartIndex = ConvertIndex(- 1); } return;}unsigned long int ConvertIndex(const long int index){ return (StartIndex + index + (MaxValueCounts + 1)) % (MaxValueCounts + 1); //Absolute distance base on 0 /* 应该就是上面这句，频繁调用忒别慢... */}
[解决办法]
代码风格还好。
[解决办法]
多次循环执行的地方需要优化，不然没有必要（好像是废话）
[解决办法]
楼主在练习排序算法？如果是工作需要，用个set不就可以了？何必先弄个vector，再去排序？
[解决办法]
这些类设计的有点混乱，类的定义和实现最好分开
[解决办法]
为什么不直接用 std::sort?
即使只会 c 也可以用 qsort 阿