实现文件：
/****************************************************************************** sort.h** Some sort algorithms.** This file includes several usually used sorting algorithm, such as: bubble* sorting, selection sorting, insertion sorting, quick sorting, merging* sorting, and heap sorting.** Zhang Ming, 2010-07*****************************************************************************/#ifndef SORT_H#define SORT_H#include <vector>using namespace std;namespace itlab{/*** Bubble sort algorithm.* "a" ----> array of Comparable items.* "left" ----> the left-most index of the subarray.* "right" ----> the right-most index of the subarray.*/template <typename Type>void bubbleSort( vector<Type> &a, int left, int right ){bool cond;for( int i=left; i<right; ++i ){cond = false;for( int j=right; j>i; --j )if( a[j] < a[j-1] ){swap( a[j], a[j-1] );cond = true;}if( !cond )return;}}/*** Selection sort algorithm.* "a" ----> array of Comparable items.* "left" ----> the left-most index of the subarray.* "right" ----> the right-most index of the subarray.*/template <typename Type>void selectSort( vector<Type> &a, int left, int right ){Type minPos;for( int i=left; i<right; ++i ){minPos = i;for( int j=i+1; j<=right; ++j )if( a[j] < a[minPos] )minPos = j;if( i != minPos )swap( a[i], a[minPos] );}}/*** Insertion sort algorithm.* "a" ----> array of Comparable items.* "left" ----> the left-most index of the subarray.* "right" ----> the right-most index of the subarray.*/template <typename Type>void insertSort( vector<Type> &a, int left, int right ){for( int p=left+1; p<=right; p++ ){Type tmp = a[p];int j;for( j=p; j>left && tmp<a[j-1]; --j )a[j] = a[j-1];a[j] = tmp;}}/*** Return median of left, center, and right.* Order these and hide the pivot.*/template <typename Type>const Type& median3( vector<Type> &a, int left, int right ){int center = (left+right) / 2;if( a[center] < a[left] )swap( a[left], a[center] );if( a[right] < a[left] )swap( a[left], a[right] );if( a[right] < a[center] )swap( a[center], a[right] );swap( a[center], a[right-1] );return a[right-1];}/*** Internal quicksort method that makes recursive calls.* Uses median-of-three partitioning and a cutoff of 20.* "a" ----> array of Comparable items.* "left" ----> the left-most index of the subarray.* "right" ----> the right-most index of the subarray.*/template <typename Type>void quickSort( vector<Type> &a, int left, int right ){if( left+20 <= right ){Type pivot = median3( a, left, right );// begin partitioningint i = left, j = right-1;for( ; ; ){while( a[++i] < pivot ) { }while( pivot < a[--j] ) { }if( i < j )swap( a[i], a[j] );elsebreak;}// Restore pivotswap( a[i], a[right-1] );// Sort small elementsquickSort( a, left, i-1 );// Sort large elementsquickSort( a, i+1, right );}elseinsertSort( a, left, right );}/*** Merg two subsequence to a bigger one.* The first subsequence is a[left1] ... a[right1], and* The second subsqeuence is a[left2] ... a[right2].*/template <typename Type>void merg( vector<Type> &a, int left1, int right1, int left2, int right2 ){int k = 0,i = left1,j = left2,n1 = right1-left1+1,n2 = right2-left2+1;Type *tmp = new Type[n1+n2];while( i <= right1 && j <= right2 )if( a[i] < a[j] )tmp[k++] = a[i++];elsetmp[k++] = a[j++];while( i <= right1 )tmp[k++] = a[i++];while( j <= right2 )tmp[k++] = a[j++];for( int i=0; i<n1; ++i )a[left1++] = tmp[i];for( int i=0; i<n2; ++i )a[left2++] = tmp[n1+i];delete []tmp;}/*** Merg sort algorithm (nonrecursion).* "a" ----> array of Comparable items.* "left" ----> the left-most index of the subarray.* "right" ----> the right-most index of the subarray.*/template <typename Type>void mergSort( vector<Type> &a, int left, int right ){int left1, right1, left2, right2,n = right - left + 1,size = 1;while( size < n ){left1 = left;while( left1+size < n ){left2 = left1+size;right1 = left2-1;if( left2+size > n )right2 = right;elseright2 = left2+size-1;merg( a, left1, right1, left2, right2 );left1 = right2+1;}size *= 2;}}/*** Heap sort algorthm.* "a" ----> array of Comparable items.* "left" ----> the left-most index of the subarray.* "right" ----> the right-most index of the subarray.*/template <typename Type>void heapSort( vector<Type> &a, int left, int right ){int n = right-left+1;vector<Type> tmp( n );for( int i=0; i<n; ++i )tmp[i] = a[left+i];for( int i=n/2; i>=0; --i )filterDown( tmp, i, n );for( int j=n-1; j>0; --j ){swap( tmp[0], tmp[j] );filterDown( tmp, 0, j );}for( int i=0; i<n; ++i )a[left+i] = tmp[i];}/*** Percolate down the heap.* "i" ----> the position from which to percolate down.* "n" ----> the logical size of the binary heap.*/template <typename Type>void filterDown( vector<Type> &a, int i, int n ){int child;Type tmp;for( tmp=a[i]; 2*i+1<n; i=child ){child = 2*i+1;if( child!=n-1 && a[child]<a[child+1] )child++;if( tmp < a[child] )a[i] = a[child];elsebreak;}a[i] = tmp;}}// namespace itlab#endif// SORT_H
测试文件：
/****************************************************************************** sort_test.cpp** Sorting algorithm testing.** Zhang Ming, 2009-10*****************************************************************************/#include <iostream>#include <random.h>#include <sort.h>using namespace std;using namespace itlab;const int SIZE = 10;template <typename Type>void printVector( const vector<Type> &a ){vector<int>::const_iterator itr = a.begin();while( itr != a.end() )cout << *itr++ << "\t";cout << endl;}int main(){vector<int> a( SIZE );cout << "Unsorted Numbers : " << endl;Random r(127);for( unsigned i=0; i<a.size(); ++i )a[i] = r.random( 1, 10*SIZE );printVector( a );cout << "Bubble Sorted Numbers : " << endl;bubbleSort( a, 0, a.size()-1 );printVector( a );cout << endl;cout << "Unsorted Numbers : " << endl;for( unsigned i=0; i<a.size(); ++i )a[i] = r.random( 1, 10*SIZE );printVector( a );cout << "Select Sorted Numbers : " << endl;selectSort( a, 0, a.size()-1 );printVector( a );cout << endl;cout << "Unsorted Numbers : " << endl;for( unsigned i=0; i<a.size(); ++i )a[i] = r.random( 1, 10*SIZE );printVector( a );cout << "Insert Sorted Numbers : " << endl;insertSort( a, 0, a.size()-1 );printVector( a );cout << endl;cout << "Unsorted Numbers : " << endl;for( unsigned i=0; i<a.size(); ++i )a[i] = r.random( 1, 10*SIZE );printVector( a );cout << "Quick Sorted Numbers : " << endl;quickSort( a, 0, a.size()-1 );printVector( a );cout << endl;cout << "Unsorted Numbers : " << endl;for( unsigned i=0; i<a.size(); ++i )a[i] = r.random( 1, 10*SIZE );printVector( a );cout << "Merg Sorted Numbers : " << endl;mergSort( a, 0, a.size()-1 );printVector( a );cout << endl;cout << "Unsorted Numbers : " << endl;for( unsigned i=0; i<a.size(); ++i )a[i] = r.random( 1, 10*SIZE );printVector( a );cout << "Heap Sorted Numbers : " << endl;heapSort( a, 0, a.size()-1 );printVector( a );cout << endl;return 0;}
联系客服
