排序算法-鸡尾酒排序

鸡尾酒排序是冒泡排序的一种改进算法，效果稍好（可能减少交换次数）。先从头比到尾找到最大（或最小），然后从尾比到头找到最小（或最大）。

时间复杂度：o(n^2)，比较总次数为((n-1)+1)*(n-1)/2=n*(n-1)/2

C代码：

template <typename T>

void cocktail_sort( T t[], int size, bool bASC = true )

{

    T temp;

    int left = 0;

    int right = size-1;

    while( left<right )

    {

        for ( int i=left; i<right; ++i )

        {

            if ( (bASC && t[i]>t[i+1]) || (!bASC && t[i]<t[i+1]) )

            {

                temp = t[i+1];

                t[i+1] = t[i];

                t[i] = temp;

            }

        }

        --right;

        for ( int i=right; i>left; --i )

        {

            if ( (bASC && t[i-1]>t[i]) || (!bASC && t[i-1]<t[i]) )

            {

                temp = t[i];

                t[i] = t[i-1];

                t[i-1] = temp;

            }

        }//end of for ( int i=right; i>left; --i )

        ++left;

    }//end of while( left<right )

}