快排
要排a[0].....a[n-1]
先选取一个元素（如最左侧的元素）作为中轴元素
经过n-1次比较
得
元素<=中轴 中轴元素 >=中轴
分析 ： Tmin(n) = 2* T(n/2)+n-1 = θ(n* logn)
最坏 ： Tmax(n) = T(0)+T(n-1)+n-1 = θ(n^2)
快排中的分区算法（原地分区）
Paritition(A,p,q)
{
x<-A[p] ;//分支点
i= p//分界点的位置
for(j =p;j<=q;j++)
{
if(A[j]<=x)//比x大的依次放左边
{
i++;
Swap(A[i],A[j]);//交换
}
}//end for
Swap(A[i],A[p]);
return i;
}
template<class T>
int Partition (T *a,int p,int q)
{
//对于a[p]...a[q]
//以a[p]作为分界元素
T x = a[p]; //记录下分界点的值
int i = p;//用于记录分界点的位置
for(int j = p + 1;j<=q;j++)
{
if(!x<a[j])
{
i++;
Swap(a[i],a[j]);
}
}
swap(a[p],a[i]);
return i;
}
template <class T>
void Qsort(T *a,int l,int r)
{
if(r<=l) return;
int m = paritition(a,l,r)l//n-1次比较
//l....m...r
Qsort(a,l,m-1);
Qsort(a,m+1,r);
}
第k小问题
在一个序列或集合中找出"第k小"元素
解题方法：类快排
若 k =m 则找到 即是 a[m-1]
否则或左或右的去查找
template <class T>
T kthElement( T *n, int l, int r,int k)
{
//从a[l]....a[r]中找第k小
if(r<=l) return a[l];
int m = paritition(a,l,r);//分区（如原地分区）
int kk = m- l +1;
if(k==kk) return a[m];
else if( k<kk)
{
return kthElement(a,l,m-1,k);
}
else
{
return kthElement(a,m+1,r,k-kk);
}
}
分析：
- 最好：经过n-1比较分区后，分界点即是
- 最坏：T(n) = (n-1)+T(n-1)
设：分区后，分界点所处的位置有比例，如1/3* n,2/3* n
则 T(n) = (n-1) + T(2/3* n) = θ(n) 线性级别