当前位置:   article > 正文

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

快速排序算法java实现

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

快速排序2

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

快速排序3

继续排 0 和 1 :

快速排序4

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

快速排序5

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

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开发全套学习资料》,初衷也很简单,就是希望能够帮助到想自学提升又不知道该从何学起的朋友,同时减轻大家的负担。
img
img
img
img
img
img

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

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

如果你觉得这些内容对你有帮助,可以添加V获取:vip1024b (备注Java)
img

最后总结

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

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

image

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

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

最后总结

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

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

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/花生_TL007/article/detail/630409
推荐阅读
相关标签
  

闽ICP备14008679号