题目： 快速排序
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n个整数，表示排好序的数列。
数据范围
1≤n≤100000
题目分析：
本题的要求非常简单，就是实现一个排序算法。我们已知的排序算法有冒泡、插入、选择等，但是这些排序算法中最快的就是快速排序，当然在一些场合下，用其他排序更优于快速排序。下面我们再来介绍。
解法一、sort函数
先上代码！
#include<iostream> #include<algorithm> using namespace std; int main(){ int a=0; cin>>a; int num[100000]={0}; for(int i=0;i<a;i++){ cin>>num[i]; } sort(num,num+a); for(int i=0;i<a-1;i++){ cout<<num[i]<<" "; } cout<<num[a-1]<<endl; }
到这里可能有人会质疑，sort函数是快速排序吗？这里用sort函数是不是不对啊。别急，听我慢慢道来。 由于考虑到部分友友可能不想了解sort函数的内核所以在这里我便放上一篇我之前写过的博客： 里面详细介绍了sort函数的内核。
总之，本题的数据量为100000虽然算是比较大的数据但是由于整体递归的结构不是很复杂，不需要堆排序进行深度优化，所以sort函数仍然会选择快速排序(这里我用断点去尝试过了）。
既然能用sort那么本题就非常简单了！首先是for循环去输入生成数组，然后再把数组的迭代器放到sort中，最后输出整体便结束了，算是偷懒了吧~~嘻嘻
解法二、快速排序
分治法：
现在进入正题，让我们正儿八经的解决这个问题。
首先一个说明：快速排序是依靠递归实现的，其核心思想是分而治之。按照算法导论的大佬说的，分治法都可以按照以下的步骤去实现：
1、分解子问题
2、递归解决子问题
3、归并子问题
由于是递归解决子问题，所以这里必然要涉及递归停止条件。
快排思想：
快排的思想总结起来非常简单：
1、任意找一个序列中的数x，然后将序列中大于x的放在数组右边，小于x的放在数组左边
2、对左边的数组、右边的数组重复上面第一个操作
3、如此递归最后就能实现排序。
总的来说，就是把一个大问题，分解成两个小问题，并且保证两个小问题一旦解决大问题也就解决了。然后这两个小问题又会不停去分解，由于最小的子问题的排序必然已经完成，所以倒着反推，此问题必然也已经完成。（大部分递归的思想都是如此） 
废话不多说，直接上代码！
#include <iostream> using namespace std; const int N = 100010; int q[N]; void quick_sort(int q[], int l, int r) { if (l == r) return;//问题1 int i = l - 1, j = r + 1, x = q[(l+r)>>1];//问题2、3 while (i < j) { do i ++ ; while (q[i] < x);//问题4 do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]);//问题5 } quick_sort(q, l,j);//问题6 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; }
首先说明，scanf输入会比cin快许多，所以为了追求时间效率这里我们都用了scanf来代替cin方法。
问题1
这里解决的是递归停止的条件。当我们不停递归转化为子问题的时候，当l==r或者l>=r时让递归自己停止。所以，这里这两种写法都可以。
问题2
这里的问题是 i = l - 1, j = r + 1这个地方。这里我们先明确一个点：下面需要用do while循环，而不能用while循环（具体原因下面解释）。由于需要用do while循环，所以一定会进入一次循环体，即进行一次i++和j--的操作。这里为了让第一个和最后一个元素（即l和r）也能参与while的判断，所以采用这种写法。
问题3
中间值x的选择与其选取左右两端的数作为划分值，不妨选取数组中间的数字
让我们思考一种情况，如果数组本身就是有序的，这个时候我们的中间值选为左端。那么j就会一直走到开头这个位置（相当于n次），下一次递归时右边那个区间是n-1的长度，又重复之前的操作（相当于n-1次）~~~综上最后的时间复杂度为O（n^2)。当数据量一旦变大后，一旦数据集中存在一种情况它的复杂度是n^2，那么这个情况对整体时间复杂度的影响非常大。
具体例子：假如数据集为10^10个,那么其平方为10^20次运算，对于一般的快排只有接近10^10次。这样前后的差距便非常大，所以n^2对整体的时间复杂度影响非常大。
所以为了保证这种有序数组的情况出现，复杂度仍然为nlogn。我们不选两端作为中间值，而是选择中间的数字。这样子任何测试数据集，我们的运行时间都不会超时。
说明：
只影响时间，不影响正确性。
问题4
这里讨论为什么要用do while循环。while和do while的区别就在于循环会不会至少进入一次，dowhile循环每次开始时都至少执行一次。让我们看一个极端情况（此时中间数也取2）：
3
2 1 2
此时如果是while循环则会出现死循环的情况。因为while (q[i] < x)和while (q[j] > x)判断不成立不会进入，又因为q[i] = q[j] = x，交换它们之后这个局面仍然不会改变。如果我们使用的是do while循环，那么一定会跳转开。原因如下：
一、假设在开始遇到这种情况，那么while循环进入后，执行do则i++，j--成功避开。
二、假设在递归中交换数据后遇到这种情况。由于swap后重新回到上面的while循环，所以下面又重新执行do while，又成功避开。
问题5
为什么又要重新判断一次i和j的关系？虽然在上面的while中我们已经判断过，但是下面的do while循环中i和j又发生变化，并且i>=j时我们不能交换，因为此时说明整体出现问题了。j右边是大于x，i左边是小于x的，若i大于j，则出现矛盾。
也许有人会问了，我们整个程序的运行过程中，一直保证不满足“j右边是大于x，i左边是小于x的”这个条件则交换，且i和j是一一加的，为什么会出现上面的矛盾。这和do while循环必须加1次有关。见下面例子：
3
3 1 2
交换完3和1后形成1 3 2的局面，i ++变成1指向元素3，j --变成0指向元素1，没有做检查指针相对位置的判断，又发生了一次交换，恢复成3 1 2的局面。
问题6
这个问题就是为什么子区间是使用[l, j]而不是[l, i]。这个其实很好理解，让我们在大脑里面模拟一下算法的整个过程：假设i++，j--一直在重复，最终两者靠在一起了（i=j-1），此时是j在循环，那么下一步j就会继续--，这时就会退出while循环，此时j和i是相等，所以上面两个子区间是通用的。但是如果，在i=j-1的时候发生了一次swap交换，那么重新进入while循环时，由于do循环至少执行一次，会出现j=i+1的情况，这时由于i=j-1的时候刚刚交换过所以原本i的位置的数如今存放的是原本j位置的数，而我们知道交换的原因就是因为不满足条件，所以此时原本i的位置的数应该属于右区间，而原本j位置的数属于左区间。并且在ij变化后，j指向的就是原本j的数，而i指向原本i的数。
所以这里写的应该是（l，j）（j+1，r）或者是（l，i-1）（i，r）
