题目

给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼1e9 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。

题目描述

将一个随机数组进行升序排列
包含 n 个整数（所有整数均在 1∼1e9 范围内）
//为了自己理解 给自己写的一篇题解

样例

10
9 5 6 2 1 3 0 4 7 8

输出
0 1 2 3 4 5 6 7 8 9

算法1

过程

样例
9 5 6 2 1;
过程
n=5,l=0,r=4;
i=-1,j=5,x=6;
第一个dowhile
i，j先自加减1//在自己发现的一些问题会提到这一点
i=0，j=4;
i=0;9不满足<6
i指针停止
第二个dowhile
j=4; 1不满足>6
j指针停止
swap(a[i],a[j]);
1 5 6 2 9;
同理
i+=2 j–//满足条件的情况
1 5 2 6 9//所以6 2 互换
i=2,j=3;
递归第二阶段
l~j 0~3
1 5 2为前段递归
6 9 为后端递归
也同第一大部
1 2 5
6 9
所以 最后1 2 5 6 9
//本来想写10个数的例题的 发现字有点多

时间复杂度

不知道对时间复杂度理解是否正确
O(nlogn)
在quick——sort函数里 用了递归所以有一个logn的形式
前面有while来循环，所以是n的形式
最后复杂度就为O(nlogn)；

自己写的时候的一些问题

1、为什么不用while 用dowhile
2、用if(l>r)会怎么样
3、对比a[(l+r)/2]和a[l+r>>1]
4、对于1e5+10的理解

1、为什么不用while

//为什么不用
while(a[i] < x) i++;
while(a[j] > x) j--;
//当a[i]和a[j]都为 x 时, i和j都不改变,导致在while内死循环
//而dowhile 至少会使i j至少执行一次，不会出现都等于x卡死的情况

2、用if(l>r)会怎么样
在quick_sort函数一开始的判断
当初抄代码时漏写了= hhhhh
其实用到这个判断的情况也就只有两种时候
一是n=1时 只有一个数时
二是递归到最后面只剩下一个数时，用它来退出函数
如果没有这个判断 或 判断条件里不写>= 会退出不了函数 所以会超时

3、对比a[(l+r)/2]和a[l+r>>1]
以前学习时没有注意过位运算，没想到差别还挺大（在这道题里）
因为我当初用第一个我没有ac，发现会超时，最后知道了计算机内用>>会更快
所以养成习惯 乘除2的n次时 用<<和>>符号
这两符号的优先级 是劣于+-的 所以可以不写括号
搞不清也可以都写 这样就不用背运算符优先级顺序了

4、对于1e5+10的理解
数据范围是
1≤n≤100000
比动态创建数组方便的多
+10是为了处理一些边界问题
主要是边界问题懒得处理也懒的想 +10会方便很多

参考文献

y总所讲内容
(自己想不出来)

C++ 代码

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
void quick_sort(int a[],int l,int r)
{
    if(l>=r)return;
    int i=l-1,j=r+1,x=a[l+r>>1];
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j)swap(a[i],a[j]);
    }
    quick_sort(a,l,j);
    quick_sort(a,j+1,r);
}
int main ()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    quick_sort(a,0,n-1);
    for(int i=0;i<n;i++)printf("%d ",a[i]);
    return 0;
}