现在的位置: 首页 > 综合 > 正文

一个c++中计算算法运行时间的程序 一个c++中计算算法运行时间的程序

2017年11月03日 ⁄ 综合 ⁄ 共 31063字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 

一个c++中计算算法运行时间的程序

分类：2010-05-08
13:14 556人阅读 评论(0) 收藏 举报

      经常在论坛上看到一些牛人测试某个算法的运行时间，有c#版的，有c++版的，而自己一个都不知道是如何实现，今天看Data Structures with C++ using STL, 2nd Edition这本书的时候看到了一个比较好的例子，上面也写到了我以前写过的排序算法，看到别人写的，汗颜不已！另外，最近看了一些老外写的代码：注释之详细，结构之清晰、这些编程风格都让我感到自己的业余，代码很长，只是大概看懂了，贴出来，和大家分享下。

1.d_random.h

[cpp] view
plaincopy

  1. #include <iostream>  
  2. #include <time.h>  
  3.   
  4. using namespace std;  
  5.   
  6. // generate random numbers  
  7. class randomNumber  
  8. {  
  9.     public:  
  10.         // initialize the random number generator  
  11.         randomNumber(long s = 0);  
  12.   
  13.         // return a 32-bit random integer m, 1 <= m <= 2^31-2  
  14.         long random();  
  15.   
  16.         // return a 32-bit random integer m, 0 <= m <= n-1,  
  17.         // where n <= 2^31-1  
  18.         long random(long n);  
  19.   
  20.         // return a real number x, 0 <= x < 1  
  21.         double frandom();  
  22.   
  23.     private:  
  24.         static const long A;  
  25.         static const long M;  
  26.         static const long Q;  
  27.         static const long R;  
  28.   
  29.         long seed;  
  30. };  
  31.   
  32. const long randomNumber::A = 48271;  
  33. const long randomNumber::M = 2147483647;  
  34. const long randomNumber::Q = M / A;  
  35. const long randomNumber::R = M % A;  
  36.   
  37. randomNumber::randomNumber(long s)  
  38. {  
  39.     if (s < 0)  
  40.         s = 0;  
  41.   
  42.     if (s == 0)  
  43.     {  
  44.         // get time of day in seconds since 12:00 AM,  
  45.         // January 1, 1970  
  46.         long t_time = time(NULL);  
  47.   
  48.         // mix-up bits by squaring  
  49.         t_time *= t_time;  
  50.         // result can overflow. handle cases  
  51.         // > 0, < 0, = 0  
  52.         if (t_time > 0)  
  53.             s = t_time ^ 0x5EECE66DL;  
  54.         else if (t_time < 0)  
  55.             s = (t_time & 0x7fffffff) ^ 0x5EECE66DL;  
  56.         else  
  57.             s = 0x5EECE66DL;  
  58.     }  
  59.   
  60.     seed = s;  
  61. }  
  62.   
  63. long randomNumber::random()  
  64. {  
  65.     long tmpSeed = A * ( seed % Q ) - R * ( seed / Q );  
  66.   
  67.     if( tmpSeed >= 0 )  
  68.          seed = tmpSeed;  
  69.     else  
  70.          seed = tmpSeed + M;  
  71.   
  72.     return seed;  
  73. }  
  74.   
  75. long randomNumber::random(long n)  
  76. {  
  77.     double fraction = double(random())/double(M);  
  78.   
  79.     return int(fraction * n);  
  80. }  
  81.   
  82. double randomNumber::frandom()  
  83. {  
  84.     return double(random())/double(M);  
  85. }  

2.d_timer.h

[cpp] view
plaincopy

  1. #ifndef TIMER_CLASS  
  2. #define TIMER_CLASS  
  3.   
  4. #include <time.h> // declares clock_t type, function clock(),  
  5.                   // and constant CLOCKS_PER_SEC  
  6.   
  7. class timer  
  8. {  
  9.    private:  
  10.   
  11.       // starting and ending time measured in clock ticks  
  12.       clock_t startTime, endTime;  
  13.   
  14.    public:  
  15.       timer();  
  16.             // initialize the timer.  
  17.             // Postconditions: set the starting and ending event times to 0.  
  18.             // this creates an event whose time is 0.0  
  19.   
  20.       void start();  
  21.             // start timing an event.  
  22.             // Postcondition:   record the current time as the starting time  
  23.         void stop();  
  24.             // stop timing an event.  
  25.             // Postconditon:    record the current time as the ending time  
  26.       double time() const;  
  27.             // return the time the event took in seconds by computing  
  28.             // the difference between the ending and starting times.  
  29. };  
  30.   
  31. // ***********************************************************  
  32. //      timer class implementation  
  33. // ***********************************************************  
  34.   
  35. // constructor. set starting and ending times to 0  
  36. timer::timer():startTime(0), endTime(0)  
  37. {}  
  38.   
  39. // determine clock ticks at start  
  40. void timer::start()  
  41. {  
  42.    startTime = clock();  
  43. }  
  44.   
  45. // determine clock ticks at end  
  46. void timer::stop()  
  47. {  
  48.    endTime = clock();  
  49. }  
  50.   
  51. // return the elapsed time in seconds  
  52. double timer::time() const  
  53. {  
  54.    return (endTime-startTime)/double(CLOCKS_PER_SEC);  
  55. }  
  56.   
  57. #endif   // TIMER_CLASS  

