快速排序
快速排序概述
快速排序是一种分治算法,分而治之,每次将序列分成两部分,递归处理,进而求得答案
快排正如y总说的那样,它的边界问题很多。对于这种情况,把模板背了就好,没有必要过分纠结一些细节(当然知道也更好)。追求效率的话,背过即可
快排算法分析
1. 确定分界点
分界点可以是$l ~ r$任意一点,常用为$l, r, (l + r >> 1)$, 分界点为$x$
2. 调整范围
需要得到的结果是左部分的数均小于等于枢纽元,右侧均大于等于枢纽元。
(1)开辟两个数组,遍历时候,小于等于的放在第一个数组,大于放第二个数组最后合并(空间浪费)
(2)双指针算法(维护次序)。 $i$ 从左到右遇到第一个 $>= x$, 停下来, $j$从右到左,遇到第一个 $<=x$的停下来。二者交换。最终也可以分成两个满足需求的部分
3. 递归处理
递归处理左部分与右部分。递归结束条件, $l >= r$,即区间内没有数字或者只有一个数字的时候截止递归
常见问题
1. Q: $i$和$j$在等于的情况下交换,是不是不必要的?
A: 如果我们不在等于的时候交换,那么$i, j$就很容易越界,会出现很多边界问题,为了解决这个问题,将会让代码复杂化,这个代价相比于多出的微不足道的时间是要多很多的。
2. Q: 分界点取$j$,用$i$可不可以?
A: 可以,但是二者需要对称着写,同时要注意取得枢纽元,比如用i的话,就不能取左边界作枢纽元,中点也需要像上取证,否则就会出现死循环,($eg$,课上的例子,$0,2$)
3. 模板保证的是左部分$<= x$, 右部分 $>=x$,但分界点不一定是$x$。这与在教科书上看到的工程式写法不同,那种写法一般最后有一次交换操作
4. 枢纽元选取的问题,个人一般使用的是中点,采用左右端点,如果遇到不太好的数列,比如单调递增/递减,就会出$O(N^{2})$的时间复杂度。中点相对于端点就好了很多(当然也不是最好的,三数取中法应该是不错的,取随机数代价也是很大的)
时间复杂度
平均情况$O(n\log n)$,最坏情况$O(n^2)$
$c++$ 一秒计算$10^8$ 到$10^9$次
平均情况得不到200w,可以计算出来
代码
#include <iostream>
using namespace std;
const int N = 100010;//多10个保险,可以防止一些越界问题
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;//递归结束条件,范围内没有数字或者只有一个数字
int i = l - 1, j = r + 1, x = q[l + r >> 1];//因为我们每次是指针先移动,再判断,所以定义i,j为端点两侧
while (i < j)
{
do i ++ ; while (q[i] < x);//从左向右找到第一个 >= x的数字
do j -- ; while (q[j] > x);//从右向左找到第一个 <= x的数字
if (i < j) swap(q[i], q[j]);//满足条件则交换
}
quick_sort(q, l, j);//递归处理左右两部分
quick_sort(q, j + 1, r);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
quick_sort(q, 0, n - 1);//左右区间端点是0, n - 1
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
一些碎碎念
其实大家题解写的都很不错了,我一个月前入门的时候,有一些小小的建议
比如说,听的是y总的代码,题解各巨经常是各显神通,各式优化,对当时初学的我对应起来有一些不方便。
又或者是,阅读习惯的问题,有的大佬喜欢几句点播式的,有的则是事无巨细,需要找一个适合自己的题解。
这次,我二刷,顺道尽量完善题解,争取覆盖基础课内容,代码就采用y总的打卡代码,同时尽可能的与y总上课讲解内容做到一致,方便大家阅读。
如果有我参考别的巨佬的代码,找到比较好的优化,会放在最后作为补充内容,hhh
如果有什么更好的排版,也希望大家能告诉我,我去完善一下
争取系列不太监!(笑,希望别和总管一样,写着写着就太监了,hh)