l

成都手游码农一枚
随笔 - 32, 文章 - 0, 评论 - 117, 引用 - 0
数据加载中……

[C++]快速排序

最近学数据结构,就试着写了下,虽然结果正常,但也难免有错,希望能指出。

/*
快速排序。
*/

#include 
<iostream>

using namespace std;

/*交换元素*/
template
<typename _Ty>
inline 
void Swap(_Ty& _f,_Ty& _s){
    _Ty _t
=_f;
    _f
=_s;_s=_t;
}


/*一次排序*/
template
<typename _Ty>
int Partition(_Ty* _arr,int _beg,int _end)
{
    
int _index=_beg;
    _Ty _p
=_arr[_beg];

    
while(true)
    
{    //左移后索引 直到一个小于_p的值
        while(_beg<_end&&_arr[_end]>=_p)--_end;
        
//右移前索引 直到一个大于_p的值 ++跳过_p的检验 
        while(_beg<_end&&_arr[++_beg]<=_p);
        
//前后索引相遇退出
        if(_beg==_end)break;
        
//交换前后索引处的值,使的 左<_p<右
        Swap(_arr[_beg],_arr[_end]);
    }

    
//将_p与索引处值交换
    Swap(_arr[_beg],_arr[_index]);
    
return _beg;
}


/*排序*/
template
<typename _Ty>
void QSort(_Ty* _arr,int _beg,int _end)
{
    
if(_beg>=_end)return;

    
int _pos=Partition(_arr,_beg,_end);

    QSort(_arr,_beg,_pos
-1);
    QSort(_arr,_pos
+1,_end);
}


/*快速排序*/
template
<typename _Ty>
void QuikeSort(_Ty* _arr,int _size)
{
    QSort(_arr,
0,_size-1);
}



/*打印数组*/
template
<typename _Ty>
void OutArr(_Ty* _arr,int _size,ostream& _Os=cout)
{
    
for(int i=0;i<_size;++i)
        _Os
<<_arr[i]<<" ";
    _Os
<<endl;
}


int main()
{
    
int arr[100];

    
for(int i=0;i<100;arr[i++]=rand()%100);

    QuikeSort(arr,
100);

    OutArr(arr,
100);
}

posted on 2009-11-04 16:52 l1989 阅读(300) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理