浅谈快速排序（假设处理数组）

引言

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用
因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。
但大多数快速排序枢纽点的选择都会选择第一个元素，对于一些喜欢探索的学者来说他们都喜欢变换一下这个枢纽点的选择，
接下来我就我自己的观点分享一下我的观点。这边如果对快速排序有些遗忘的同学，我建议大家可以看一下这个链接https://www.runoob.com/w3cnote/quick-sort.html的内容回顾一下。

正文

首先我想先说明一下我的观点：
对于那些喜欢用第一个元素的作为枢纽的原因大部分是因为可以写成可以实际运行且正确的代码，巧妙的利用分治法，面对处理的数组长度逐渐减少时不会产生因枢纽点选择而造成错误。对于任意选择枢纽点进行快速排序也是可行的，但很难用代码很流畅的写出处理快速排序的全过程，只能分开的确定每次分治时要选择的一个一个去处理。比如当你选择第5个元素作为枢纽点对于那些数组小于5的数组来说就不太合适。

实现

下面给出任意枢纽点的一次排序代码：param 为枢纽点的位置 其余的与一般的快速排序相似。

   public static int s(int[] a,int low,int high,int param) {		
	int rr=param+low;//获取的指定区间枢纽点选择的位置
	int p=low,q=high,r=a[rr];//存储枢纽点的值		
	while(p<q) {
		while(p<q&&a[q]>=r) --q;
		if(p<q) {
		a[rr]=a[q];
		rr=q;//通过rr参数动态的指向下一次移动到的位置
		}
		while(p<q&&a[p]<=r) ++p;
		if(p<q) {
		a[rr]=a[p];
		rr=p;
		}
	}
	a[rr]=r;
	return rr;
	
}