quiksort.h

c++编程宝典源码及Quincy99编译器 是《标准C++编程宝典》电子工业出版社的光盘

////////////////////////////////////////
// File Name: Quiksort.h
////////////////////////////////////////
#ifndef QUIKSORT_H
#define QUIKSORT_H

template<class T>
inline void swap(T& t1, T& t2)
{
    T hold = t2;
    t2 = t1;
    t1 = hold;
}

template<class T>
void quicksort(T *array, int hi, int lo = 0)
{
    while (hi > lo)
    {
        int i = lo;
        int j = hi;

        // Sort everything higher than median above it
        // and everything lower below it.
        do
        {
            while (array[i] < array[lo] && i < j)
                i++;
            while (array[--j] > array[lo])
                ;
            if (i < j)
                swap(array[j], array[i]);
        }
        while (i < j);

        swap(array[lo], array[j]);

        // Sort the set with the fewer number of elements.
        if (j - lo > hi - (j+1))
        {
            // Sort the bottom set.
            quicksort(array, j-1, lo);
            lo = j+1;
        }
        else
        {
            // Sort the top set.
            quicksort(array, hi, j+1);
            hi = j-1;
        }
    }
}

#endif