快速排序之双边循环法
双边循环法思路
思路概述:
1. 选定基准元素standardValue,同时设置左右两个指针left和right分别指向数组的最左和最右两个元素.
2. 从右指针开始,将指针指向的元素与基准元素进行比较:
如果大于等于基准元素,则指针向左移动一位
如果小于基准元素,则停止移动
3. 轮到左指针操作,将指针指向的元素与基准元素进行比较:
如果小于等于基准元素,则指针向右移动一位
如果大于基准元素,则停止移动
4. 当左右指针都停止移动时,将左右指针指向的元素进行交换
如此重复2.3. ...
5.当左右指针重合时,将重合点的元素和基准元素交换,这一轮宣告结束
递归,重复1.2.3.4.5. ...
双边循环法实现
双边循环法递归部分quickSort()的实现和单边循环部分代码一样,不同的是partition(),如下:
package com.xgcd.lab.sort;
import java.util.Arrays;
/**
* @description: 快速排序
* @author: liangyadong
* @date: 2021/6/29 23:24
*/
public class QuickSort {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 递归结束条件
if (startIndex >= endIndex) {
return;
}
// 1.得到基准元素位置
int standardIndex = partition(arr, startIndex, endIndex);
// 2.根据基准元素,分成两个部分进行递归排序
quickSort(arr, startIndex, standardIndex - 1);
quickSort(arr, startIndex + 1, endIndex);
}
/**
* 分治(双边循环法)
*
* @param arr 待交换的数组
* @param startIndex 起始下标
* @param endIndex 结束下标
* @return 基准元素的位置
*/
private static int partition(int[] arr, int startIndex, int endIndex) {
// 基准元素 standardValue
int standardValue = arr[startIndex];
// 左指针 left
int left = startIndex;
// 右指针 right
int right = endIndex;
while (left < right) {
// 右指针的操作
for (int i = endIndex; i > startIndex; i--) {
// 从右指针开始,如果指针指向的元素大于等于基准元素则指针向左移动一位继续遍历,如果小于基准元素则停止移动切换到左指针
if (standardValue <= arr[right]) {
right--;
} else {
break;
}
}
// 左指针的操作
for (int j = startIndex; j < endIndex; j++) {
// 轮到左指针,如果指针指向的元素小于等于基准元素则指针向右移动一位继续遍历,如果大于基准元素则停止移动
if (standardValue >= arr[left]) {
left++;
} else {
break;
}
}
// 将左指针和右指针指向的元素交换
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
}
// 当左指针和右指针重合的时候,将基准元素和指针重合的元素交换,这一轮宣告结束
int temp = arr[startIndex];
arr[startIndex] = arr[left];
arr[left] = temp;
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));
}
}
简洁版
上面的partition()比较啰嗦...简洁版如下(只关注partition方法即可):
package com.xgcd.lab.sort;
import java.util.Arrays;
/**
* @description: 快速排序
* @author: liangyadong
* @date: 2021/7/1 0001 12:22
**/
public class QuickSort {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 递归结束条件
if (startIndex >= endIndex) {
return;
}
// 1.得到基准元素位置
int standardIndex = partition(arr, startIndex, endIndex);
// 2.根据基准元素,分成两个部分进行递归排序
quickSort(arr, startIndex, standardIndex - 1);
quickSort(arr, startIndex + 1, endIndex);
}
public static int partition(int[] arr, int startIndex, int endIndex) {
// 基准元素
int pivot = arr[startIndex];
// 左指针
int left = startIndex;
// 右指针
int right = endIndex;
while (left != right) {
// 右指针操作
while (left < right && arr[right] >= pivot) {
right--;
}
// 左指针操作
while (left < right && arr[left] <= pivot) {
left++;
}
// 交换左右指针指向的元素
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
// 交换基准元素和重合点元素
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));
}
}
下集预告
xxxx...
习惯沉淀
一线码农的学习见闻与思考
Official Account