当前位置：首页 > article >正文

十大排序算法：快速排序算法

article 2025/9/14 4:47:19

一、快速排序算法思想或步骤

分解： 数组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;}}