快速排序据说是21世纪伟大的发明之一，其思想也应用广泛。
核心
当前版本的快速排序，核心：
- 首先从数组中寻找一个元素，把所有比该元素小的元素放到该元素的左边(从小到大)，所有比当前元素大的元素放到右边。
- 当前元素的下标会变化到某个位置，运用递归，再进行第一步操作。
比如元素：
{6,202,100,301,38,8,1}
第一遍：我们默认从最左边的元素开始寻找那么最终结果：
{1, 6, 100, 301, 38, 8, 202}
过程：
我们每次进行比较之前需定义 两个下标：指向当前要比较的元素,指向小于该元素与大于该元素的分界点
- 因为我们从最左边的元素开始比较，那么所有在该元素右边的位置只要比该元素大即可。
- {6,202,100,301,38,8,1}如果6与元素比较，202，100等比6大，不用调换位置。
- 当碰到比6小的元素，6右边第一个元素与1互换位置，将
指向要交换的位置加1。
{6,1,202,100,301,38,8}
将最左边的元素与刚才指向的元素下标交换位置
{1, 6, 100, 301, 38, 8, 202}返回的下标为1，继续递归，回到第1步。分别比较下标[0,1],[2,6]之间的元素。
图解：
image.png
image.png
如果：(e = arr[i]) > (v = arr[l])，那么，继续向下走
image.png
如果：(e = arr[i]) < (v = arr[l]):
那么把i下标的元素与橙色部分元素的最后一个位置交换位置，橙色区域仍然是小于v的元素
然后j++：
image.png
遍历完成之后：
image.png
最后一步操作：
image.png
代码
依赖：
- Lomhok插件
@Slf4j
public class QuickSort {
public static void main(String[] args) {
//代码不应该写死的，但为了测试，就写出固定的了。
int[] a = {6,202,100,301,38,8,1};
sort(a);
log.info("排序完成数组{} ", a);
}
public static void sort(int[] arr){
sort(arr,0,arr.length - 1);
}
private static void sort(int[] arr, int l, int r) {
if (l >= r){
return;
}
//求下标的过程也被称为Partition，下标左边的元素全部小于arr[p]，下标右边的元素全部大于arr[p]
int p = partition(arr,l,r);
sort(arr,l,p);
sort(arr,p + 1,r);
}
private static int partition(int[] arr, int l, int r) {
int v = arr[l];
int j = l;
//为了查看效果，所以把日志都打印出来了。
log.info("下标{} , {}",l,r);
log.info("排序前数组{} ", arr);
for (int i = l + 1; i <= r; i++) {
if (arr[i] < v){
j++;
Hepler.swap(arr,j,i);
log.info("排序中数组{} ", arr);
}
}
Hepler.swap(arr,l,j);
log.info("排序后数组{} ", arr);
return j;
}
}
最后
这里演示了快速排序第一版的算法思想与流程，重点在于理解过程。
