快速排序算法动图演示及解析2024版（附Java代码实现），献给真心想学Java的打工人_快速排序算法java实现

与其他元素依次比较，大的放右边，小的放左边：

然后我们以同样的方式排左边的数据：

继续排 0 和 1 ：

由于只剩下一个数，所以就不用排了，现在的数组序列是下图这个样子：

右边以同样的操作进行，即可排序完成。

4、快速排序算法Java代码实现

================

1//Java 代码实现

2public class QuickSort implements IArraySort {

3

4 @Override

5 public int[] sort(int[] sourceArray) throws Exception {

6 // 对 arr 进行拷贝，不改变参数内容

7 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

8

9 return quickSort(arr, 0, arr.length - 1);

10 }

11

12 private int[] quickSort(int[] arr, int left, int right) {

13 if (left < right) {

14 int partitionIndex = partition(arr, left, right);

15 quickSort(arr, left, partitionIndex - 1);

16 quickSort(arr, partitionIndex + 1, right);

17 }

18 return arr;

19 }

20

21 private int partition(int[] arr, int left, int right) {

22 // 设定基准值（pivot）

23 int pivot = left;

24 int index = pivot + 1;

25 for (int i = index; i <= right; i++) {

26 if (arr[i] < arr[pivot]) {

27 swap(arr, i, index);

28 index++;

29 }

30 }

31 swap(arr, pivot, index - 1);

32 return index - 1;

33 }

34

35 private void swap(int[] arr, int i, int j) {

36 int temp = arr[i];

37 arr[i] = arr[j];

38 arr[j] = temp;

39 }

40

41}

5、单边扫描

======

快速排序的关键之处在于切分，切分的同时要进行比较和移动，这里介绍一种叫做单边扫描的做法。

我们随意抽取一个数作为基准值，同时设定一个标记 mark 代表左边序列最右侧的下标位置，当然初始为 0 ，接下来遍历数组，如果元素大于基准值，无操作，继续遍历，如果元素小于基准值，则把 mark + 1 ，再将 mark 所在位置的元素和遍历到的元素交换位置，mark 这个位置存储的是比基准值小的数据，当遍历结束后，将基准值与 mark 所在元素交换位置即可。

代码实现：

public static void sort(int[] arr) {

sort(arr， 0， arr.length - 1);

}

private static void sort(int[] arr， int startIndex， int endIndex) {

if (endIndex <= startIndex) {

return;

}

//切分

int pivotIndex = partitionV2(arr， startIndex， endIndex);

sort(arr， startIndex， pivotIndex-1);

sort(arr， pivotIndex+1， endIndex);

}

private static int partition(int[] arr， int startIndex， int endIndex) {

int pivot = arr[startIndex];//取基准值

int mark = startIndex;//Mark初始化为起始下标

for(int i=startIndex+1; i<=endIndex; i++){

if(arr[i]<pivot){

//小于基准值 则mark+1，并交换位置。

mark ++;

int p = arr[mark];

arr[mark] = arr[i];

arr[i] = p;

}

}

//基准值与mark对应元素调换位置

arr[startIndex] = arr[mark];

arr[mark] = pivot;

return mark;

}

6、双边扫描

======

另外还有一种双边扫描的做法，看起来比较直观：我们随意抽取一个数作为基准值，然后从数组左右两边进行扫描，先从左往右找到一个大于基准值的元素，将下标指针记录下来，然后转到从右往左扫描，找到一个小于基准值的元素，交换这两个元素的位置，重复步骤，直到左右两个指针相遇，再将基准值与左侧最右边的元素交换。

我们来看一下实现代码，不同之处只有 partition 方法：

public static void sort(int[] arr) {

sort(arr， 0， arr.length - 1);

}

private static void sort(int[] arr， int startIndex， int endIndex) {

if (endIndex <= startIndex) {

return;

}

//切分

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024b （备注Java）

最后总结

搞定算法，面试字节再不怕，有需要文章中分享的这些二叉树、链表、字符串、栈和队列等等各大面试高频知识点及解析

最后再分享一份终极手撕架构的大礼包(学习笔记)：分布式+微服务+开源框架+性能优化

实战项目、讲解视频，并且后续会持续更新**

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024b （备注Java）
[外链图片转存中…(img-v7QQAuON-1712028348852)]

最后总结

搞定算法，面试字节再不怕，有需要文章中分享的这些二叉树、链表、字符串、栈和队列等等各大面试高频知识点及解析

最后再分享一份终极手撕架构的大礼包(学习笔记)：分布式+微服务+开源框架+性能优化

[外链图片转存中…(img-J2TshHnQ-1712028348853)]