快速排序算法

排序算法有很多种，而快排基本上是比较常用的一种，相比于其他排序，其平均时间复杂度为O（nlogn），其最坏时间复杂度为O(n2）（此处表示n的平方），而最坏时间复杂度主要发生在程序有序且逆序排列的情况下。因此其默认时间复杂度通常认为是其平均时间复杂度。

快速排序算法的思想主要就是选择一个元素，将不大于它的元素放在他的左边（或者右边），将不小于它的元素放在它的右边（左边），此处左右主要取决于要求的排序方式是升序还是降序，以下假设是进行升序排列。
因此，使用一次快速排序以后必定有一个元素满足它左边的元素都不大于它，它右边的元素都不小于它，也就是该元素已经固定了，它的位置就是排好序后该元素所在的位置。
例如：要对7 5 6 8 3 这五个元素进行排序
调用第一次排序，若选中的元素为7，经过一次排序后数组为：
变成3 5 6 7 8。
7的位置就已经是它的最终位置了，也就是对于快速排序，它每次都至少能确定一个元素所在的位置。
同时对于快速排序，实际使用的是递归调用，在确定了第一个元素的位置以后，可以对其左边和右边的元素再分别进行排序。快速排序算法实际就像一个二叉树，不断对选中元素的左右孩子再进行划分。

简单的算法代码如下:

#include
using namespace std;
int quicksort(int a[],int l,int r){
	if(l>=r) return l;
	int t=a[l];
	while(l=t&&l=r) return ;
	int mid =quicksort(a,l,r);
	qsort(a,l,mid);
	qsort(a,mid+1,r);
	
}

int main(){
	int n;
	cin>>n;
	int a[n];
	for (int i=0;i>a[i];
	}
	qsort(a,0,n-1);
	for (int i=0;i 
递归调用过程 
快速排序算法递归调用的过程如上所示（画图有点难用，这个图只能这样吧），但基本递归调用过程就是这样，在这里我们可以明显的看见选中的元素分布的越均匀，我们递归调用的次数也就越少，这里元素较少，相差还不是特别明显。
 因此，在快速排序算法中我们往往希望选中的元素能够尽量将数据平均分成两份，为了达到该目的，我们在选择元素的时候除了选择最左边或最右边的元素，还可以选择从第（l+r）/2个元素来进行比较或者是使用random函数产生一个随机数作为选中元素来进行比较，由于代码差不多，此处就不累述。