```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 ``` ```#include //#include //#include //#include using namespace std; template void CountingSort(T *A, long n, long * comperisons, long * exchanges); template bool Sort(Func funcSort, T * A, long n, long * com, long * exc, long * time); int main(void) { // srand((unsigned) time(NULL)); long N = 100000; long * A = new long[N]; long com = 0; long exc = 0; long timet = 0; for(int i = 0; i < N; i++) { A[i] = i;//rand()%100000; } Sort(CountingSort, A, N, &com, &exc, &timet); cout << com << " " << exc << " ";// << time; } template void CountingSort (T *A, long n, long * comperisons, long * exchanges) { T max = A[0]; T min = A[0]; for(int i = 0; i < n; i++) { if(A[i] > max) { (*comperisons)++; max = A[i]; } if(A[i] < min) { (*comperisons)++; min = A[i]; } } int i, j; T c; T *B = (T *)calloc(max - min + 1, sizeof(T)); for (i = 0; i < n; i++) ++B[A[i] - min]; for (j = min; j <= max; ++j) { c = B[j - min]; while (c > 0) { *A = j; ++A; --c; } } free(B); } template bool Sort(Func funcSort, T * A, long n, long * com, long * exc, long * time) { // LARGE_INTEGER freq, t1, t2; // if(QueryPerformanceFrequency(&freq)) // { // QueryPerformanceCounter(&t1); funcSort(A, n, com, exc); // QueryPerformanceCounter(&t2); // time = 1000 * (t2.QuadPart - t1.QuadPart) / freq.QuadPart; return true; // } // else // { // return false; //} //} } ```
 ```1 ``` `99999 0 `