#算法3 快速排序

上期回顾

上一次我们学了质数筛中的欧拉筛，它的核心思路是先默认所有数都是质数，然后找到一个数n后，如果n是第i个质数，就把质数表的第i项赋值为这个质数，接下来不论是质数还是合数都乘上质数表中的质数，直到质数表中的数是n的因数。至此质数筛的学习就告一段落了，今天我们学习快速排序。

算法思路

快速排序的实现需要两个哨兵i和j，以及一个基准数。基准数有三种分别是两端的其中一个数，中间值和随机值。哨兵i和j分别从两端向中间遍历数，直到i找到第一个比基准值大的数，j找到第一个比基准值小的数，将它们调换后再继续，直到相遇，而相遇的位置就是基准值的位置，将基准值与相遇的值进行调换。此时整个数组也被分为了两部分，再把两部分继续执行以上步骤，直到全部有序。
**提示：**基准数如果采取两端的话有可能会退化！所以我们使用中间值做基准值的方法示范。_{文末有彩蛋哦。}

具体实现

首先，我们先定义三个变量i，j和基准数，$l$表示起始的下标，$r$表示结束的下标。代码↓

int i=l,j=r,jzz=a[(l+r)/2];

接下来我们要执行“哨兵i和j分别从两端向中间遍历数，直到i找到第一个比基准值大的数，j找到第一个比基准值小的数，将它们调换后再继续，直到相遇”的部分。“再继续，直到相遇”部分可以用while(i<=j){}表示，中间“哨兵i和j分别从两端向中间遍历数”也是while循环，但此时，i和j是分开的，所以就分成两段。
i：

while(a[i] < jzz){
	i++;
}

j:

while(a[j] > jzz){//找到第一个比基准值小的数 
	j--;
}

此时i和j都找到了各自要找的数，进行一次交换。

if(i<=j){//交换 
	swap(a[i],a[j]);
	i++;
	j--;
}

随后又会进入外面的循环，继续遍历，最终还会又一次交换。
最后，我们要将以上步骤再重复一遍，不需要复制粘贴，用递归的方法，但别忘了在开头加上一个if语句。

if(l >= r){//全部归位后退出 
	return;
}

开头的if语句↑
结尾的递归↓

if(l < j) kspx(l,j);
if(i < r) kspx(i,r);

此时，再把最后的函数封装完成

void kspx(int l,int r){
    //此处省略一大堆代码
}

函数名k(kuai快)s(su速)p(pai排)x(xu序)是不是很好记呢？

完整代码

请勿抄袭！

int a[100000000];
void kspx(int l,int r){//快速排序
	if(l >= r){//全部归位后退出 
		return;
	}
	
	int i=l,j=r,jzz=a[(l+r)/2];
	//哨兵1，哨兵2，基准值（中间值）
	while(i<=j){
		while(a[i] < jzz){//找到第一个比基准值大的数 
			i++;
		}
		while(a[j] > jzz){//找到第一个比基准值小的数 
			j--;
		}
		if(i<=j){//交换 
			swap(a[i],a[j]);
			i++;
			j--;
		}
	}
	 
	if(l < j) kspx(l,j);
	if(i < r) kspx(i,r);
	//递归 
}

彩蛋：用最左侧做基准值：

void qSort(int left,int right){
	//
	
	if(left>=right) return ;
	
	int i=left,j=right,tmp; 
	tmp=a[left];
	
	while(i!=j){
		//1. 从右向左 寻找比基准值小
//		while(a[j]>=tmp){j--;
//		} 
		while(a[j]>=tmp){j--;}
		//2. 从左往右，寻找比基准值大的数
		while(a[i]<=tmp){i++;}
		
		if(i<j)
			swap(a[i],a[j]);
		
	}
	//使基准值归位 
	a[left]=a[i];
	a[i]=tmp;
	// 递归排序两侧
	//
	qSort(left,i-1);
	
	qSort(i+1,right); 
}