快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分，然后分别对这两个部分再排序。
双边排序法
先选定基准元素pivot，然后设置两个指针left和right，指向数列的最左和最右两个元素,目标是把比pivot小的放到左边，把比pivot大的放到右边
第一次循环
从right指针开始，让指针所指向的元素和基准元素做比较。如果大于或等于pivot，则指针向左移动，如果小于pivot，则right指针停止移动，切换到left指针
轮到left指针行动，让指针所指向的元素和基准元素做比较。如果小于或等于pivot，则指针向右移动，如果大于pivot，则left指针停止移动
此时left指向了一个大于pivot的元素，right指向了一个小于pivot的元素
将左右指针指向的元素交换位置
第二次循环
重新回到right指针，right指针先向左移动，移动到8的时候，8>pivot的4，继续左移，移动到2的时候，2<pivot的4切换到left指针，left指针在6的位置停下来
交换左右指针的元素
第三次循环
交换5和3
第四次循环
left指针和right指针在元素3相遇
将基准元素4和3交换
此时4左边的都是比4小的，右边的都是比4大的，然后再分别对基准元素4左边和4右边的进行排序
代码实现
public class QuickSort1 {
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);
}
/**
* 分治(双边循环法)
*
* @param arr 待交换的数组
* @param startIndex 起始下标 * @param endIndex 结束下标
*/
private static int partition(int[] arr, int startIndex, int endIndex) { // 取第1个位置(也可以选择随机位置)的元素作为基准元素
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while (left != right) {
//控制right 指针比较并左移
while (left < right && arr[right] > pivot) {
right--;
}
//控制left指针比较并右移
while (left < right && arr[left] <= pivot) {
left++;
}
//交换left和right 指针所指向的元素
if (left < right) {
int p = arr[left];
arr[left] = arr[right];
arr[right] = p;
}
}
//pivot 和左右指针重合点交换
arr[startIndex] = arr[left];
arr[left] = pivot;
return left;
}
public static void main(String[] args) {
int[] arr = new int[]{4, 7, 3, 5, 6, 2, 8, 1};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
单边排序法
单边循环法只从数组的一边对元素进行遍历和交换
单边循环法先选定基准元素pivot，再设置一个mark指针指向数列起始位置，遍历结束后这个mark左边的都是小于pivot的元素，mark右边的都是小于pivot的元素
从基准元素的下一个位置开始遍历数组。
如果遍历到的元素大于基准元素，就继续往后遍历，如果遍历到的元素小于基准元素，把mark指针右移1位，让最新遍历到的元素和mark指针所在位置的元素交换位置，表示找到了一个小于pivot的元素
第一次遍历到7，7大于4，继续遍历
然后遍历到3，3小于4，mark右移一位到7
让元素3和mark指针所在位置的元素交换
继续遍历，一直遍历到2，2<4
mark右移，然后把7和2交换位置
继续遍历，最后把1和5交换位置
最后把mark所在的位置的元素和pivot的元素交换位置
这样mark左边都是小于mark的元素，右边的都是大于mark的元素，然后递归分别对mark左边的和mark右边的排序
代码实现
public class QuickSort2 {
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);
}
/**
* 分治(单边循环法) *
*
* @param arr 待交换的数组
* @param startIndex 起始下标
* @param endIndex 结束下标 * @return
*/
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;
}
}
//mark元素和pivot元素交换
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
}
public static void main(String[] args) {
int[] arr = new int[]{4, 7, 3, 5, 6, 2, 8, 1};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}