DraculaW

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  19 随笔 :: 0 文章 :: 7 评论 :: 0 Trackbacks
/////////////////////////////////////////////////////////////////////////////////

// The Sort //

// //

/////////////////////////////////////////////////////////////////////////////////
#ifndef _SORT_H_

#define _SORT_H_
/////////////////////////////////////////////////////////////////////////////////

// The QuickSort //

// //

/////////////////////////////////////////////////////////////////////////////////
template<typename T>

int Quick(T* a, int s, int e)

{

    T t = a[e];

    int i = s - 1;

    for(int j = s; j < e; j++ )

        if(a[j] <= t)

        {

            i++;

            swap(a[j],a[i]);

        }



        swap(a[i+1], a[e]);

        return i+1;

}
template<typename T>

void QuickSort(T* a, int s, int e)

{

    if( s < e )

    {

        int i = Quick(a, s, e);

        //int i = part(a, s, e);

        QuickSort(a, s, i-1);

        QuickSort(a, i+1, e);

    }

}
/////////////////////////////////////////////////////////////////////////////////

// The HeapSort //

// //

/////////////////////////////////////////////////////////////////////////////////

inline int left(int i)

{

    return 2*i+1;

}
inline int right(int i)

{

    return 2*i+2;

}
template<typename T>

void HeapHy(T* a, int n, int i)

{

    int big = i;

    //first find the lage of i, left(i),right(i)

    if(left(i) < n)

    {

        big = a[i]>a[left(i)]?(i):(left(i));

        if(right(i) < n)

            big = a[big]>a[right(i)]?(big):(right(i));

    }

    //and if the i not the biggest change pos i with the bigest

    if(i!=big)

    {

        swap(a[i], a[big]);

        //then HeapHy(a, n, bigest)

        HeapHy(a, n, big);

    }

}
template<typename T>

void BuildHeap(T* a, int n)

{

    for(int i = n/2; i > -1; i--)

        HeapHy(a, n, i);

}
template<typename T>

void HeapSort(T* a, int n)

{

    BuildHeap(a, n);

    for(int i=n-1; i>0; i--)

    {

        swap(a[0], a[i]);

        HeapHy(a, i, 0);

    }

}
/////////////////////////////////////////////////////////////////////////////////

// The ShellSort //

// //

/////////////////////////////////////////////////////////////////////////////////
template<typename T>

void ShellSort(T* a, int s)

{

    T t;

    int i,j,k;

    for(i=s/2; i>0; i=i/3)

    {

        for(j=i; j<s; j++)

        {

            t = a[j];

            for(k=j-i; k>-1; k-=i)

            {

                if(a[k]>t)

                    a[k+i] = a[k];

            }

            a[k+i] = t;

        }

    }

}
#endif //_SORT_H_
posted on 2007-11-15 20:27 DraculaW 阅读(127) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理