快速排序算法

时间复杂度 : O(nlogn)

原理：对于一个序列A[1]、A[2]、........A[n],调整序列中元素的位置，使得A[1]的左侧的所有元素不超过A[1]、右侧的所有元素都大于A[1].以此原理进行递归，直到序列中所有的元素有序

#include<bits/stdc++.h>
using namespace std;
int Partition(int A[],int left,int right)
{
	int temp=A[left];// 将最左边的元素存到某个临时变量里面 ,那么此时这个元素所在的位置相当于空出来了 
	while(left<right)
	{
		while(left<right&&A[right]>temp)//找打一个元素使之小于等于temp 
		right--;//改变条件
		A[left]=A[right];//将A[right]挪到A[left] 
		while(left<right&&A[left]<=temp)//找到一个元素使之大于temp 
		left++;//改变条件 
		A[right]=A[left];//将A[left]挪到A[right] 
	}
	A[left]=temp;
	return left;
}


void quickSort(int A[],int left,int right)//快速排序算法的理解 
{
	if(left<right) 
	{
		int pos=Partition(A,left,right);
		quickSort(A,left,pos-1);
		quickSort(A,pos+1,right);
	}
}
int main()
{
    int A[10]={2,3,69,54,25,69,48,25,34,97};
    quickSort(A,0,9);
    for(int i=0;i<10;i++)
    {
    	printf("%d ",A[i]);
    }
}

但当序列中的元素接近有序时，时间复杂度就会达到最坏的O(n^2),因此不能总是用最左边的元素作为主元，要在[left,right]区间里面随机选取作为主元的元素

#include<bits/stdc++.h>
using namespace std;
int randPartition(int A[],int left,int right)
{
	//生成区间里的随机数 
	int p=round((rand()/RAND_MAX*(right-left)+left));
	swap(A[p],A[left]);
	
	int temp=A[left];
	while(left<right)
	{
		while(left<right&&A[right]>temp)
		     right--;
	    A[left]=A[right];
	    while(left<right&&A[left]<=temp)
	         left++;
	    A[right]=A[left];
	} 
	A[left]=temp;
	return left;
} 

   void quickSort(int A[],int left,int right)
   {
   	    if(left<right)
   	    {
   	    	int pos=randPartition(A,left,right);
   	    	quickSort(A,0,pos-1);
   	    	quickSort(A,pos+1,right);
   	    }
   }
   
   int main()
   {
   	srand((unsigned)time(NULL));
   	int A[10]={25,36,98,100,2,36,699,255,456,999};
   	quickSort(A,0,9);
   	for(int i=0;i<10;i++)
   	{
   		printf("%d ",A[i]);
   	}
   	return 0;
   }