排序的算法集中到一起了，包括冒泡排序、选择排序、插入排序，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;
}

评论