关于快排的笔记（quick_sort)
题目：
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在1~109109范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：1 2 3 4 5
正文：快速排序即在给定的数列中随便找一个数赋值到X上（找最中间的数据对于整个程序所花费的时间应该是较少的）
（此处默认快速排序为升序排序），
同时定义左边的指针和右边的指针在数列最两侧，设i为左边的指针，j为右边的指针，同时先从左侧开始寻找，若i指代的数大于X，
即停止i++,然后再从右侧j来寻找，直到找到j指代的数小于X并停止寻找，此时恰好可以使i和j互换，达到交换的目的;
当指针交汇，再从已经以X为分界的两个区间再进行上述操作（通过递归执行，结束条件是左边界大于右边界）
以下为具体代码：
#include <bits/stdc++.h>
using namespace std;
void quick_sort(int q[],int l,int r)
{
if(l>=r) return; //此处一定要将等于号加上，不然会形成死循环;
int x=q[(l+r)/2],i=i-1,j=r+1; //X取中间的数有利于提高速度，但不追求速度的情况下，用其中数列中任意一个数来进行快排都是可以的;
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;
int a[100005];
cin>>n;
for(int i=1;i<=n;i++)
{
scanf(“%d”,&a[i]); //用scanf而不是cin是由于scanf比cin要快，由于快排的题目多涉及大数字，容易超时，因此用scanf更为保险，但cin也可以用;
}
quick_sort(a,1,n);
for(int i=1;i<=n;i++)
{
printf(“%d “,a[i]);
}
}