3.d_search.h

[cpp] view
plaincopy

  1. #ifndef SEARCH_FUNCTIONS  
  2. #define SEARCH_FUNCTIONS  
  3.   
  4. #include <vector>  
  5. #include <list>  
  6.   
  7. using namespace std;  
  8.   
  9. // perform a sequential search of an integer array for a target  
  10. // in the index range [first, last). return the index of a  
  11. // match or last if the target is not in arr  
  12. int seqSearch(const int arr[], int first, int last, int target);  
  13.   
  14. // perform  asequential search for a target in the index range  
  15. // [first, last).  return the index of a match or last if the  
  16. // target is not in arr  
  17. template <typename T>  
  18. int seqSearch(const T arr[], int first, int last, const T& target);  
  19.   
  20. // perform a binary search of an integer array for a target  
  21. // in the index range [first, last). return the index of a  
  22. // match or last if the target is not in arr  
  23. int binSearch(const int arr[], int first, int last, int target);  
  24.   
  25. // perform a binary search of an array for a target  
  26. // in the index range [first, last). return the index of a  
  27. // match or last if the target is not in arr  
  28. template <typename T>  
  29. int binSearch(const T arr[], int first, int last, const T& target);  
  30.   
  31. // vector version of the sequential search  
  32. template <typename T>  
  33. int seqSearch(const vector<T>& v, int first, int last, const T& target);  
  34.   
  35. // vector version of the binary search  
  36. template <typename T>  
  37. int binSearch(const vector<T>& v, int first, int last, const T& target);  
  38.   
  39. // perform the sequential search for target in the list  
  40. // iterator range [first, last). return an iterator pointing  
  41. // at the target in the list or last if target is not found  
  42. template <typename T>  
  43. typename list<T>::iterator seqSearch(typename list<T>::iterator first,  
  44.                                      typename list<T>::iterator last, const T& target);  
  45.   
  46. // perform the sequential search for target in the container  
  47. // iterator range [first, last). return an iterator pointing  
  48. // at the target in the container or last if target is not  
  49. // found  
  50. template <typename Iterator, typename T>  
  51. Iterator find(Iterator first, Iterator last, const T& target);  
  52.   
  53. // ***********************************************************  
  54. //      search function implementations  
  55. // ***********************************************************  
  56.   
  57. int seqSearch(const int arr[], int first, int last, int target)  
  58. {  
  59.     int i;  
  60.   
  61.    // scan indices in the range first <= i < last  
  62.     for(i=first; i < last; i++)  
  63.         if (arr[i] == target)  
  64.             return i;               // immediately return on a match  
  65.   
  66.     return last;                    // return last if target not found  
  67. }  
  68.   
  69. template <typename T>  
  70. int seqSearch(const T arr[], int first, int last, const T& target)  
  71. {  
  72.     int i;  
  73.   
  74.    // scan indices in the range first <= i < last  
  75.     for(i=first; i < last; i++)  
  76.         if (arr[i] == target)   // assume T has the "==" operator  
  77.             return i;               // immediately return on a match  
  78.   
  79.     return last;                    // return last if target not found  
  80. }  
  81.   
  82. int binSearch(const int arr[], int first, int last, int target)  
  83. {  
  84.     int mid;                        // index of the midpoint  
  85.     int midValue;               // object that is assigned arr[mid]  
  86.     int origLast = last;        // save original value of last  
  87.       
  88.     while (first < last)     // test for nonempty sublist  
  89.     {  
  90.         mid = (first+last)/2;  
  91.         midValue = arr[mid];  
  92.         if (target == midValue)  
  93.             return mid;         // have a match  
  94.       // determine which sublist to search  
  95.         else if (target < midValue)  
  96.             last = mid;         // search lower sublist. reset last  
  97.         else  
  98.             first = mid+1;      // search upper sublist. reset first  
  99.     }  
  100.   
  101.     return origLast;            // target not found  
  102. }  
  103.   
  104. template <typename T>  
  105. int binSearch(const T arr[], int first, int last, const T& target)  
  106. {  
  107.     int mid;                        // index of the midpoint  
  108.     T midValue;                 // object that is assigned arr[mid]  
  109.     int origLast = last;        // save original value of last  
  110.       
  111.     while (first < last)     // test for nonempty sublist  
  112.     {  
  113.         mid = (first+last)/2;  
  114.         midValue = arr[mid];  
  115.         if (target == midValue)  
  116.             return mid;         // have a match  
  117.       // determine which sublist to search  
  118.         else if (target < midValue)  
  119.             last = mid;         // search lower sublist. reset last  
  120.         else  
  121.             first = mid+1;      // search upper sublist. reset first  
  122.     }  
  123.   
  124.     return origLast;            // target not found  
  125. }  
  126.   
  127. template <typename T>  
  128. int seqSearch(const vector<T>& v, int first, int last, const T& target)  
  129. {  
  130.     int i;  
  131.   
  132.    // scan indices in the range first <= i < last  
  133.     for(i=first; i < last; i++)  
  134.         if (v[i] == target)     // assume T has the "==" operator  
  135.             return i;               // immediately return on a match  
  136.   
  137.     return last;                    // otherwise return last  
  138. }  
  139.   
  140. template <typename T>  
  141. int binSearch(const vector<T>& v, int first, int last, const T& target)  
  142. {  
  143.     int mid;                        // index of the midpoint  
  144.     T midvalue;                 // object that is assigned v[mid]  
  145.     int origLast = last;        // save original value of last  
  146.       
  147.     while (first < last)     // test for nonempty sublist  
  148.     {  
  149.         mid = (first+last)/2;  
  150.         midvalue = v[mid];  
  151.         if (target == midvalue)  
  152.             return mid;         // have a match  
  153.       // determine which sublist to search  
  154.         else if (target < midvalue)  
  155.             last = mid;         // search lower sublist. reset last  
  156.         else  
  157.             first = mid+1;      // search upper sublist. reset first  
  158.     }  
  159.   
  160.     return origLast;            // target not found  
  161. }  
  162.   
  163. template <typename T>  
  164. typename list<T>::iterator seqSearch(typename list<T>::iterator first,  
  165.                                      typename list<T>::iterator last, const T& target)  
  166. {  
  167.     // start at location first  
  168.     list<T>::iterator iter = first;  
  169.   
  170.     // compare list elements with item until either  
  171.     // we arrive at last or locate item   
  172.     while(iter != last && !(*iter == target))  
  173.         iter++;  
  174.   
  175.     // iter either points at item or is last  
  176.     return iter;  
  177. }  
  178.   
  179. template <typename Iterator, typename T>  
  180. Iterator find(Iterator first, Iterator last, const T& target)  
  181. {  
  182.     Iterator iter = first;  
  183.   
  184.     // scan iterator range [first, last), stopping  
  185.     // if the loop locates target  
  186.     while (iter != last && *iter != target)  
  187.         iter++;  
  188.   
  189.     // if target located, iter points at it; otherwise  
  190.     // is has value last  
  191.     return iter;  
  192. }  
  193.   
  194. #endif   // SEARCH_FUNCTIONS  

