经常在论坛上看到一些牛人测试某个算法的运行时间,有c#版的,有c++版的,而自己一个都不知道是如何实现,今天看Data Structures with C++ using STL, 2nd Edition这本书的时候看到了一个比较好的例子,上面也写到了我以前写过的排序算法,看到别人写的,汗颜不已!另外,最近看了一些老外写的代码:注释之详细,结构之清晰、这些编程风格都让我感到自己的业余,代码很长,只是大概看懂了,贴出来,和大家分享下。
1.d_random.h
using namespace std;
// generate random numbers
class randomNumber
{
public:
// initialize the random number generator
randomNumber(long s = 0);
// return a 32-bit random integer m, 1 <= m <= 2^31-2
long random();
// return a 32-bit random integer m, 0 <= m <= n-1,
// where n <= 2^31-1
long random(long n);
// return a real number x, 0 <= x < 1
double frandom();
private:
static const long A;
static const long M;
static const long Q;
static const long R;
long seed;
};
const long randomNumber::A = 48271;
const long randomNumber::M = 2147483647;
const long randomNumber::Q = M / A;
const long randomNumber::R = M % A;
randomNumber::randomNumber(long s)
{
if (s < 0)
s = 0;
if (s == 0)
{
// get time of day in seconds since 12:00 AM,
// January 1, 1970
long t_time = time(NULL);
// mix-up bits by squaring
t_time *= t_time;
// result can overflow. handle cases
// > 0, < 0, = 0
if (t_time > 0)
s = t_time ^ 0x5EECE66DL;
else if (t_time < 0)
s = (t_time & 0x7fffffff) ^ 0x5EECE66DL;
else
s = 0x5EECE66DL;
}
seed = s;
}
long randomNumber::random()
{
long tmpSeed = A * ( seed % Q ) - R * ( seed / Q );
if( tmpSeed >= 0 )
seed = tmpSeed;
else
seed = tmpSeed + M;
return seed;
}
long randomNumber::random(long n)
{
double fraction = double(random())/double(M);
return int(fraction * n);
}
double randomNumber::frandom()
{
return double(random())/double(M);
}
2.d_timer.h
#include <time.h> // declares clock_t type, function clock(),
// and constant CLOCKS_PER_SEC
class timer
{
private:
// starting and ending time measured in clock ticks
clock_t startTime, endTime;
public:
timer();
// initialize the timer.
// Postconditions: set the starting and ending event times to 0.
// this creates an event whose time is 0.0
void start();
// start timing an event.
// Postcondition: record the current time as the starting time
void stop();
// stop timing an event.
// Postconditon: record the current time as the ending time
double time() const;
// return the time the event took in seconds by computing
// the difference between the ending and starting times.
};
// ***********************************************************
// timer class implementation
// ***********************************************************
// constructor. set starting and ending times to 0
timer::timer():startTime(0), endTime(0)
{}
// determine clock ticks at start
void timer::start()
{
startTime = clock();
}
// determine clock ticks at end
void timer::stop()
{
endTime = clock();
}
// return the elapsed time in seconds
double timer::time() const
{
return (endTime-startTime)/double(CLOCKS_PER_SEC);
}
#endif // TIMER_CLASS
3.d_search.h
#include <vector>
#include <list>
using namespace std;
// perform a sequential search of an integer array for a target
// in the index range [first, last). return the index of a
// match or last if the target is not in arr
int seqSearch(const int arr[], int first, int last, int target);
// perform asequential search for a target in the index range
// [first, last). return the index of a match or last if the
// target is not in arr
template <typename T>
int seqSearch(const T arr[], int first, int last, const T& target);
// perform a binary search of an integer array for a target
// in the index range [first, last). return the index of a
// match or last if the target is not in arr
int binSearch(const int arr[], int first, int last, int target);
// perform a binary search of an array for a target
// in the index range [first, last). return the index of a
// match or last if the target is not in arr
template <typename T>
int binSearch(const T arr[], int first, int last, const T& target);
// vector version of the sequential search
template <typename T>
int seqSearch(const vector<T>& v, int first, int last, const T& target);
// vector version of the binary search
template <typename T>
int binSearch(const vector<T>& v, int first, int last, const T& target);
// perform the sequential search for target in the list
// iterator range [first, last). return an iterator pointing
// at the target in the list or last if target is not found
template <typename T>
typename list<T>::iterator seqSearch(typename list<T>::iterator first,
typename list<T>::iterator last, const T& target);
// perform the sequential search for target in the container
// iterator range [first, last). return an iterator pointing
// at the target in the container or last if target is not
// found
template <typename Iterator, typename T>
Iterator find(Iterator first, Iterator last, const T& target);
// ***********************************************************
// search function implementations
// ***********************************************************
int seqSearch(const int arr[], int first, int last, int target)
{
int i;
// scan indices in the range first <= i < last
for(i=first; i < last; i++)
if (arr[i] == target)
return i; // immediately return on a match
return last; // return last if target not found
}
template <typename T>
int seqSearch(const T arr[], int first, int last, const T& target)
{
int i;
// scan indices in the range first <= i < last
for(i=first; i < last; i++)
if (arr[i] == target) // assume T has the "==" operator
return i; // immediately return on a match
return last; // return last if target not found
}
int binSearch(const int arr[], int first, int last, int target)
{
int mid; // index of the midpoint
int midValue; // object that is assigned arr[mid]
int origLast = last; // save original value of last
while (first < last) // test for nonempty sublist
{
mid = (first+last)/2;
midValue = arr[mid];
if (target == midValue)
return mid; // have a match
// determine which sublist to search
else if (target < midValue)
last = mid; // search lower sublist. reset last
else
first = mid+1; // search upper sublist. reset first
}
return origLast; // target not found
}
template <typename T>
int binSearch(const T arr[], int first, int last, const T& target)
{
int mid; // index of the midpoint
T midValue; // object that is assigned arr[mid]
int origLast = last; // save original value of last
while (first < last) // test for nonempty sublist
{
mid = (first+last)/2;
midValue = arr[mid];
if (target == midValue)
return mid; // have a match
// determine which sublist to search
else if (target < midValue)
last = mid; // search lower sublist. reset last
else
first = mid+1; // search upper sublist. reset first
}
return origLast; // target not found
}
template <typename T>
int seqSearch(const vector<T>& v, int first, int last, const T& target)
{
int i;
// scan indices in the range first <= i < last
for(i=first; i < last; i++)
if (v[i] == target) // assume T has the "==" operator
return i; // immediately return on a match
return last; // otherwise return last
}
template <typename T>
int binSearch(const vector<T>& v, int first, int last, const T& target)
{
int mid; // index of the midpoint
T midvalue; // object that is assigned v[mid]
int origLast = last; // save original value of last
while (first < last) // test for nonempty sublist
{
mid = (first+last)/2;
midvalue = v[mid];
if (target == midvalue)
return mid; // have a match
// determine which sublist to search
else if (target < midvalue)
last = mid; // search lower sublist. reset last
else
first = mid+1; // search upper sublist. reset first
}
return origLast; // target not found
}
template <typename T>
typename list<T>::iterator seqSearch(typename list<T>::iterator first,
typename list<T>::iterator last, const T& target)
{
// start at location first
list<T>::iterator iter = first;
// compare list elements with item until either
// we arrive at last or locate item
while(iter != last && !(*iter == target))
iter++;
// iter either points at item or is last
return iter;
}
template <typename Iterator, typename T>
Iterator find(Iterator first, Iterator last, const T& target)
{
Iterator iter = first;
// scan iterator range [first, last), stopping
// if the loop locates target
while (iter != last && *iter != target)
iter++;
// if target located, iter points at it; otherwise
// is has value last
return iter;
}
#endif // SEARCH_FUNCTIONS
4.d_heap.h
#include <vector>
#include <functional>
using namespace std;
// the vector elements in the range [0, last-1) are a heap.
// insert the element v[last-1] into the heap so that the
// range [0, last) is a heap. use the function object comp
// to perform comparisons
template <typename T, typename Compare>
void pushHeap(vector<T>& v, int last, Compare comp);
// filter the vector element v[first] down the heap with index
// range [first, last)
template <typename T, typename Compare>
void adjustHeap(vector<T>& v, int first, int last, Compare comp);
// the vector elements in the range [0, last) are a heap.
// swap the first and last elements of the heap and then
// make the elements in the index range [0, last-1) a heap.
// use the function object comp to perform comparisons
template <typename T, typename Compare>
void popHeap(vector<T>& v, int last, Compare comp);
// arrange the vector elements into a heap. use the function
// object comp to perform comparisons
template <typename T, typename Compare>
void makeHeap(vector<T>& v, Compare comp);
// implementations
template <typename T, typename Compare>
void pushHeap(vector<T>& v, int last, Compare comp)
{
// assume the new item is at location v[last-1] and that
// the elements v[0] to v[last-2] are in heap order
int currentPos, parentPos;
T target;
// currentPos is an index that traverses path of parents.
// target is value hlist[i] and is repositioned in path
currentPos = last-1;
parentPos = (currentPos-1)/2;
target = v[last-1];
// traverse path of parents up to the root
while (currentPos != 0)
{
// compare target and parent value
if (comp(target,v[parentPos]))
{
// move data from parent position to current
// position. update current position to parent
// position. compute next parent
v[currentPos] = v[parentPos];
currentPos = parentPos;
parentPos = (currentPos-1)/2;
}
else
// if !comp(target, parentvalue), heap condition is ok. break
break;
}
// the correct location has been discovered. assign target
v[currentPos] = target;
}
template <typename T, typename Compare>
void adjustHeap(vector<T>& v, int first, int last, Compare comp)
{
int currentPos, childPos;
T target;
// start at first and filter target down the heap
currentPos = first;
target = v[first];
// compute the left child index and begin a scan down
// path of children, stopping at end of list (last)
// or when we find a place for target
childPos = 2 * currentPos + 1;
while (childPos <= last-1)
{
// index of right child is childPos+1. compare the
// two children. change childPos if
// comp(v[childPos+1], v[childPos]) is true
if ((childPos+1 <= last-1) &&
comp(v[childPos+1], v[childPos]))
childPos = childPos + 1;
// compare selected child to target
if (comp(v[childPos],target))
{
// comp(selected child, target) is true.
// move selected child to the parent;
// position of selected child is now vacated
v[currentPos] = v[childPos];
// update indices to continue the scan
currentPos = childPos;
childPos = 2 * currentPos + 1;
}
else
// target belongs at currentPos
break;
}
v[currentPos] = target;
}
template <typename T, typename Compare>
void popHeap(vector<T>& v, int last, Compare comp)
{
T temp;
// exchange the first and last element in the heap
temp = v[0];
v[0] = v[last-1];
v[last-1] = temp;
// filter down the root over the range [0, last-1)
adjustHeap(v, 0, last-1, comp);
}
template <typename T, typename Compare>
void makeHeap(vector<T>& v, Compare comp)
{
int heapPos, lastPos;
// compute the size of teh heap and the index
// of the last parent
lastPos = v.size();
heapPos = (lastPos - 2)/2;
// filter down every parent in order from last parent
// down to root
while (heapPos >= 0)
{
adjustHeap(v,heapPos, lastPos, comp);
heapPos--;
}
}
#endif // HEAP_FUNCTIONS
5.d_sort.h
#ifndef SORTING_ALGORITHMS
#define SORTING_ALGORITHMS
#include <vector>
#include <queue>
#include "d_heap.h" // heap function library
using namespace std;
// sort an integer array using selection sort
void selectionSort(int arr[], int n);
// sort an array of type T using selection sort
template <typename T>
void selectionSort(T arr[], int n);
// sort a vector of type T using selection sort
template <typename T>
void selectionSort(vector<T>& v);
// sort a vector of type T using insertion sort
template <typename T>
void insertionSort(vector<T>& v);
// sort the elements of a vector of type T in the range
// [first, last) using insertion sort
template <typename T>
void insertionSort(vector<T>& v, int first, int last);
// sort v using the radix sort. each integer has d digits
void radixSort(vector<int>& v, int d);
// sort a vector using heapsort
template <typename T, typename Compare>
void heapSort (vector<T>& v, Compare comp);
// the elements in the ranges [first,mid) and [mid,last) are
// ordered. the function merges the ordered sequences into
// an ordered sequence in the range [first,last)
template <typename T>
void merge(vector<T>& v, int first, int mid, int last);
// sorts v in the index range [first,last) by merging
// ordered sublists
template <typename T>
void mergeSort(vector<T>& v, int first, int last);
// using the value at the midpoint of [first,last) as the pivot,
// locate the pivot in its final location so all elements
// to its left are <= to its value and all elements to the
// right are >= to its value. return the index of the pivot
template <typename T>
int pivotIndex(vector<T>& v, int first, int last);
// sort a vector using quicksort
template <typename T>
void quicksort(vector<T>& v, int first, int last);
// locate the kth largest element of v at index k
template <typename T>
void findK(vector<T>& v, int first, int last, int k);
// IMPLEMENTATIONS
void selectionSort(int arr[], int n)
{
int smallIndex; // index of smallest element in the sublist
int pass, j;
int temp;
// pass has the range 0 to n-2
for (pass = 0; pass < n-1; pass++)
{
// scan the sublist starting at index pass
smallIndex = pass;
// j traverses the sublist arr[pass+1] to arr[n-1]
for (j = pass+1; j < n; j++)
// update if smaller element found
if (arr[j] < arr[smallIndex])
smallIndex = j;
// if smallIndex and pass are not the same location,
// exchange the smallest item in the sublist with arr[pass]
if (smallIndex != pass)
{
temp = arr[pass];
arr[pass] = arr[smallIndex];
arr[smallIndex] = temp;
}
}
}
template <typename T>
void selectionSort(T arr[], int n)
{
int smallIndex; // index of smallest element in the sublist
int pass, j;
T temp;
// pass has the range 0 to n-2
for (pass = 0; pass < n-1; pass++)
{
// scan the sublist starting at index pass
smallIndex = pass;
// j traverses the sublist arr[pass+1] to arr[n-1]
for (j = pass+1; j < n; j++)
// update if smaller element found
if (arr[j] < arr[smallIndex])
smallIndex = j;
// if smallIndex and pass are not the same location,
// exchange the smallest item in the sublist with arr[pass]
if (smallIndex != pass)
{
temp = arr[pass];
arr[pass] = arr[smallIndex];
arr[smallIndex] = temp;
}
}
}
template <typename T>
void selectionSort(vector<T>& v)
{
// index of smallest item in each pass
int smallIndex;
// save the vector size in n
int pass, j, n = v.size();
T temp;
// sort v[0]..v[n-2], and arr[n-1] is in place
for (pass = 0; pass < n-1; pass++)
{
// start the scan at index pass; set smallIndex to pass
smallIndex = pass;
// j scans the sublist v[pass+1]..v[n-1]
for (j = pass+1; j < n; j++)
// update smallIndex if smaller element is found
if (v[j] < v[smallIndex])
smallIndex = j;
// when finished, place smallest item in arr[pass]
if (smallIndex != pass)
{
temp = v[pass];
v[pass] = v[smallIndex];
v[smallIndex] = temp;
}
}
}
template <typename T>
void insertionSort(vector<T>& v)
{
int i, j, n = v.size();
T target;
// place v[i] into the sublist
// v[0] ... v[i-1], 1 <= i < n,
// so it is in the correct position
for (i = 1; i < n; i++)
{
// index j scans down list from v[i] looking for
// correct position to locate target. assigns it to
// v[j]
j = i;
target = v[i];
// locate insertion point by scanning downward as long
// as target < v[j-1] and we have not encountered the
// beginning of the list
while (j > 0 && target < v[j-1])
{
// shift elements up list to make room for insertion
v[j] = v[j-1];
j--;
}
// the location is found; insert target
v[j] = target;
}
}
template <typename T>
void insertionSort(vector<T>& v, int first, int last)
{
int i, j;
T target;
// place v[i] into the sublist
// v[first] ... v[i-1], first <= i < last,
// so it is in the correct position
for (i = first+1; i < last; i++)
{
// index j scans down list from v[i] looking for
// correct position to locate target. assigns it to
// v[j]
j = i;
target = v[i];
// locate insertion point by scanning downward as long
// as target < v[j-1] and we have not encountered the
// beginning of the range
while (j > first && target < v[j-1])
{
// shift elements up list to make room for insertion
v[j] = v[j-1];
j--;
}
// the location is found; insert target
v[j] = target;
}
}
// support function for radixSort()
// distribute vector elements into one of 10 queues
// using the digit corresponding to power
// power = 1 ==> 1's digit
// power = 10 ==> 10's digit
// power = 100 ==> 100's digit
// ...
void distribute(const vector<int>& v, queue<int> digitQueue[],
int power)
{
int i;
// loop through the vector, inserting each element into
// the queue (v[i] / power) % 10
for (i = 0; i < v.size(); i++)
digitQueue[(v[i] / power) % 10].push(v[i]);
}
// support function for radixSort()
// gather elements from the queues and copy back to the vector
void collect(queue<int> digitQueue[], vector<int>& v)
{
int i = 0, digit;
// scan the vector of queues using indices 0, 1, 2, etc.
for (digit = 0; digit < 10; digit++)
// collect items until queue empty and copy items back
// to the vector
while (!digitQueue[digit].empty())
{
v[i] = digitQueue[digit].front();
digitQueue[digit].pop();
i++;
}
}
void radixSort(vector<int>& v, int d)
{
int i;
int power = 1;
queue<int> digitQueue[10];
for (i=0;i < d;i++)
{
distribute(v, digitQueue, power);
collect(digitQueue, v);
power *= 10;
}
}
template <typename T, typename Compare>
void heapSort (vector<T>& v, Compare comp)
{
// "heapify" the vector v
makeHeap(v, comp);
int i, n = v.size();
// iteration that determines elements v[n-1] ... v[1]
for(i = n; i > 1;i--)
{
// call popHeap() to move next largest to v[n-1]
popHeap(v, i, comp);
}
}
template <typename T>
void merge(vector<T>& v, int first, int mid, int last)
{
// temporary vector to merge the sorted sublists
vector<T> tempVector;
int indexA, indexB, indexV;
// set indexA to scan sublistA (index range [first,mid)
// and indexB to scan sublistB (index range [mid, last)
indexA = first;
indexB = mid;
// while both sublists are not exhausted, compare v[indexA] and
// v[indexB]copy the smaller to vector temp using push_back()
while (indexA < mid && indexB < last)
if (v[indexA] < v[indexB])
{
tempVector.push_back(v[indexA]); // copy element to temp
indexA++; // increment indexA
}
else
{
tempVector.push_back(v[indexB]); // copy element to temp
indexB++; // increment indexB
}
// copy the tail of the sublist that is not exhausted
while (indexA < mid)
{
tempVector.push_back(v[indexA]);
indexA++;
}
while (indexB < last)
{
tempVector.push_back(v[indexB]);
indexB++;
}
// copy vector tempVector using indexV to vector v using indexA
// which is initially set to first
indexA = first;
// copy elements from temporary vector to original list
for (indexV = 0; indexV < tempVector.size(); indexV++)
{
v[indexA] = tempVector [indexV];
indexA++;
}
}
// sorts v in the index range [first,last) by merging
// ordered sublists
template <typename T>
void mergeSort(vector<T>& v, int first, int last)
{
// if the sublist has more than 1 element continue
if (first + 1 < last)
{
// for sublists of size 2 or more, call mergeSort()
// for the left and right sublists and then
// merge the sorted sublists using merge()
int midpt = (last + first) / 2;
mergeSort(v, first, midpt);
mergeSort(v, midpt, last);
merge(v, first, midpt, last);
}
}
template <typename T>
int pivotIndex(vector<T>& v, int first, int last)
{
// index for the midpoint of [first,last) and the
// indices that scan the index range in tandem
int mid, scanUp, scanDown;
// pivot value and object used for exchanges
T pivot, temp;
if (first == last)
return last;
else if (first == last-1)
return first;
else
{
mid = (last + first)/2;
pivot = v[mid];
// exchange the pivot and the low end of the range
// and initialize the indices scanUp and scanDown.
v[mid] = v[first];
v[first] = pivot;
scanUp = first + 1;
scanDown = last - 1;
// manage the indices to locate elements that are in
// the wrong sublist; stop when scanDown <= scanUp
for(;;)
{
// move up lower sublist; stop when scanUp enters
// upper sublist or identifies an element >= pivot
while (scanUp <= scanDown && v[scanUp] < pivot)
scanUp++;
// scan down upper sublist; stop when scanDown locates
// an element <= pivot; we guarantee we stop at arr[first]
while (pivot < v[scanDown])
scanDown--;
// if indices are not in their sublists, partition complete
if (scanUp >= scanDown)
break;
// indices are still in their sublists and identify
// two elements in wrong sublists. exchange
temp = v[scanUp];
v[scanUp] = v[scanDown];
v[scanDown] = temp;
scanUp++;
scanDown--;
}
// copy pivot to index (scanDown) that partitions sublists
// and return scanDown
v[first] = v[scanDown];
v[scanDown] = pivot;
return scanDown;
}
}
template <typename T>
void quicksort(vector<T>& v, int first, int last)
{
// index of the pivot
int pivotLoc;
// temp used for an exchange when [first,last) has
// two elements
T temp;
// if the range is not at least two elements, return
if (last - first <= 1)
return;
// if sublist has two elements, compare v[first] and
// v[last-1] and exchange if necessary
else if (last - first == 2)
{
if (v[last-1] < v[first])
{
temp = v[last-1];
v[last-1] = v[first];
v[first] = temp;
}
return;
}
else
{
pivotLoc = pivotIndex(v, first, last);
// make the recursive call
quicksort(v, first, pivotLoc);
// make the recursive call
quicksort(v, pivotLoc +1, last);
}
}
template <typename T>
void findK(vector<T>& v, int first, int last, int k)
{
int index;
// partition range [first,last) in v about the
// pivot v[index]
index = pivotIndex(v, first, last);
// if index == k, we are done. kth largest is v[k]
if (index == k)
return;
else if(k < index)
// search in lower sublist [first,index)
findK(v, first, index, k);
else
// search in upper sublist [index+1,last)
findK(v, index+1, last, k);
}
#endif // SORTING_ALGORITHMS
6.main.cpp
#include <iostream>
#include "d_search.h" // generic sequential and binary searches
#include "d_sort.h" // generic selection sort
#include "d_random.h" // random number generation
#include "d_timer.h" // time events
using namespace std;
int main()
{ const int ARRAY_SIZE = 100000, TARGET_SIZE = 50000;
// arrays for the search
int list1[ARRAY_SIZE], list2[ARRAY_SIZE], targetList[TARGET_SIZE];
int i;
// t used for timing the search algorithms
timer t;
// random number object
randomNumber rnd;
// initialize the arrays with random numbers in the
// range 0 to 999,999
for (i = 0; i < ARRAY_SIZE; i++)
list1[i] = list2[i] = rnd.random(1000000);
// initialize targetList with random numbers in the
// same range 0 to 999,999
for (i=0;i < TARGET_SIZE; i++)
targetList[i] = rnd.random(1000000);
// sort list2
cout << "Timing the Selection Sort" << endl;
t.start(); // start timer
selectionSort(list2,ARRAY_SIZE);
t.stop(); // stop timer
cout << "Selection Sort takes " << t.time()
<< " seconds." << endl;
cout << endl << "Timing the Sequential Search" << endl;
t.start(); // start timer
// perform sequential search with elements from list2
for (i = 0; i < TARGET_SIZE; i++)
seqSearch(list1,0,ARRAY_SIZE,targetList[i]);
t.stop(); // stop timer
cout << "Sequential Search takes " << t.time()
<< " seconds." << endl;
cout << endl << "Timing the Binary Search" << endl;
t.start(); // start timer
// perform binary search with elements from list1
for (i = 0; i < TARGET_SIZE; i++)
binSearch(list2,0,ARRAY_SIZE,targetList[i]);
t.stop(); // stop timer
cout << "Binary Search takes " << t.time()
<< " seconds." << endl;
return 0;
}
备注:
1.参考书籍:Data Structures with C++ using STL, 2nd Edition William H. Ford William R. Topp
2.程序来源:http://www.fordtopp.com/