一、快速排序算法思想或步骤
-
分解： 数组A[p…r]被划分为两个子数组A[p…q-1]和A[q+1…r]，使得A[q]为大小居中的数，左侧A[p…q-1]中的每个元素都小于等于它，而右边A[q+1…r]每个元素都大于等于它。
-
解决： 通过递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]进行排序。
-
合并： 因为子数组都是在原址进行排序，所以不需要合并，原数组已经有序。
通过上述描述发现：划分是问题的关键
算法的就可以写出如下框架：
void quickSort(A,p,r){
if(p<r){
q = divAlgo(A,p,r);
quick(A,p,q-1);
quick(A,q+1,r);
}
}
二、划分算法divAlgo：快排算法的关键
下面介绍几种划分的思路和算法
1. 一遍单向扫描法
首先确定一个基元，一般基元确定为区间的第一个元素，然后通过两个指针pi,pj来进行移动划分，初始值pi为该区间的第二个位置，即pi=1;pj为该区间的最后一个为pj = size()-1。划分过程大致如下：
在pi小于等于pj的情况下，执行下面步骤：
- 不断向后移动pi指针，直到pi所指元素大于基元。
- 交换pi和pj所指内容，pj前移一位
- 执行第1步
- 当pi小于等于pj条件不满足时，交换pj所指元素和基元，并返回pj。
有了上述步骤，则可以轻松写出相应的划分算法。
int divAlgo(vector<int> &src,int p,int r){
int baseVal = src[p];
int pi = p + 1,pj = r;
while (pi <= pj){
if(src[pi] <= baseVal) ++pi;
else swap(src[pi],src[pj--]);
}
swap(src[p],src[pj]);
return pj;
}
那么接着使用这个划分算法测试一下能否完成排序。
#include<bits/stdc++.h>
using namespace std;
int divAlgo(vector<int> &src,int p,int r){
int baseVal = src[p];
int pi = p + 1,pj = r;
while (pi <= pj){
if(src[pi] <= baseVal) ++pi;
else swap(src[pi],src[pj--]);
}
swap(src[p],src[pj]);
return pj;
}
void quickSort(vector<int> &src,int p,int r){
if(p<r){
int q = divAlgo(src,p,r);
quickSort(src,p,q-1);
quickSort(src,q+1,r);
}
}
int main(){
vector<int> ad{4,3,2,5,1,8,9};
quickSort(ad,0,ad.size()-1);
copy(ad.begin(),ad.end(),ostream_iterator<int>(cout," "));
return 0;
}
/*
1 2 3 4 5 8 9
*/
2. 双向扫描法
双向扫描的思路为：头指针往中间进行扫描，尾指针往中间进行扫描，左边找到大于对应基元的位置，右边找到小于基元的位置，进行交换，继续扫描。
有了单向扫描的基础，该代码就比较好写，代码如下：
int divAlgo2(vector<int> &src,int p,int r){
int baseVal = src[p];
int pi = p + 1,pj = r;
while (pi <= pj){
while(pi <= pj && src[pi] <= baseVal) ++pi;
while(pi <= pj && src[pj] > baseVal) --pj;
if(pi < pj)
swap(src[pi],src[pj]);
}
swap(src[p],src[pj]);
return pj;
}
测试代码如下：
#include<bits/stdc++.h>
using namespace std;
int divAlgo2(vector<int> &src,int p,int r){
int baseVal = src[p];
int pi = p + 1,pj = r;
while (pi <= pj){
while(pi <= pj && src[pi] <= baseVal) ++pi;
while(pi <= pj && src[pj] > baseVal) --pj;
if(pi < pj)
swap(src[pi],src[pj]);
}
swap(src[p],src[pj]);
return pj;
}
void quickSort(vector<int> &src,int p,int r){
if(p<r){
int q = divAlgo2(src,p,r);
quickSort(src,p,q-1);
quickSort(src,q+1,r);
}
}
int main(){
vector<int> ad{4,3,2,5,1,8,9};
quickSort(ad,0,ad.size()-1);
copy(ad.begin(),ad.end(),ostream_iterator<int>(cout," "));
return 0;
}
/*
1 2 3 4 5 8 9
*/
三、快排存在的问题
- 如果原数组已经有序，算法效率不好
- 数组长度较大时，时间复杂度高
- 选取基元的方法本身存在缺陷。
四、优化
- 待排序元素个数比较少时，使用插入排序
- 快排时，选取基元使用绝对中值法 和三点中值法
- 排序元素较多时，使用堆排序
结合这三点，可以封装一个跟标准库中sort函数思想差不多的排序算法。
这三种优化，1和3后面会有相应的排序算法，针对2，修改divAlgo函数，三点中值法：选取基元尽可能地可以将数组分为个数相同的两半【选取左、中、右三个元素中中间大的元素作为基元】，或者绝对中值法：选取数组中间位置元素作为基元。
五、使用快排思想找数组中第k大元素框架
主框架都是这个，不同的是找枢纽的部分需要修改
int findKth(vector<int>& a, int low, int high, int k){//找第k个
int p = divAlgo(a, low, high);
if (k == p - low + 1)
return a[p];
else if (k - 1 < p - low)//则第k大的元素在前半段
return findKth(a, low, p - 1, k);
else //则第k大的元素在后半段
return findKth(a, p + 1, high, k - p + low - 1);
}
int divAlgo(vector<int> &src,int p,int r){
int baseVal = src[p];
int pi = p + 1,pj = r;
while (pi <= pj){
if(src[pi] <= baseVal) ++pi;//找第k小的，当变为>=时找第k大
else swap(src[pi],src[pj--]);
}
swap(src[p],src[pj]);
return pj;
}
最小的k个数
方法1：优先队列，大顶堆
vector<int> GetLeastNumbers_Solution_1(vector<int> input, int k) {
if(k == 0 || input.empty()) return vector<int>();
// priority_queue默认为大顶堆，声明为priority_queue<T,vector<T>,less<T>>
// priority_queue<T, vector<T>, greater<T>>为小顶堆
priority_queue<int> pq_int;// 默认是大顶堆，也就是top处的元素为当前优先队列的最大值
vector<int> res;
for(int i = 0; i < input.size(); ++i){
if(pq_int.size() < k){
pq_int.push(input[i]);
}else{
if(pq_int.top() > input[i]){
pq_int.pop();
pq_int.push(input[i]);
}
}
}
while(!pq_int.empty()){
res.push_back(pq_int.top());
pq_int.pop();
}
return res;
}
方法2：快排
// 快排思想，进行局部性排序
bool flag = true;
vector<int> GetLeastNumbers_Solution(vector<int> input, int k){
if(0 == k || input.empty()) return {};
quickSort(input, 0, input.size() - 1, k);
return vector<int>(input.begin(), input.begin() + k);
}
int divide(vector<int> &data, int l, int r){
int base_val = data[l];
int pi = l + 1, pj = r;
while(pi <= pj){
while(pi <= pj && data[pi] <= base_val) ++pi;
while(pi <= pj && data[pj] >= base_val) --pj;
if(pi < pj) swap(data[pi++], data[pj++]);
}
swap(data[l], data[pj]);
return pj;
}
void quickSort(vector<int> &data, int pi, int pj, const int &k){
if(!flag || pi >= pj) return;
int index = divide(data, pi, pj);
if(index > k){
quickSort(data, pi, index - 1, k);
}else if(index < k){
quickSort(data, index + 1, pj, k);
}else{
flag = false;
return;
}
}
