分治
快速排序基于算法中很重要的思想是 分治。
- 分解（Divide）：将原问题分为一系列子问题
- 解决（Conquer）：递归的解决子问题。如果子问题足够小，直接解决子问题
- 合并（Combine）：将子问题的结果合并为原问题的
子问题解决方法
选取一个基准元素（pivot）
比pivot小的放到pivot左边，比pivot大的放到pivot右边
对pivot左边的序列和右边的序列分别递归的执行步骤1和步骤2
伪代码：
QUICKSORT(A, p, r)
if p < r
q = PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
//将数组分为两部分，返回临界值下标
PARTITION(A, p, r)
x = A[r] //以最后一个数为主元（pivot element）
i = p-1 //小于主元子数组的下标上限
for j = p to r-1
if A[j] <= x
i = i+1 //增加小于主元子数组的大小
exchange A[i] with A[j] //将A[j]加入小于主元的子数组
exchange A[i+1] with A[r] //将主元从数组末尾移动至子数组之间
return i + 1
源码
partition示例
void quickSort(vector<int> &vi, int low, int up)
{
if(low < up)
{
int mid = partition(vi, low, up);
//Watch out! The mid position is on the place, so we don't need to consider it again.
//That's why below is mid-1, not mid! Otherwise it will occur overflow error!!!
quickSort(vi, low, mid-1);
quickSort(vi, mid+1, up);
}
}
int partition(vector<int> &vi, int low, int up)
{
int pivot = vi[up];
int i = low-1;
for (int j = low; j < up; j++)
{
if(vi[j] <= pivot)
{
i++;
swap(vi[i], vi[j]); //i+1是大于pivot的区域的第一个元素
}
}
swap(vi[i+1], vi[up]);
return i+1;
}
应用partition
剑指offer：
- 最小的K个数
- 数组中出现次数超过一半的数
