参考资料
快速排序算法
image.png
@Test
public void test() {
int[] array = new int[]{4, 2, 6, 8, 1, 4, 0, 7};
quickSort(array, 0, array.length - 1);
for (int i : array) {
System.out.print(i + " ");
}
}
private void quickSort(int[] array, int L, int R) {
// 递归回溯语句
if (L >= R) {
return;
}
int left = L;
int right = R;
int pivot = array[left]; // 中心值
while (left < right) {
// 找到右侧比中心值小的数, 为了后面做调换
while (left < right && array[right] >= pivot) {
right--;
}
// 找到一个值 array[right] < pivot
if (left < right) {
array[left] = array[right];
}
// 找到左侧比中心值大的数, 为了后面做调换
while (left < right && array[left] < pivot) {
left++;
}
// 找到一个值 array[left] > pivot
if (left < right) {
array[right] = array[left];
}
}
// left >= right, 如果left, right 交汇了就说明排序已完成, 所有的数字已经调整过
array[left] = pivot;
// 递归排序左边到中心值坐标的数组
quickSort(array, L, right - 1);
// 递归排序中心值坐标到右边的数组
quickSort(array, right + 1, R);
}
