题目描述
给定你一个长度为$n$的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在1~$10^9$范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
$1 \le n \le 100000$
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
解题报告
题意理解
这道题目显然是要我们将一个无序数列排序,成为具有升序性质的升序序列.
算法处理
一道排序题目,数据范围是关键,我们发现这道题目只能让我们使用$O(nlogn)$的算法,显然我们可以选择快速排序,归并排序等算法,这里我们就使用快速排序.
时间复杂度图
快排思想图
代码实现
#include <iostream>
using namespace std;
const int N = 1000010;
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];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > 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);
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/39784/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
C++ STL快速算法
#include <bits/stdc++.h>
using namespace std;
const int N=1000000+100;
int a[N],n,m,i,j;
int main()//C++ Stl使人快乐
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
可以AC。但是我有一个小问题，以3 1 2 4 5为例，第一轮划分基准元素是2，划分最后结果是2 1 3 4 5。从快速排序每轮划分将基准元素放在正确的位置上来说，这个结果好像是错误的，1应该在2的左边。
后面还要对两个子列进行递归
第一轮划分的基准元素不是3吗？（x=q[l]）
q[l]过不了，被数据卡掉了
这个是对的，视频里用的这个方法和咱平时数据结构书上的方法不大一样，这个是从中间劈开，第三个数左边的都小于等于，第三个数及右边的都大于等于。你这个基准元素放在正确的位置是另一种实现方法，我编写提交了一下也成功了。但这两种方法都能得到排序的正确结果
代码不是按快排基准元素规则来的。
第一轮是会有这样的情况的，不过这种情况下至少 基准元素原位置的左右两侧划分好了（左边都小于基准数原位置的那个数3，右边都大于3）；剩下的在接下来的好几轮中会调过来顺序的。
j 的位置最后是1，也就是划分为[2 1] 和 [3 4 5]，前边保证小于等于2，后边保证大于等于2就可以了。
C++ Stl使人快乐
为啥按y总那个模板写大数据检测
会超时
我也超时了
我也是，换成x = q[l + r >> 1]；后就不会了
一样，换成中间的那个就不会超时，好奇怪
它这个指针的边界问题就挺奇怪的，我看了也没大佬详细解释
应该是因为数据符合了快排的最坏情况，选取的枢轴点是当前排序的最值。
快排最优情况下形成一颗平衡二叉树，此时，若有n个数，则需要遍历n次，递归处理logn次，时间复杂度是O（nlogn）。当最坏的情况下，树退化成链，递归处理不再是logn次而是n次，复杂度变为O(n*n）。解决办法是在快速排序前先对序列进行随机排列（利用洗牌算法），防止极端数据的出现。要么就换一个x。
https://blog.csdn.net/qq_36533552/article/details/106328719
这里讲了快排最好和最坏时间复杂度。
MLE?? 为啥
没有加 if (l >= r) return; 的判断
# 6
## 666
想问一下为什么可以这样写
x = q[l + r >> 1]；
但写成
m = l + r >> 1;
再用 q[m] 的形式替代 x 去比较就不对呢
m是下标，在排序中q[m]的值可能会改变，再用去q[m]就变了
do i ++ ; while (q[i] < x);
do j – ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
这个地方，如果两边都碰到了一个等于轴点的数，不久死循环了，ij都动不了了，两边不停的交换。
所以是dowhile啊。。。先对i和j操作再判断
我一开始也是这么认为，调试一下就懂了。do…while循环会先操作，就能动了
用while的话会死循环的，dowhile不会
爱来自两年后，谢谢你，解决了困扰我的问题
do i ++ ; while (q[i] < x);
do j – ; while (q[j] > x);
为啥把 < 和 > 改成 <= 和 >= 就会爆内存呢？
去模拟一下就知道了，最后可能i=l-2或者j=r+2，虽然不会报错成下标越界但是会导致无限循环
#include[HTML_REMOVED]
using namespace std;
const int N=100010;
int n,a[N];
int Partition(int a[],int low,int high){
int pivot=a[low];
while(low[HTML_REMOVED]=pivot) high–;
a[low]=a[high];
while(low<high && a[low]<=pivot) low;
a[high]=a[low];
}
a[low]=pivot;
return low;
}
void QuiteSort(int a[],int low,int high){
if(low<high){
int pivotpos=Partition(a,low,high);
QuiteSort(a,low,pivotpos-1);
QuiteSort(a,pivotpos+1,high);
}
}
int main(){
scanf(“%d”, &n);
for(int i=1;i<=n;i){
scanf(“%d”, &a[i]);
}
QuiteSort(a,1,n);
for(int i=1;i<=n;i++){
printf(“%d “, a[i]);
}
}
为什么会超时
ios::sync_with_stdio(false);这啥意思？
加快cin速度，但是scanf语句作废
这不是很爽，cin写起来多快啊，现在效率也高了。那这影响cout,printf吗
你可以理解为他关闭了输入输出同步流，这样cin和cout还会比scanf和printf快
不错不错🥹
超时怎么改啊
同求快排动图，怎么生成的
https://www.cnblogs.com/onepixel/articles/7674659.html
这个网址的跟他的动图一样。。
秦佬，快排的空间复杂度应该是$O(logn)$
佬，那个快排思想图是咋做的
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html 这个网站
一直想不通递归那步，比如说是递归左边，那它不是会一直递归左半部分吗，右半部分怎么办
有递归终止条件的，在quick_sort()的第一行就是：if (l >= r) return;
我知道可以终止，但就是没想明白怎么处理的左半边的右半部分或者是右半边的左半部分，
程序调用的顺序你可以画出来就理解。 就像栈一样。
再或者你可以去搜一下 递归 的知识点。
好的 谢谢
我再理解下
x = q[l + r >> 1]
这个是什么意思，y总视频里写的不是这个，他的代码可以通过，我按照那样子写就不可以，
但是博主你的可以通过，那这个是什么意思呢？
l+r>>1 == (l+r)/2
位运算右移一位，就是除以2😀
谢谢你
为什么（l+r）/2不可以通过而这个可以通过
CPU中位运算的速度比除法运算快
为啥一模一样的代码我的就不行复制过去就行
语言没选对吧，这个是c++的
我也是这样的
#include[HTML_REMOVED]
using namespace std;
const int N = 100010;
int a[N];
int main()
{
int n;
scanf(“%d”, &n);
for (int i = 1; i <= n; i ){
scanf(“%d”, &a[i]);
}
sort(a+1,a+1+n);
for (int i = 1; i <= n; i ){
printf(“%d “,&a[i]);
}
return 0;
}
为什么标准库都不行呀|||
因为你没有i++
写个取随机的基准数就这么难吗。。。