4.d_heap.h

[cpp] view
plaincopy

  1. #ifndef HEAP_FUNCTIONS  
  2. #define HEAP_FUNCTIONS  
  3.   
  4. #include <vector>  
  5. #include <functional>  
  6.   
  7. using namespace std;  
  8.   
  9. // the vector elements in the range [0, last-1) are a heap.  
  10. // insert the element v[last-1] into the heap so that the  
  11. // range [0, last) is a heap. use the function object comp  
  12. // to perform comparisons  
  13. template <typename T, typename Compare>  
  14. void pushHeap(vector<T>& v, int last, Compare comp);  
  15.   
  16. // filter the vector element v[first] down the heap with index  
  17. // range [first, last)  
  18. template <typename T, typename Compare>  
  19. void adjustHeap(vector<T>& v, int first, int last, Compare comp);  
  20.   
  21. // the vector elements in the range [0, last) are a heap.  
  22. // swap the first and last elements of the heap and then  
  23. // make the elements in the index range [0, last-1) a heap.  
  24. // use the function object comp to perform comparisons  
  25. template <typename T, typename Compare>  
  26. void popHeap(vector<T>& v, int last, Compare comp);  
  27.   
  28. // arrange the vector elements into a heap. use the function  
  29. // object comp to perform comparisons  
  30. template <typename T, typename Compare>  
  31. void makeHeap(vector<T>& v, Compare comp);  
  32.   
  33. // implementations  
  34.   
  35. template <typename T, typename Compare>  
  36. void pushHeap(vector<T>& v, int last, Compare comp)  
  37. {  
  38.     // assume the new item is at location v[last-1] and that  
  39.     // the elements v[0] to v[last-2] are in heap order  
  40.     int currentPos, parentPos;  
  41.     T target;  
  42.   
  43.     // currentPos is an index that traverses path of parents.  
  44.     // target is value hlist[i] and is repositioned in path  
  45.     currentPos = last-1;  
  46.     parentPos = (currentPos-1)/2;  
  47.     target = v[last-1];  
  48.   
  49.     // traverse path of parents up to the root  
  50.     while (currentPos != 0)  
  51.     {  
  52.         // compare target and parent value  
  53.         if (comp(target,v[parentPos]))  
  54.         {  
  55.             // move data from parent position to current  
  56.             // position. update current position to parent  
  57.             // position. compute next parent  
  58.             v[currentPos] = v[parentPos];  
  59.             currentPos = parentPos;  
  60.             parentPos = (currentPos-1)/2;  
  61.         }  
  62.         else  
  63.             // if !comp(target, parentvalue), heap condition is ok. break  
  64.             break;  
  65.     }  
  66.     // the correct location has been discovered. assign target  
  67.     v[currentPos] = target;  
  68. }  
  69.   
  70.   
  71. template <typename T, typename Compare>  
  72. void adjustHeap(vector<T>& v, int first, int last, Compare comp)  
  73. {  
  74.     int currentPos, childPos;  
  75.     T target;  
  76.   
  77.     // start at first and filter target down the heap  
  78.     currentPos = first;  
  79.     target = v[first];  
  80.   
  81.     // compute the left child index and begin a scan down  
  82.     // path of children, stopping at end of list (last)  
  83.     // or when we find a place for target  
  84.     childPos = 2 * currentPos + 1;  
  85.     while (childPos <= last-1)  
  86.     {  
  87.         // index of right child is childPos+1. compare the  
  88.         // two children. change childPos if  
  89.         // comp(v[childPos+1], v[childPos]) is true  
  90.         if ((childPos+1 <= last-1) &&  
  91.             comp(v[childPos+1], v[childPos]))  
  92.             childPos = childPos + 1;  
  93.   
  94.         // compare selected child to target  
  95.         if (comp(v[childPos],target))  
  96.         {  
  97.             // comp(selected child, target) is true.  
  98.             // move selected child to the parent;  
  99.             // position of selected child is now vacated  
  100.             v[currentPos] = v[childPos];  
  101.   
  102.             // update indices to continue the scan  
  103.             currentPos = childPos;  
  104.             childPos = 2 * currentPos + 1;  
  105.         }  
  106.         else  
  107.             // target belongs at currentPos  
  108.             break;  
  109.     }  
  110.     v[currentPos] = target;  
  111. }  
  112.   
  113. template <typename T, typename Compare>  
  114. void popHeap(vector<T>& v, int last, Compare comp)  
  115. {  
  116.     T temp;  
  117.   
  118.     // exchange the first and last element in the heap  
  119.     temp = v[0];  
  120.     v[0] = v[last-1];  
  121.     v[last-1] = temp;  
  122.   
  123.     // filter down the root over the range [0, last-1)  
  124.     adjustHeap(v, 0, last-1, comp);  
  125. }  
  126.   
  127. template <typename T, typename Compare>  
  128. void makeHeap(vector<T>& v, Compare comp)  
  129. {  
  130.     int heapPos, lastPos;  
  131.   
  132.     // compute the size of teh heap and the index  
  133.     // of the last parent  
  134.     lastPos = v.size();  
  135.     heapPos = (lastPos - 2)/2;  
  136.   
  137.     // filter down every parent in order from last parent  
  138.     // down to root  
  139.     while (heapPos >= 0)  
  140.     {  
  141.         adjustHeap(v,heapPos, lastPos, comp);  
  142.         heapPos--;  
  143.     }  
  144. }  
  145.   
  146. #endif  // HEAP_FUNCTIONS  

