排序的算法集中到一起了，包括冒泡排序、选择排序、插入排序，Shell排序，快速排序、归并排序、堆排序，基数排序、bucket排序。 使用起来也很简单，包含SortAlgorithm.h即可直接使用（这里重在算法本身，用一个类包含static函数的做法则可以原谅了：）。 （两个文件：SortAlgorithm.h和main.cpp）。 //SortAlgorithm.h #if !defined _SORT_ALGORITHM_H_#define _SORT_ALGORITHM_H_ #ifndef NNULL#define NULL 0L#endif //~ NULL #include <cassert>#include <ctime> #include <iostream>using namespace std; template <typename T>class BasicSortor{public:        // bubble sort    static void bubbleSort( T* _data,int _left,int _right )    {        assert( NULL != _data );        assert( ( _left >= 0 ) && ( _right >= _left ) );            if ( 1 == _right - _left )  return ;               for ( int i = _left; i <= _right; ++i )            for ( int j = _right; j > i; --j )                if ( _data[j] < _data[j - 1] )                    swap( _data[j], _data[j - 1] );    }        // select sort    static void selectSort( T* _data, int _left, int _right )    {        assert( NULL != _data );        assert( ( _left >= 0 ) && ( _right >= _left ) );            if ( 0 == _right - _left ) return ;            for ( int i = _left; i <= _right; ++i)    {            int min = i;            for ( int j = i; j <= _right; ++j)    {                if ( _data[j] < _data[min] )                min = j;    }                swap( _data[i],_data[min] );    }    }        // insert sort    static void insertSort( T* _data, int _left, int _right )    {        assert( NULL != _data );        assert( ( _left >= 0 ) && ( _right >= _left ) );            if ( 0 == _right - _left ) return ;            for ( int i = _left; i <= _right; ++i )    {            int j = i;            T tmp = _data[i];                while ( ( j > _left ) && ( tmp < _data[j - 1] ) )    {                _data[j] = _data[j - 1];        j--;    }                _data[j] = tmp;    }    }        //shell sort    static void shellSort( T* _data, int _left, int _right)    {        assert( NULL != _data );        assert( ( _left >= 0 ) && ( _right >= _left ) );            if ( 0 == _right - _left ) return ;            int d = 0;        for ( int  m = 0; m < ( _right - _left ) / 3; ++m )            d = 3 * d + 1;            for ( ; d > 0; d /= 3 )    {            for ( int i = _left; i <= _right; ++i )    {                int j = i;                T tmp = _data[j];                    while ( ( j >= _left + d) && ( tmp < _data[j - d] ) )        {                    _data[j] = _data[j - d];            j -= d;        }                    _data[j] = tmp;    }    }     }        // quick sort    static void quickSort( T* _data, int _left, int _right)    {        assert( NULL != _data );            if ( _left >= _right ) return ;            int mid = partition( _data, _left, _right );        quickSort( _data, _left, mid - 1 );        quickSort( _data, mid + 1, _right );    }        // merge sort    static void mergeSort( T* _data, int _left, int _right )    {        assert ( NULL != _data );            if ( _left >= _right ) return ;            int mid = ( _left + _right ) / 2;        mergeSort( _data, _left, mid );        mergeSort( _data, mid + 1, _right );        merge( _data, _left, _right, mid );    }        // heap sort    static void heapSort( T* _data,int _left, int _right )    {        assert( NULL != _data );        assert( ( _left >= 0 ) && ( _right >= _left ) );            for ( int i = _right; i > ( _right - _left ) / 2; --i )            fixUp(_data, _left, _right, i );            while ( _right > _left )    {            swap( _data[_left], _data[_right] );            fixDown( _data, _left, --_right, _left );    }    }        // bucket sort    static void bucketSort( T* _data,int _left, int _right, int MAX_NUM = 1000 )    {        assert( NULL != _data );        assert( ( _left >= 0 ) && ( _right >= _left ) );            if ( 0 == _right - _left ) return ;            int num = _right - _left + 1;         int* count = new int[MAX_NUM];            // calculate the num of elements equal or less than _data[i]        for ( int i = 0; i < MAX_NUM; ++i )            count[i] = 0;            for ( int j = _left; j <= _right; ++j )            count[_data[j]]++;            for ( int k = 1; k < MAX_NUM; ++k )            count[k] += count[k - 1];            T* tmp = new T[num];            // copy each element to the right position         // ( from right to left to reserve the related position in the array )        for ( int m = _right; m >= _left; --m )            tmp[--count[_data[m]]] = _data[m];            for ( int n = _left; n <= _right; ++n)            _data[n] = tmp[n - _left];            delete[] count;        delete[] tmp;        }        // radix sort    static void radixSort( T* _data,int _left, int _right )    {        assert( NULL != _data );        assert( ( _left >= 0 ) && ( _right >= _left ) );            if ( 0 == _right - _left ) return ;         const int WIDTH = 4;         for ( int i = 1; i <= WIDTH; ++i )            sortAtBit( _data, _left, _right, i );    }public:    static void printData( const T* _data,                           int _left,                           int _right)    {        assert( NULL != _data );        assert( (_left >= 0 ) && (_right >= _left) );                for ( int i = _left; i <= _right; ++i)    {            cout<<_data[i]<<" ";    }            cout<<endl;    }        static T* initData( int ARR_LEN = 10,                        int MAX_NUM = 1000 )    {        T* data = new T[ARR_LEN];            srand( ( unsigned int )time(NULL));            for ( int i = 0; i < ARR_LEN ; ++i)    {            data[i] = rand() % MAX_NUM;    }            return data;    }protected:    private:        // swap     static void swap(T& a,T& b)    {        T tmp = a;        a = b;        b = tmp;    }        // partition    static int partition( T* _data,                  int _left,                  int _right)    {        assert ( NULL != _data);        assert ( ( _left >= 0 ) && ( _right >= _left ) );            if ( 0 == _right - _left )    {            return _left;    }            T tmp = _data[_left];        int i = _left + 1;        int j = _right;            while ( true )    {            while ( _data[i] < tmp )    {        i++;                if ( i == _right ) break;    }             while ( _data[j] > tmp )        j--;                if ( i >= j )             break ;                swap( _data[i], _data[j] );    }            swap( _data[_left], _data[j] );            return j;    }        // merge    static void merge( T* _data,                        int _left,                        int _right,                        int _mid)    {        assert ( NULL != _data );            int num = _right - _left + 1;        T* tmp = new T[num];            for ( int i = _left, j = _mid + 1, k = 0; k < num; ++k)    {            if ( i > _mid )     {                tmp[k] = _data[j++];                continue ;    }            if ( j > _right )    {                 tmp[k] = _data[i++];                 continue ;    }                tmp[k] = ( _data[i] < _data[j] ) ? _data[i++] : _data[j++];    }            for ( int m = _left; m <= _right; ++m )            _data[m] = tmp[m - _left];            delete[] tmp;    }        // heap fix up    static void fixUp( T* _data,                        int _left,                        int _right,                        int i )    {        int prt = ( i - _left - 1 ) / 2 + _left;   // parent node        while ( i > _left )    {            if ( _data[i] < _data[prt] )                swap( _data[i], _data[prt] );                i = prt;            prt = ( i - _left - 1 ) / 2 + _left;    }    }        // heap fix down    static void fixDown( T* _data,                          int _left,                          int _right,                          int i )    {        int child = 2 * ( i - _left ) + 1 + _left;  // left child node            while ( child <= _right )    {            if ( ( child + 1 <= _right ) && ( _data[child] > _data[child + 1] ) )                child += 1;                if ( _data[child] < _data[i] )                swap( _data[child], _data[i] );                i = child;             child = 2 * ( i - _left ) + 1 + _left;    }    }        // get bits from a int    static int getBitAt( int num,                           int i )    {        int ret = 0;        while ( i-- > 0 )    {            ret = num % 10;            num /= 10;    }            return ret;     }        // sort array on bit i    static void sortAtBit( T* _data,                            int _left,                            int _right,                            int d )    {        const int RADIX = 10;            int count[RADIX] = { 0 };            for ( int i = _left; i <= _right; ++i )            count[getBitAt(_data[i], d)]++;            for ( int j = 1; j < RADIX; ++j )            count[j] += count[j - 1];            int num = _right - _left + 1;        T* tmp = new T[num];            for ( int k = _right; k >= _left; --k )            tmp[--count[getBitAt(_data[k], d)]] = _data[k];            for ( int m = _left; m <= _right; ++m )            _data[m] = tmp[m - _left];            delete[] tmp;    }}; #endif //~_SORT_ALGORITHM_H_//这里是最后简单的测试代码：// main.cpp #include "SortAlgorithm.h" #include <iostream>using namespace std; int main(int argc,char* argv[]){    const int NUM = 20;     cout<<"原始数据为："<<endl;    int* data = BasicSortor<int>::initData(NUM);     BasicSortor<int>::printData(data,0,NUM - 1);    cout<<"排序数据为："<<endl;    BasicSortor<int>::bubbleSort(data,0,NUM - 1);    //BasicSortor<int>::selectSort(data,0,NUM - 1);    //BasicSortor<int>::insertSort(data,0,NUM - 1);    //BasicSortor<int>::quickSort(data,0,NUM - 1);    //BasicSortor<int>::mergeSort(data,0,NUM - 1);    //BasicSortor<int>::shellSort(data,0,NUM - 1);    //BasicSortor<int>::heapSort(data,0,NUM - 1);    //BasicSortor<int>::bucketSort(data,0,NUM - 1);    //BasicSortor<int>::radixSort(data,0,NUM - 1);     BasicSortor<int>::printData(data,0,NUM - 1);        return 0;}

评论