最近学数据结构,就试着写了下,虽然结果正常,但也难免有错,希望能指出。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
快速排序。
*/
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*交换元素*/
template<typename _Ty>
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline void Swap(_Ty& _f,_Ty& _s)
{
_Ty _t=_f;
_f=_s;_s=_t;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*一次排序*/
template<typename _Ty>
int Partition(_Ty* _arr,int _beg,int _end)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int _index=_beg;
_Ty _p=_arr[_beg];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(true)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ //左移后索引 直到一个小于_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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*排序*/
template<typename _Ty>
void QSort(_Ty* _arr,int _beg,int _end)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(_beg>=_end)return;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int _pos=Partition(_arr,_beg,_end);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
QSort(_arr,_beg,_pos-1);
QSort(_arr,_pos+1,_end);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*快速排序*/
template<typename _Ty>
void QuikeSort(_Ty* _arr,int _size)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
QSort(_arr,0,_size-1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*打印数组*/
template<typename _Ty>
void OutArr(_Ty* _arr,int _size,ostream& _Os=cout)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
for(int i=0;i<_size;++i)
_Os<<_arr[i]<<" ";
_Os<<endl;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int arr[100];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(int i=0;i<100;arr[i++]=rand()%100);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
QuikeSort(arr,100);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
OutArr(arr,100);
}