5.d_sort.h

[cpp] view
plaincopy

  1. #ifdef __BORLANDC__  
  2. // turn off Borland warning message about comparison of signed and  
  3. // unsigned values  
  4. #pragma warn -8012  
  5. #endif  // __BORLANDC__  
  6.   
  7. #ifndef SORTING_ALGORITHMS  
  8. #define SORTING_ALGORITHMS  
  9.   
  10. #include <vector>  
  11. #include <queue>  
  12.   
  13. #include "d_heap.h" // heap function library  
  14.   
  15. using namespace std;  
  16.   
  17. // sort an integer array using selection sort  
  18. void selectionSort(int arr[], int n);  
  19.   
  20. // sort an array of type T using selection sort  
  21. template <typename T>  
  22. void selectionSort(T arr[], int n);  
  23.   
  24. // sort a vector of type T using selection sort  
  25. template <typename T>  
  26. void selectionSort(vector<T>& v);  
  27.   
  28. // sort a vector of type T using insertion sort  
  29. template <typename T>  
  30. void insertionSort(vector<T>& v);  
  31.   
  32. // sort the elements of a vector of type T in the range  
  33. // [first, last) using insertion sort  
  34. template <typename T>  
  35. void insertionSort(vector<T>& v, int first, int last);  
  36.   
  37. // sort v using the radix sort. each integer has d digits  
  38. void radixSort(vector<int>& v, int d);  
  39.   
  40. // sort a vector using heapsort  
  41. template <typename T, typename Compare>  
  42. void heapSort (vector<T>& v, Compare comp);  
  43.   
  44. // the elements in the ranges [first,mid) and [mid,last) are  
  45. // ordered. the function merges the ordered sequences into  
  46. // an ordered sequence in the range [first,last)  
  47. template <typename T>  
  48. void merge(vector<T>& v, int first, int mid, int last);  
  49.   
  50. // sorts v in the index range [first,last) by merging  
  51. // ordered sublists  
  52. template <typename T>  
  53. void mergeSort(vector<T>& v, int first, int last);  
  54.   
  55. // using the value at the midpoint of [first,last) as the pivot,  
  56. // locate the pivot in its final location so all elements  
  57. // to its left are <= to its value and all elements to the  
  58. // right are >= to its value. return the index of the pivot  
  59. template <typename T>  
  60. int pivotIndex(vector<T>& v, int first, int last);  
  61.   
  62. // sort a vector using quicksort  
  63. template <typename T>  
  64. void quicksort(vector<T>& v, int first, int last);  
  65.   
  66. // locate the kth largest element of v at index k  
  67. template <typename T>  
  68. void findK(vector<T>& v, int first, int last, int k);  
  69.   
  70. // IMPLEMENTATIONS  
  71.   
  72. void selectionSort(int arr[], int n)  
  73. {  
  74.    int smallIndex; // index of smallest element in the sublist  
  75.    int pass, j;  
  76.     int temp;  
  77.   
  78.    // pass has the range 0 to n-2  
  79.    for (pass = 0; pass < n-1; pass++)  
  80.    {  
  81.         // scan the sublist starting at index pass  
  82.         smallIndex = pass;  
  83.   
  84.         // j traverses the sublist arr[pass+1] to arr[n-1]  
  85.         for (j = pass+1; j < n; j++)  
  86.          // update if smaller element found  
  87.             if (arr[j] < arr[smallIndex])  
  88.                 smallIndex = j;  
  89.   
  90.         // if smallIndex and pass are not the same location,  
  91.         // exchange the smallest item in the sublist with arr[pass]  
  92.         if (smallIndex != pass)  
  93.         {  
  94.             temp = arr[pass];  
  95.             arr[pass] = arr[smallIndex];  
  96.             arr[smallIndex] = temp;  
  97.         }  
  98.     }  
  99. }  
  100.   
  101. template <typename T>  
  102. void selectionSort(T arr[], int n)  
  103. {  
  104.    int smallIndex; // index of smallest element in the sublist  
  105.    int pass, j;  
  106.     T temp;  
  107.   
  108.    // pass has the range 0 to n-2  
  109.    for (pass = 0; pass < n-1; pass++)  
  110.    {  
  111.         // scan the sublist starting at index pass  
  112.         smallIndex = pass;  
  113.   
  114.         // j traverses the sublist arr[pass+1] to arr[n-1]  
  115.         for (j = pass+1; j < n; j++)  
  116.          // update if smaller element found  
  117.             if (arr[j] < arr[smallIndex])  
  118.                 smallIndex = j;  
  119.   
  120.         // if smallIndex and pass are not the same location,  
  121.         // exchange the smallest item in the sublist with arr[pass]  
  122.         if (smallIndex != pass)  
  123.         {  
  124.             temp = arr[pass];  
  125.             arr[pass] = arr[smallIndex];  
  126.             arr[smallIndex] = temp;  
  127.         }  
  128.     }  
  129. }  
  130.   
  131. template <typename T>  
  132. void selectionSort(vector<T>& v)  
  133. {  
  134.    // index of smallest item in each pass  
  135.     int smallIndex;  
  136.     // save the vector size in n  
  137.     int pass, j, n = v.size();  
  138.     T temp;  
  139.   
  140.     // sort v[0]..v[n-2], and arr[n-1] is in place  
  141.     for (pass = 0; pass < n-1; pass++)  
  142.     {  
  143.         // start the scan at index pass; set smallIndex to pass  
  144.         smallIndex = pass;  
  145.         // j scans the sublist v[pass+1]..v[n-1]  
  146.       for (j = pass+1; j < n; j++)  
  147.          // update smallIndex if smaller element is found  
  148.          if (v[j] < v[smallIndex])  
  149.             smallIndex = j;  
  150.       // when finished, place smallest item in arr[pass]  
  151.       if (smallIndex != pass)  
  152.         {  
  153.             temp = v[pass];  
  154.             v[pass] = v[smallIndex];  
  155.             v[smallIndex] = temp;  
  156.         }  
  157.    }  
  158. }  
  159.   
  160. template <typename T>  
  161. void insertionSort(vector<T>& v)  
  162. {  
  163.    int i, j, n = v.size();  
  164.    T target;  
  165.   
  166.     // place v[i] into the sublist  
  167.     //   v[0] ... v[i-1], 1 <= i < n,  
  168.     // so it is in the correct position  
  169.    for (i = 1; i < n; i++)  
  170.    {  
  171.       // index j scans down list from v[i] looking for  
  172.       // correct position to locate target. assigns it to  
  173.       // v[j]  
  174.       j = i;  
  175.       target = v[i];  
  176.       // locate insertion point by scanning downward as long  
  177.       // as target < v[j-1] and we have not encountered the  
  178.       // beginning of the list  
  179.       while (j > 0 && target < v[j-1])  
  180.       {  
  181.          // shift elements up list to make room for insertion  
  182.          v[j] = v[j-1];  
  183.          j--;  
  184.       }  
  185.       // the location is found; insert target  
  186.       v[j] = target;  
  187.    }  
  188. }  
  189.   
  190. template <typename T>  
  191. void insertionSort(vector<T>& v, int first, int last)  
  192. {  
  193.    int i, j;  
  194.    T target;  
  195.   
  196.     // place v[i] into the sublist  
  197.     //   v[first] ... v[i-1], first <= i < last,  
  198.     // so it is in the correct position  
  199.    for (i = first+1; i < last; i++)  
  200.    {  
  201.       // index j scans down list from v[i] looking for  
  202.       // correct position to locate target. assigns it to  
  203.       // v[j]  
  204.       j = i;  
  205.       target = v[i];  
  206.       // locate insertion point by scanning downward as long  
  207.       // as target < v[j-1] and we have not encountered the  
  208.       // beginning of the range  
  209.       while (j > first && target < v[j-1])  
  210.       {  
  211.          // shift elements up list to make room for insertion  
  212.          v[j] = v[j-1];  
  213.          j--;  
  214.       }  
  215.       // the location is found; insert target  
  216.       v[j] = target;  
  217.    }  
  218. }  
  219.   
  220. // support function for radixSort()  
  221. // distribute vector elements into one of 10 queues  
  222. // using the digit corresponding to power  
  223. //   power = 1    ==> 1's digit  
  224. //   power = 10   ==> 10's digit  
  225. //   power = 100  ==> 100's digit  
  226. //   ...  
  227. void distribute(const vector<int>& v, queue<int> digitQueue[],  
  228.                 int power)  
  229. {  
  230.     int i;  
  231.   
  232.     // loop through the vector, inserting each element into  
  233.     // the queue (v[i] / power) % 10  
  234.     for (i = 0; i < v.size(); i++)  
  235.         digitQueue[(v[i] / power) % 10].push(v[i]);  
  236. }  
  237.   
  238. // support function for radixSort()  
  239. // gather elements from the queues and copy back to the vector  
  240. void collect(queue<int> digitQueue[], vector<int>& v)  
  241. {  
  242.     int i = 0, digit;  
  243.   
  244.     // scan the vector of queues using indices 0, 1, 2, etc.  
  245.     for (digit = 0; digit < 10; digit++)  
  246.         // collect items until queue empty and copy items back  
  247.         // to the vector  
  248.         while (!digitQueue[digit].empty())  
  249.         {  
  250.             v[i] = digitQueue[digit].front();  
  251.             digitQueue[digit].pop();  
  252.             i++;  
  253.         }  
  254. }  
  255.   
  256. void radixSort(vector<int>& v, int d)  
  257. {  
  258.     int i;  
  259.     int power = 1;  
  260.     queue<int> digitQueue[10];  
  261.   
  262.     for (i=0;i < d;i++)  
  263.     {  
  264.         distribute(v, digitQueue, power);  
  265.         collect(digitQueue, v);  
  266.         power *= 10;  
  267.     }  
  268. }  
  269.   
  270. template <typename T, typename Compare>  
  271. void heapSort (vector<T>& v, Compare comp)  
  272. {  
  273.     // "heapify" the vector v  
  274.     makeHeap(v, comp);  
  275.   
  276.     int i, n = v.size();  
  277.   
  278.     // iteration that determines elements v[n-1] ... v[1]  
  279.     for(i = n; i > 1;i--)  
  280.     {  
  281.         // call popHeap() to move next largest to v[n-1]  
  282.         popHeap(v, i, comp);  
  283.     }  
  284. }  
  285.   
  286. template <typename T>  
  287. void merge(vector<T>& v, int first, int mid, int last)  
  288. {  
  289.     // temporary vector to merge the sorted sublists  
  290.     vector<T> tempVector;  
  291.     int indexA, indexB, indexV;  
  292.   
  293.     // set indexA to scan sublistA (index range [first,mid)  
  294.     // and indexB to scan sublistB (index range [mid, last)  
  295.     indexA = first;  
  296.     indexB = mid;  
  297.   
  298.     // while both sublists are not exhausted, compare v[indexA] and  
  299.     // v[indexB]copy the smaller to vector temp using push_back()  
  300.     while (indexA < mid && indexB < last)  
  301.         if (v[indexA] < v[indexB])  
  302.         {  
  303.             tempVector.push_back(v[indexA]);    // copy element to temp  
  304.             indexA++;                               // increment indexA  
  305.         }  
  306.         else  
  307.         {  
  308.             tempVector.push_back(v[indexB]);    // copy element to temp  
  309.             indexB++;                               // increment indexB  
  310.         }  
  311.   
  312.     // copy the tail of the sublist that is not exhausted  
  313.     while (indexA < mid)  
  314.     {  
  315.         tempVector.push_back(v[indexA]);  
  316.         indexA++;  
  317.     }  
  318.   
  319.     while (indexB < last)  
  320.     {  
  321.         tempVector.push_back(v[indexB]);  
  322.         indexB++;  
  323.     }  
  324.   
  325.     // copy vector tempVector using indexV to vector v using indexA  
  326.     // which is initially set to first  
  327.     indexA = first;  
  328.   
  329.     // copy elements from temporary vector to original list  
  330.     for (indexV = 0; indexV < tempVector.size(); indexV++)  
  331.     {  
  332.         v[indexA] = tempVector [indexV];  
  333.         indexA++;  
  334.     }  
  335. }  
  336.   
  337. // sorts v in the index range [first,last) by merging  
  338. // ordered sublists  
  339. template <typename T>  
  340. void mergeSort(vector<T>& v, int first, int last)  
  341. {  
  342.     // if the sublist has more than 1 element continue  
  343.     if (first + 1 < last)  
  344.   {  
  345.         // for sublists of size 2 or more, call mergeSort()  
  346.         // for the left and right sublists and then  
  347.         // merge the sorted sublists using merge()  
  348.         int midpt = (last + first) / 2;  
  349.   
  350.         mergeSort(v, first, midpt);  
  351.         mergeSort(v, midpt, last);  
  352.         merge(v, first, midpt, last);  
  353.    }  
  354. }  
  355.   
  356.   
  357. template <typename T>  
  358. int pivotIndex(vector<T>& v, int first, int last)  
  359. {  
  360.     // index for the midpoint of [first,last) and the  
  361.     // indices that scan the index range in tandem  
  362.     int mid, scanUp, scanDown;  
  363.     // pivot value and object used for exchanges  
  364.     T pivot, temp;  
  365.   
  366.     if (first == last)  
  367.         return last;  
  368.     else if (first == last-1)  
  369.         return first;  
  370.     else  
  371.     {  
  372.         mid = (last + first)/2;  
  373.         pivot = v[mid];  
  374.   
  375.         // exchange the pivot and the low end of the range  
  376.         // and initialize the indices scanUp and scanDown.  
  377.         v[mid] = v[first];  
  378.         v[first] = pivot;  
  379.   
  380.         scanUp = first + 1;  
  381.         scanDown = last - 1;  
  382.   
  383.         // manage the indices to locate elements that are in  
  384.         // the wrong sublist; stop when scanDown <= scanUp  
  385.         for(;;)  
  386.         {  
  387.             // move up lower sublist; stop when scanUp enters  
  388.             // upper sublist or identifies an element >= pivot  
  389.             while (scanUp <= scanDown && v[scanUp] < pivot)  
  390.                 scanUp++;  
  391.   
  392.             // scan down upper sublist; stop when scanDown locates  
  393.             // an element <= pivot; we guarantee we stop at arr[first]  
  394.             while (pivot < v[scanDown])  
  395.                 scanDown--;  
  396.   
  397.             // if indices are not in their sublists, partition complete  
  398.             if (scanUp >= scanDown)  
  399.                 break;  
  400.   
  401.             // indices are still in their sublists and identify  
  402.             // two elements in wrong sublists. exchange  
  403.             temp = v[scanUp];  
  404.             v[scanUp] = v[scanDown];  
  405.             v[scanDown] = temp;  
  406.   
  407.             scanUp++;  
  408.             scanDown--;  
  409.         }  
  410.   
  411.         // copy pivot to index (scanDown) that partitions sublists  
  412.         // and return scanDown  
  413.         v[first] = v[scanDown];  
  414.         v[scanDown] = pivot;  
  415.         return scanDown;  
  416.     }  
  417. }  
  418.   
  419. template <typename T>  
  420. void quicksort(vector<T>& v, int first, int last)  
  421. {  
  422.    // index of the pivot  
  423.    int pivotLoc;  
  424.     // temp used for an exchange when [first,last) has  
  425.     // two elements  
  426.     T temp;  
  427.   
  428.    // if the range is not at least two elements, return  
  429.    if (last - first <= 1)  
  430.         return;  
  431.   
  432.     // if sublist has two elements, compare v[first] and  
  433.     // v[last-1] and exchange if necessary  
  434.    else if (last - first == 2)  
  435.     {  
  436.         if (v[last-1] < v[first])  
  437.         {  
  438.             temp = v[last-1];  
  439.             v[last-1] = v[first];  
  440.             v[first] = temp;  
  441.         }  
  442.         return;  
  443.     }  
  444.    else  
  445.     {  
  446.         pivotLoc = pivotIndex(v, first, last);  
  447.   
  448.         // make the recursive call  
  449.         quicksort(v, first, pivotLoc);  
  450.   
  451.         // make the recursive call  
  452.         quicksort(v, pivotLoc +1, last);  
  453.     }  
  454. }  
  455.   
  456. template <typename T>  
  457. void findK(vector<T>& v, int first, int last, int k)  
  458. {  
  459.     int index;  
  460.   
  461.     // partition range [first,last) in v about the  
  462.     // pivot v[index]  
  463.     index = pivotIndex(v, first, last);  
  464.   
  465.     // if index == k, we are done. kth largest is v[k]  
  466.     if (index == k)  
  467.         return;  
  468.     else if(k < index)  
  469.         // search in lower sublist [first,index)  
  470.         findK(v, first, index, k);  
  471.     else  
  472.         // search in upper sublist [index+1,last)  
  473.         findK(v, index+1, last, k);  
  474. }  
  475.   
  476. #endif   // SORTING_ALGORITHMS  

