快速排序

1. 今天来复习下几个常用的排序方式，首先想到的就是快速排序，思路用的是分治思想。
   

2. 选取一个标准值，利用两个指针i,j分别只想最左边，最右边，i从左边找到1个比这个标准值大的数，j从右边找到1个比这个值小的数，两者交换，直到i>j

   就找到了这个标准值的位置。

   
   

/*
快速排序,分治思想
给定的N个数从小到达进行排序
3 2 4 5 1
思路：选定第一个元素作为轴，i从左往右找比他大的一个数a[i],j从后往前找比他小的数a[j]
两者交换，知道i>j 

对轴左边继续执行上述操作，右边继续执行上述操作，分而治之 
*/
#include <bits/stdc++.h>
using namespace std;
int a[1000010];
int n;
void mysort(int a[],int l,int r){
	//i记录轴左边位置，j记录轴右边位置 
	int i=l,j=r;
	int pvot=a[(l+r)>>1]; 
	while(i<=j){
		//从左边找比他大的一个数 
		while(a[i]<pvot){
			i++ ;
		}
		//从右边找比他小的一个数 
		while(a[j]>pvot){
			j--;
		}
		if(i<=j){
			swap(a[i],a[j]);//交换 
			i++;
			j--;
		}
	}
	//左右两边分别排序
	if(l<j) mysort(a,l,j);
	if(i<r) mysort(a,i,r);	
}


int main(){

	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}

	int l=0,r=n-1;
	mysort(a,l,r); 
	for(int i=0;i<n;i++){
		printf("%d ",a[i]);
	}
	
	return 0;
}