八大排序算法之六：快速排序（以中轴值作为排序基准）

算法思想

快速排序是对冒泡排序的一种改进：

通过一趟排序，将要排序的数据分割成独立的2部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法
对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以达到整个数据变成有序序列。

快排（以中轴数作为基准）的实现：

1. 对序列进行处理的操作，

   • 目的是：依据选择的基准（这里采用的是中轴值pivot），将序列切分称为两个子序列（因为是依照值进行切分的，所以两个子序列大小不一定相等）
   • 具体的实现方式：
     ① 定义两个指针l、r，其中，l的初值为left，r的初值为right ；
     ② 确定此次划分的中轴值pivot = arr[（left +right）/2] ；
     ③ 当l < r的时候进行while循环，来进行对序列的按值划分:
     <1>对l指针，从左向右遍历，直至遇到一个数，使得arr[l]<pivot不成立；
     <2>对r指针，从右向左遍历，直至遇到一个数，使得arr[r]<pivot不成立；
     此时，如果l < r，就交换l、r对应的元素的值；否则，退出交换的循环【 如果l == r，表明：此时l(也是r)指针的左右两侧的子序列已经满足：左侧的子序列中的值，都小于等于pivot；右侧子序列中的值，都大于等于pivot。】
     == >直到退出进行元素交换的循环，完成了：基于中轴值pivot的，将一个序列按照元素值，划分为两个子序列的操作。
     ----在这个过程中，需要注意的是：
     如果在某一次交换l、r对应的元素值之后，发现arr[l] == pivot，也就是进行交换之前arr[r] == pivot，应该将r指针向前移动一位；同理，如果在某一次交换l、r对应的元素值之后，发现arr[r] == pivot，也就是进行交换之前arr[l] == pivot，应该将l指针向后移动一位；
     =>这是因为，交换之前该位的值 == pivot，（那么跟它进行数据交换的位的值就 == pivot）.为防止特殊情况（交换之后该位的值仍==pivot），出现死循环，应该将对应的指针，沿着遍历的方向移动一位。
     =>这一点比较难理解，但是一定要注意，不然的话，在运行过程中，很可能会出现死循环（当发生两个等于pivot的值互换的时候）！！！！！！

2. 在对序列的处理完成后，就开始进入递归模块。 在这里需要注意的是：因为退出前边的处理模块的外层while循环，对应两种情况： 1）l>r 2）l==r

   • 但是，进行递归操作，必须保证：向左递归 和 向右递归到的时候，他们的递归边界不能重合（否则容易发生栈溢出）
   • 这是因为l==r退出前边的处理模块的外层while循环时，在进行递归之前，需要让l和r两个指针的位置错开。
     —如果这么看不好理解的话，可以看代码实现，可能会比较好理解！！！

算法实现

// 实现快速排序的方法
	public static void quickSort(int[] arr, int left, int right) {

		int l = left;
		int r = right;
		int pivot = arr[(left + right) / 2];// 排序的中轴值
		int temp = 0;//用于交换对应元素的临时变量
		//是进行递归前的处理操作
		while(l < r) {
			//从左向右找到第一个大于等于pivot的值
			while(arr[l] < pivot) {
				l += 1;
			}
			//从右向左找到第一个小于等于pivot的值
			while(arr[r] > pivot) {
				r -= 1;
			}
//			System.out.println("l="+l+",r="+r);
			//判断找到的两个值是否发生交叉或者重叠
			if( l >= r ) {
				break;
			}
			//交换对应的两个元素的值
			temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;
//			System.out.println("l="+l+",r="+r+",arr[l]="+arr[l]+",arr[r]="+arr[r]);
			//判断发生交换的数，是否等于中轴值pivot，避免在下一轮循环时，在两个小的while循环处，形成死循环
			if(arr[l] == pivot) {
				r -= 1;
			}
			if(arr[r] == pivot) {
				l += 1;
			}
//			System.out.println("l="+l+",r="+r);
		}
		
//		System.out.println("排序的pivot值为："+ pivot +""
//				+ ",left="+left+",right="+right
//						+ ",l="+l+",r="+r
//				+ "排序的结果为："+Arrays.toString(arr));
		
		/*
		 * 开始进行递归操作
		 * 分为两个方向：向左递归，向右递归
		 * ----
		 * 但是，在进行递归操作之前，应该对于走出上面的外层while循环的情况进行判断：是满足l==r结束的循环；还是满足l>r结束的循环
		 * =>如果是l==r，标明结束循环的地方，正好是元素值==pivot的地方。
		 * 在下一轮的递归中，不应该取本次的中轴值pivot作为序列的边界上的值。
		 * 应该将l、r两个指针，与pivot的下标值错开：
		 * l += 1;r -= 1;
		 * =>如果是l>r，则可以直接进行递归调用，进入下一轮的递归操作中去
		 */
		if(l==r) {
			l += 1;
			r -= 1;
		}
		//进行递归调用
		//向左递归
		if(left < r) {
			quickSort(arr, left, r);
		}
		//向右递归
		if(l < right) {
			quickSort(arr, l, right);
		}
	}

---

其实，之前总结过：以当前序列的第一个元素作为基准数进行排序的情况，链接如下：
快速排序----以第一个元素作为基准值
遇到难的东西，不要慌，进下心来，一点点理解透彻，是可以解决的!!!