各种排序

数据定义

#define _LZZ_BEGIN namespace lzzs {
#define _LZZ_END }

_LZZ_BEGIN
    template<class T>
    void exchange(T & f, T & s)
    {
        T t = f;
        f = s;
        s = t;
    };
_LZZ_END

冒泡

    void bubble_sort(DataType datas[], int begin, int end)
    {
        for (int i = end - 1; i > begin; i --)
            for (int j = begin; j < i; j ++)
                if (datas[j] > datas[j + 1])
                    exchange(datas[j], datas[j + 1]);
    }

    void bubble_sort( DataType datas[], int len )
    {
        bubble_sort(datas, 0, len);
    }

插入

    void insert_sort(DataType datas[], int begin, int end)
    {
        DataType tdt;
        for (int i = begin + 1; i < end; ++i)
        {
            tdt = datas[i];
            int j = i - 1;
            for (; j >= begin && datas[j] > tdt; --j)
                datas[j + 1] = datas[j];
            datas[j + 1] = tdt;
        }
    }

    void insert_sort( DataType datas[], int len )
    {
        insert_sort(datas, 0, len);
    }

快排

    int partition(DataType datas[], int begin, int end)
    {
        int last = end - 1;
        int standard = last;
        int i = begin - 1;
        int j = begin;
        while (j < last)
        {
            if (datas[j] <= datas[standard])
                exchange(datas[++ i], datas[j]);
            j ++;
        }
        exchange(datas[++ i], datas[j]);
        return i;
    }

    void quick_sort(DataType datas[], int begin, int end)
    {
        if (begin < end - 1)
        {
            int mid = partition(datas, begin, end);
            quick_sort(datas, begin, mid);
            quick_sort(datas, mid + 1, end);
        }

    }

    void quick_sort( DataType datas[], int len )
    {
        quick_sort(datas, 0, len);
    }

堆排

#define P(child) ( ( ( child ) - 1) / 2 )
#define L(parent) ( ( 2 * ( parent ) ) + 1 )
#define R(parent) ( ( 2 * ( parent ) ) + 2 )

    void heap_up( DataType datas[], int len, int targetidx)
    {
        if (targetidx >= len || targetidx <= 0)
            return;
        int pidx = P(targetidx);
        if (datas[pidx] < datas[targetidx])
        {
            exchange(datas[pidx], datas[targetidx]);
            heap_up(datas, len, pidx);
        }
    }
    void heap_down( DataType datas[], int len, int targetidx)
    {
        if (targetidx >= len || targetidx < 0)
            return;
        int maxidx = targetidx;
        int lidx = L(targetidx);
        if ( lidx < len &&  datas[lidx] > datas[maxidx])
            maxidx = lidx;
        int ridx = R(targetidx);
        if ( ridx < len &&  datas[ridx] > datas[maxidx])
            maxidx = ridx;
        if (maxidx != targetidx)
        {
            exchange(datas[maxidx], datas[targetidx]);
            heap_down(datas, len, maxidx);
        }
    }

    void heap_build( DataType datas[], int len )
    {
        for (int i = P(len - 1); i >= 0; -- i)
            heap_down(datas, len, i);
    }

    void heap_sort( DataType datas[], int len )
    {
        heap_build( datas, len );
        for (int i = len - 1; i > 0; --i)
        {
            exchange( datas[0], datas[i] );
            heap_down(datas, i, 0);
        }
    }

    void heap_sort( DataType datas[], int begin, int end )
    {
        heap_sort(datas + begin, end - begin);
    }