排序-快排

一：快排的简单介绍

快速排序之所以快，是相对于冒泡排序，不再是只有相邻的数之间交换，它是可以跳跃式的交换，交换的距离会变得大的多，所以速度就提高了，当然也会存在最坏的结果，仍然是跟冒泡一样是相邻的两数之间进行了交换，所以它最差的时间复杂度和冒泡排序是一样的，都是O(N²),它的平均复杂度是O(NlogN)。

二：快排的实现逻辑（图解）

画图举例来解释把：

随意列出10个无序的数字，需要用到i，j两个变量，i在这列数的最左边，j在这列数的最右边，在这列数中随意找到一个数设置基准值（这里为了方便将第一个数设置为基准），首先让j向左移动，让i向右移动。

j找到一个比基准值小的数2停下来，然后i向右移动找到比基准值大的数6停下来，然后将i，j所指向的数进行交换。

交换后，j继续向左移动找到比基准值小的数4停下来，然后i向右移动找到比基准值大的数7停下来，然后将i，j所指向的数进行交换。

接下来j继续向左移动找到比基准值小的数3，i向右移动和j碰面，此时i和j在同一个位置上停下来，此时将i和j所指向的数和基准值进行交换，即将3和5进行交换。

即基准值归位后，基准值左边的都是小于基准值5的数，在基准值右边的都是大于基准值5的数。

这里需要提一点的是，为什么每次都需要j先移动，因为当最后i和j相碰时，此时所指向的是j寻找到比基准值小的数字，然后和基准值交换能确保基准值左边的都是小于基准值的数字，但是如果i先右边移动的话，最后i和j相碰时，i和j所指向的是i寻找得比基准值大的数，此时和基准值相交换，基准值左边是有一个比基准值大的数，没有达到我们需要的排序效果。

之后我们将5左边的拉出来再进行排序，此时选的基准值是3，根据原先的流程再来一遍。

这就是快速排序的逻辑。

最后总结下快排的步骤和注意点：

1.选取基准点
2.永远是j先向左移动，i再向右移动
3.当i，j碰面时候，将i和j所指向的数和基准值交换
4.然后处理左半边和右半边（递归）

三：代码实现快排（递归）

代码实现：

#include<stdio.h>
int n,i,j,a[100];  //定义全局变量 

void quicksort(int left, int right)   
{
	int temp,t;   //temp变量是基准，t变量是用来交换的第三变量 
	if(left > right)   //跳出循环的第一个条件 
	{
		return;
	}
	
	temp = a[left];   //此时选用的是第一个数当做基准 
	i = left;     //i是1 
	j = right;     //j是n 
	while(i != j)     //当i,j没有走到一块的时候 
	{
		while(a[j] >= temp && i<j)   //j一步一步左移，查找比基准值小的数 
		{
			j--;
		}
		while(a[i] <= temp && i<j)   //i一步一步右移，查找比基准值大的数 
		{
			i++;
		}
		if(i < j)
		{
			t = a[i];    //将j查到的比基准值的数与i查到的比基准值小的数交换 
			a[i] = a[j];  //即将小的数放在基准值左边 
			a[j] = t;      //将大的数放在基准值右边 
		}
	}
	  //将基准值归位 
	a[left] = a[i];    //当循环结束时，i=j，在中间某一位置 
	a[i] = temp;      //将那一位置的数与基准值交换 
	
	//递归 ，将基准值左边分为一部分
   //将基准值右边分为一部分 
	quicksort(left,i-1);     //继续处理左半部分的数    
	quicksort(i+1,right);   //继续处理右半部分的数 
	return ;
}

int main()  //主函数 
{
	scanf("%d",&n);  //用来限制输入的个数 
	for(i=1; i<=n; i++)
	{
		scanf("%d",&a[i]); //读入数据 
	}
	quicksort(1,n);  //调用快排函数 
	for(i=1; i<=n; i++) 
	{
		printf("%d\t",a[i]);  //循环输出 
	}
}