一：概述
双边循环法从数组的两边交替遍历元素，虽然更加直观，但是代码实现比较繁琐。而单边循环法则简单许多，只从数组的一边对元素进行遍历合交换。
二：具体说明
给定的原始数组如下图所示：
开始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向起始的位置，这个mark指针代表小于基准元素的区域边界.
接下来，从基准元素的下一个位置开始遍历数组。
如果遍历到的元素大于基准元素，就继续往后遍历。
如果遍历到的元素小于基准元素，则需要做两件事：第一，把mark指针右移1位，因为小于pivot的区域边界增大了1；第二，让最新遍历到的元素和mark指针所在的位置的元素交换位置，因为最新的元素归属小于pivot区域。
首先遍历到元素7，7>4，所以继续遍历。
接下来遍历得到的元素是3，3<4，所以mark指针右移1位。
随后，让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域。
按照这个思路，继续遍历，后续的步骤如下图所示：
双边循环法和单边循环法的区别在于partition函数的实现。
单边循环法的代码如下图所示：
// 快速排序之单边循环法
public class Sort5 {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 递归结束条件：startIndex 大于或等于endIndex时
if (startIndex >= endIndex) {
return;
}
// 得到基准元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根据基准元素，分成两个部分进行递归排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第1个位置(也可以选择随机位置)的元素为基准元素
int pivot = arr[startIndex];
int mark = startIndex;
for (int i = startIndex + 1; i < endIndex; i++) {
if (arr[i] < pivot) {
mark ++;
int p = arr[mark];
arr[mark] = arr[i];
arr[i] = p;
}
}
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
}
public static void main(String[] args) {
// 创建一个数组
int[] arr = new int[] {4, 5, 6, 5, 3, 2, 8, 1};
quickSort(arr,0,arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
可以从上述的代码中看出，partition方法只需要一个大循环就搞定了，的确比双边循环法简单。
无论是单边循环法还是双边循环法，它们都是基于递归的方式去实现的。