快排
-
对于数组A[p...r]进行快排：
主要思想：将数组A[p...r]划分为A[p...q-1]和A[q+1...r]，使得左区间的每一个元素小于A[q]，右区间每一个元素大于A[q]。实现方法：（伪代码）
QUICKSORT(A,p,r)
1 if p<r
2 q=PARTITION(A,p,r) //寻找划分中点
3 QUICKSORT(A,p,q-1)
4 QUICKSORT(A,q+1,r)
其中PARTITION函数极为关键
PARTITION(A,q,r)
1 x=A[r] //假设要置于中间位置的数（即排序后的A[p]）是数组最后一个
2 i=p-1
3 for j=p to r-1 //始终保证A[p..i]中所有元素是小于x的
4 if A[j]<=x
5 i=i+1
6 exchange A[i] with A[j]
7 exchange A[i+1] with A[r]
8 return i+1
但是每次选择最后一个数作为划分中点会导致在有些情况下（如数组本来就有序）复杂度极高，所以，这里采取另一种分划方式
RANDOMIZED-PARTITION(A,p,r)
1 i=RANDOM(p,r)
2 exchange A[r] with A[i]
3 return PARTITION(A,p,r)
ps：
这种划分方式也提供了一种快速找出数组A[p...r]中第i小值的一种方法
RANDOMIZED-SELECT(A,p,r,i)
1 if p==r
2 return A[p]
3 q=RANDOMIZED-PARTITION(A,p,r)
4 k=q-p+1
5 if i==k
6 return A[q]
7 else if i<k
8 return RANDOMIZED-SELECT(A,p,q-1,i)
9 else
10 return RANDOMIZED-SELECT(A,q+1,r,i-k)
-
了解一下三中值法
