七大排序算法之快速排序
@(算法笔记)[排序算法, 快速排序, C++实现]
[TOC]
快速排序的介绍：
快速排序是C. A. R. Hoare在1962年提出的，平均时间复杂度为O(nlogn)级的高效率算法，也是目前O(nlogn)的排序算法中使用最多的算法，这段时间想把自己学过的算法都整理一遍，于是就写了这篇博客，来记录自己的学习过程吧...也希望能给初学者带来一些帮助。
快速排序的核心思想
每次排序都需要以序列的第一个值为关键值，将序列分成两个部分，并且使其中一部分的值都大于关键值，而另一部分的值都小于关键值，然后再分别对两个部分都再次进行本操作，直至某次操作的部分只有一个值。整个排序过程可以通过递归的方式进行，使整个序列变成有序序列。
简单例子
初学者们可能无法看懂上面的描述，不过没关系，让我们来举个栗子:
待排序序列： 5 3 7 6 9 1 2
第一轮排序： 2 3 1 5 9 6 7
第二轮排序： 1 2 3 5 7 6 9
第三轮排序： 1 2 3 5 6 7 9
第四轮排序： 1 2 3 5 6 7 9
第一轮快速排序，把上面这个序列分成了两个部分，然后5作为关键值在中间
第二轮快速排序，分别再对之前的两个序列再进行操作，2和9分别是关键值
第三轮中，只有一个值的序列不再进行操作，现在灰色区域的序列
第四轮中，每个部分都只有一个值了，排序结束
由此可见，快速排序要做的事，就是用二分的思想，每次都将待处理的序列分成两个部分，并且保证其中一个序列的值都大于另一个序列的值，显然，将本操作执行完之后，序列自然就都是有序的了，那剩下的问题只有，每轮的操作该如何实现了。
每轮快排的具体实现
每轮操作该如何执行？ 我们要做到以O(n)的时间复杂度，做到让序列分成两个部分，该如何实现呢？
其实这个实现起来并不困难，举个栗子：
初始序列：
5 3 7 6 9 1 2
我们选中第一个数字5作为关键值，然后先从后往前找比关键值小的数
5 3 7 6 9 1 2
此时我们找到了数字2，它比关键数5要大，于是我们让它和关键数交换
2 3 7 6 9 1 5
关键数到了后面，我们锁定5，转换方向，再从前面开始找比5大的数
2 3 7 6 9 1 5
此时我们找到了数字7，交换
2 3 5 6 9 1 7
之后再转换方向，从上一次找到的位置从后往前找比关键值小的数1，交换
2 3 1 6 9 5 7
与1交换，再从1往后找比5大的数，找到了6，交换
2 3 1 5 9 6 7
5之后，6之前已经没有比关键字大的数了，结束
这样子一轮操作就结束了，我们也确实在O(n)的时间复杂度内，实现将数组分成两个序列了，看着这个栗子是不是有点天昏地转的感觉？哈哈，没事的，习惯就好了。
用语言来描述每轮的操作就是：锁定一个数为关键数，然后先从尾部往前找比第一个比关键数小的数，找到了交换并交换方向，没找到就结束本轮操作。换方向后，从刚刚交换的位置再往后/前找，找到第一个比关键数大/小的数，交换，直到没找到符合条件的数为止，本轮操作结束。
时间复杂度的讨论
上面的介绍中已经提到了，快速排序算法的时间复杂度是O(nlogn)，现在我们来简单地分析一下：
可见，虽然每轮操作中，待处理的序列段会逐渐变多，但需要处理的数字的数量是不会增加的，所以只要让操作的时间复杂度都是O(n) 就行了（此处的n是每段待处理的序列中数值的数量），这样就能保证每轮的时间复杂度都是O(n)。
接着再来讨论算法需要执行几轮：在数列足够乱序的情况下，我们假设每个部分操作完了之后，都会产生左右两个序列，即构造成一个满二叉树，在这个前提下，我们执行n轮，就能解决2的n次方个数的排序。所以只需进行logn次操作就能得到答案。当然，这个前提有点苛刻。但在平均情况（随机序列）下，执行的轮数的数量级都是logn，所以，我们说快速排序的平均时间复杂度是O(nlogn)。
有最好的情况，肯定也有最坏的情况，对快速排序来说，最坏的情况就是待排序的数组本身有序（顺序逆序都是），每次操作的时候，都会出现所有的数都在关键值的同一边的尴尬的情况，使得这个二叉树成了一个单向链表，那么操作的轮数就是n轮了，在这种极端的情况下，快速排序的时间复杂度就是O(n^2)了。
代码
#include<cstdio>
#include<iostream>
using namespace std;
int a[100005];
void swap(int n,int m)
{
int temp=a[n];
a[n]=a[m];
a[m]=temp;
}
int partition(int p,int q)
{
int n=q,s=1;//n为临时变量，s为记录方向的变量
while(p!=q)//只要p和q两变量不相等，就代表没找完
{
if( s && a[n]<a[p]) //s判断方向
{
s=!s;//找到了，改变方向
swap(n,p);//交换
n=++p;
}
else if( s && a[n]>=a[p])//小于的话移一位
{
n=--q;
}
else if( !s && a[n]>a[q])//与上面同理
{
s=!s;
swap(n,q);
n=--q;
}
else if( !s && a[n]<=a[q])
{
n=++p;
}
}
return n;
}
void qsort(int p,int q)
{
int j=partition(p,q);//进行划分操作
//两个部分再次进入递归
if(p!=j) qsort(p,j-1);
if(q!=j) qsort(j+1,q);
}
int main()
{
int t;
scanf("%d",&t);
int i=0;
for(i=0;i<t;i++)//输入数据
{
scanf("%d",&a[i]);
}
qsort(0,t-1);//进行快速排序
for(i=0;i<t;i++)//输出数据
{
printf("%d ",a[i]);
}
return 0;
}
