快速排序的思想跟归并排序的思想是一致的,也就是把一个大的问题,分成2个小的问题,然后再合并.
概念简单来讲就是,首先在待排序队列里面找到一个数,比这个数小的放到这个数的左边,比这个数大的放到数的右边,然后分别对左右两边进行递归排序.
代码如下:QuickSort.h
/******************************************************
* 快速排序步骤：QuickSort
* 1.找到关键点 FindPivot
* 2.吧容器分成两部分，小于关键点的部分在关键点左边，大于关键点的放到关键点右边DivideUp
* 3.递归关键点的左右两部分。QuickSort
*******************************************************/
#ifndef ___QUICK_SORT_H
#define ___QUICK_SORT_H
#include <assert.h>
namespace zk_sima
{
template<typename Iterator ,typename Object>
Object FindPivot(Iterator first,Iterator last,Object)
{
assert(last-first>0);
Iterator middle=first+(last-first)/2;
if(*middle>*(last-1)&&*middle>*first)
{
if(*(last-1)<*first)
{
Object temp=*first;
*first=*(last-1);
*(last-1)=temp;
}
}
else if(*middle<*(last-1)&&*middle<*first)
{
if(*first<*(last-1))
{
Object temp=*first;
*first=*(last-1);
*(last-1)=temp;
}
}
else
{
Object temp=*middle;
*middle=*(last-1);
*(last-1)=temp;
}
return *(last-1);
}
template<typename Iterator ,typename Object>
Iterator DivideUp(Iterator first,Iterator last,Object)
{
Object pivot=FindPivot(first,last,*first);
Iterator leftPoint=first,rightPoint=last-1-1;
while(leftPoint<rightPoint)
{
while(*leftPoint<pivot) ++leftPoint;
while(*rightPoint>pivot)--rightPoint;
//swap *leftPoint and *rightPoint
Object temp=*leftPoint;
*leftPoint=*rightPoint;
*rightPoint=temp;
++leftPoint;
--rightPoint;
}
*(last-1)=*leftPoint;
*leftPoint=pivot;
return leftPoint;
}
template<typename Iterator>
void QuickSort(Iterator first,Iterator last)
{
if(first>=last-1)
return ;
Iterator pivotIter=DivideUp(first,last,*first);
QuickSort(first,pivotIter);
QuickSort(pivotIter+1,last);
}
}
#endif
