快速排序之单边循环法
递归的精髓在于放弃！放弃你对于理解和跟踪递归全程的企图，只理解递归两层之间的交接，以及递归终结的条件。
快速排序和冒泡排序一样,也属于交换排序.和冒泡排序不同的是,快速排序在每一轮选中1个基准元素,并让其它比它大的元素移动到一边,比它小的移动到另一边,从而把数列拆解成两个部分.这种思路叫作分治法.
通过以上描述,快速排序实现分成2步:
1. 获取基准元素
2. 元素的交换
基准元素的选择
毫无疑问,最简单的方式就是选择数列的第1个元素作为基准元素.
元素的交换
元素的交换实现有两种方式:单边循环法和双边循环法.先记录单边循环法的思路.
举个例子,将一下数组,从小到大进行升序排序:
4, 7, 3, 5, 6, 2, 8, 1
一. 首先获取基准元素standardValue,同时设置一个mark指针指向数列起始位置,mark指针表示小于基准元素的区域边界.用以上数组来说:
standardValue=4, mark=0
二. 然后,从基准元素的下一位(即7)开始遍历数组:
如果遍历到的元素大于基准元素,继续遍历;
如果遍历到的元素小于基准元素,需要完成:
1.将mark指针右移1位,因为小于基准元素的区域边界增大了1;
2.将最新遍历到的元素和mark指针指向的元素进行交换,因为最新遍历的元素属于小于基准元素standardValue的区域.
4, 3, 2, 1, 6, 7, 8, 5
三. 最后,将基准元素和指针指向的元素交换,这一轮宣告结束,将看到的数组是这样:
1, 3, 2, 4, 6, 7, 8, 5
实现了将数组中比基准元素4小的元素移动到了左边, 比基准元素4大的元素移动到了右边, 分成左右两个部分, 然后对左右两个部分继续一 二 三的步骤,也就是递归.
单边循环法的实现
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) {
// 取第一位元素作为基准元素
int standardValue = arr[startIndex];
// 指针指向数列的起始位置,mark代表小于基准元素的区域边界
int mark = startIndex;
// 遍历数组,如果遍历到的元素小于基准元素: 1. 2.
for (int i = startIndex + 1; i <= endIndex; i++) {
if (arr[i] < standardValue) {
// 1.指针右移一位
mark++;
// 2.并将当前遍历到的元素和指针所指元素交换
int temp = arr[i];
arr[i] = arr[mark];
arr[mark] = temp;
}
}
// 遍历结束,将基准元素和指针指向的元素交换,这一轮宣告结束
arr[startIndex] = arr[mark];
arr[mark] = standardValue;
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));
}
}
下集预告
下篇记录一下快速排序的双边循环法.
习惯沉淀
一线码农的学习见闻与思考
Official Account