6.main.cpp

[cpp] view
plaincopy

  1. // File: prg3_1.cpp  
  2. // the program compares the efficiency of the sequential  
  3. // and binary search by timing algorithm execution using the  
  4. // timer class. two integer arrays list1 and list2  
  5. // of size ARRAY_SIZE are initialized with the same random  
  6. // integers in the range 0 to 999,999. initialize the array  
  7. // targetList having TARGET_SIZE elements to contain other  
  8. // random numbers in the same range. time the selection sort  
  9. // as it sorts list2 and output the result. using the  
  10. // elements in array targetList as target values for the  
  11. // sequential and binary searches, time each algorithm and  
  12. // output the results  
  13.   
  14. #include <iostream>  
  15.   
  16. #include "d_search.h"   // generic sequential and binary searches  
  17. #include "d_sort.h"     // generic selection sort  
  18. #include "d_random.h"   // random number generation  
  19. #include "d_timer.h"        // time events  
  20.   
  21. using namespace std;  
  22.   
  23. int main()  
  24. {   const int ARRAY_SIZE = 100000, TARGET_SIZE = 50000;  
  25.   
  26.     // arrays for the search  
  27.    int list1[ARRAY_SIZE], list2[ARRAY_SIZE], targetList[TARGET_SIZE];  
  28.     int i;  
  29.   
  30.     // t used for timing the search algorithms  
  31.     timer t;  
  32.     // random number object  
  33.     randomNumber rnd;  
  34.   
  35.     // initialize the arrays with random numbers in the  
  36.    // range 0 to 999,999   
  37.    for (i = 0; i < ARRAY_SIZE; i++)  
  38.         list1[i] = list2[i] = rnd.random(1000000);  
  39.   
  40.     // initialize targetList with random numbers in the  
  41.    // same range 0 to 999,999   
  42.     for (i=0;i < TARGET_SIZE; i++)  
  43.         targetList[i] = rnd.random(1000000);  
  44.   
  45.     // sort list2  
  46.    cout << "Timing the Selection Sort" << endl;  
  47.     t.start();      // start timer  
  48.     selectionSort(list2,ARRAY_SIZE);  
  49.     t.stop();       // stop timer  
  50.     cout << "Selection Sort takes " << t.time()  
  51.           << " seconds." << endl;  
  52.   
  53.    cout << endl << "Timing the Sequential Search" << endl;  
  54.     t.start();      // start timer  
  55.     // perform sequential search with elements from list2  
  56.     for (i = 0; i < TARGET_SIZE; i++)  
  57.         seqSearch(list1,0,ARRAY_SIZE,targetList[i]);  
  58.     t.stop();       // stop timer  
  59.     cout << "Sequential Search takes " << t.time()  
  60.           << " seconds." << endl;  
  61.   
  62.     cout << endl << "Timing the Binary Search" << endl;  
  63.     t.start();      // start timer  
  64.     // perform binary search with elements from list1  
  65.     for (i = 0; i < TARGET_SIZE; i++)  
  66.         binSearch(list2,0,ARRAY_SIZE,targetList[i]);  
  67.     t.stop();       // stop timer  
  68.     cout << "Binary Search takes " << t.time()  
  69.           << " seconds." << endl;  
  70.   
  71.     return 0;  
  72. }  

备注：

1.参考书籍：Data Structures with C++ using STL, 2nd Edition  William H. Ford  William R. Topp

2.程序来源：http://www.fordtopp.com/

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