快速排序

时间复杂度：由于每一次扫描交换都是跳跃性的，所以平均复杂度：O(nlogn);最坏时间复杂度：O(n²)

算法思路描述
——————————————————————————————————————————

算法思路描述
首先在序列中随便找一个数作为基准数，一般会取序列的第一个数作为基准数，然后分别从序列的两端进行探测，从右往左（j–）找小于基准数的元素，找到之后停止，然后从左往右(i++)找大于基准数的元素，找到之后停止，将找到的i与j对应的两元素交换位置，然后继续探测，切记每次探测都是右侧先找（因为基准数是最左边的数）。
当i与j碰面时，元素已分好类，左侧均为小于基准数的元素，右侧均为大于基准数的元素，此时交换基准数与i或j对应的元素。
此时基准数的两侧可以看作原序列的子序列，所以递归函数即可，左侧为数组起始下标——i-1,右侧为i+1——数组长度。
排列完成！

——————————————————————————————————————————

#include<stdio.h>

int a[100],n;//全局变量

//排序函数
quickSort(int left,int right)
{
    
	int i,j,temp;//设置哨兵 i，j ,临时变量temp,存储基准数
	if(left>right)
	{
    
		return 0;
	}//递归结束
	temp = a[left];//存储基准数
	i = left;
	j=right;
	while(i!=j)
	{
    
		while(a[j]>=temp&&i<j)//先走右侧 很重要
		{
    
			j--;//往左侧移动
		}//找到比temp小的值停下

		while(a[i]<=temp&&i<j)
		{
    
			i++;//
		}//找到比temp大的值停下
		if(i<j)
		{
    
			int t=a[i];
			a[i]=a[j];
			a[j]=t;
		}
	}
	//i与j扫描完毕，即当前数组被扫描一遍，则将基准数归位
	a[left]=a[i];//此处用i或者用 j 都行，因为i==j
	a[i]=temp;
// 递归执行上述操作，可以优先找左侧或者右侧都行，个人理解（未测试，可以交换一下下述函数位置自行测试） 
	quickSort(left,i-1);//左侧部分
	quickSort(i+1,right);//右侧部分 
	return 0;//排序完毕 

}

int main()
{
    
// int i,j;
	scanf("%d",&n);
	for(int i=0; i<n; i++)
	{
    
		scanf("%d",&a[i]);
	}

	quickSort(0,n-1);

	for(int i=0; i<n; i++)
	{
    
		printf("%d ",a[i]);
	}

	return 0;
}

下为数组传址排序，不用定义全局数组。

#include<stdio.h>

void quickSort(int *a,int left,int right)
{
    
	int i=left,j=right,temp;

	if(left>right)
	{
    
	  return;	
	}
	temp=a[left];//设置基准点
	while(i!=j)
	{
    
		while(a[j]>=temp&&i<j)//注意要有i<j的判定条件
		{
    
			j--;
		}
		while(a[i]<=temp&i<j)//注意要有i<j的条件
		{
    
			i++;
		}
		if(i<j)
		{
    
			int s=a[i];
			a[i]=a[j];
			a[j]=s;
		}
	}
	a[left]=a[i];
	a[i]=temp;
	quickSort(a,left,i-1);
	quickSort(a,i+1,right);
	return;
}
int main()
{
    
	int a[101],n;
	scanf("%d",&n);
	for(int i = 0; i<n; i++)
	{
    
		scanf("%d",&a[i]);
	}
	quickSort(a,0,n-1);
	for(int i = 0;i<n;i++)
	{
    
		printf("%d ",a[i]);
	}
	return 0;
}