一、前言
1.1、概念
快速排序:用数组的第一个数作为基准数据,然后将所有比它小的数都放到它左边,所有比它大的数都放到它右边,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
1.2、算法过程
- 数组为arr,设置两个变量left、right,排序开始的时候:left=0,right=arr.length-1
- 以第一个数组元素作为关键数据,赋值给key,即key=A[left]
- 从right开始向前搜索,即从后向前搜索(right–),找到第一个小于key的值 arr[right],将 arr[right] 和 arr[left] 的值交换,如果不满足(即3中arr[right]不小于key),则right=right-1
- 从left开始向后搜索,即从前向后搜索(left++),找到第一个大于key的 arr[left],将arr[left] 和 arr[right] 的值交换,如果不满足(即4中arr[left]不大于key),则left=left+1
- 重复第3、4步,直到left==right (3,4步中,找到符合条件的值,进行交换的时候left, right指针位置不变。另外,left==right 时循环结束)
二、maven依赖
pom.xml
<dependencies>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter</artifactId>
<version>2.6.0</version>
</dependency>
<dependency>
<groupId>org.projectlombok</groupId>
<artifactId>lombok</artifactId>
<version>1.16.14</version>
</dependency>
</dependencies>
三、流程解析
假设我们要排序的数据是:19, 28, 8, 23, 10, 21, 9
3.1、全部数据分区
先看看全部数据分区是怎么做的,后续递归过程和这个是一样的。
我们找的基准值是要分区的数组的首个元素:arr[left]=arr[0]=19,你也可以选其他的位置,比如中间,或者尾部,因为我们选的是首部,那么开始遍历的位置就是从右边开始,这个很重要哦。经过我们的分区之后,19左边的元素都比19要小,19右边的数据都比19要大。
3.2、左边数据分区
左边部分分区过程如下:
左边分区的数据都是全部数据分区的基准值19左边的元素,不涉及到19右边的元素,找的基准值是分区的数组的首个元素:9。经过我们的分区之后,9左边的元素都比9要小,9右边的数据都比9要大。
3.3、右边数据分区
右边部分分区过程如下:
右边分区的数据都是全部数据分区后的基准值19右边的元素,不涉及到19左边的元素,同样找的基准值是要分区的数组的首个元素:23。经过我们的分区之后,23左边的元素都比23要小,23右边的数据都比23要大。实际以为我们目前的数据来说,数组已经是有序的了。
四、编码实现
上面我们演示了一个基本的流程,如果数据更多,就继续按照左边和右边继续分区,实际上就是一个递归。我们看看具体的实现就懂了。
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
log.info("开始排从【arr[{}]】到【arr[{}]】数据", left, right);
int pivot = partition(arr, left, right);
log.info("返回的基准位置是:{},分区排序后的结果:{}", pivot, arr);
// 基准元素一定比左边的数大,所以左边分区最大值是:pivot - 1,分区范围是[left, pivot - 1]
quickSort(arr, left, pivot - 1);
// 基准元素一定比右边的数小,所以右边分区最小值是:pivot + 1,分区范围是[pivot + 1, right]
quickSort(arr, pivot + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
// 定义基准元素
int pivotValue = arr[left];
// 遍历(条件就是分区左边索引小于右边索引)
while (left < right) {
// 从右边right开始遍历,找到一个数比基准数小
while (left < right && arr[right] >= pivotValue) {
// 未找到,继续往前找
right--;
}
// 找到了,则把找到小值放到此时左边索引的位置
// 第一次进入时,基准元素已存放到临时值pivotValue了,第一次就相当于放到基准位置了,同时,arr[right]也腾出了一个位置
arr[left] = arr[right];
// 从左边left开始遍历,找到一个数比基准数大
while (left < right && arr[left] <= pivotValue) {
// 未找到,继续往后找
left++;
}
// 找到了,则把找到大值放到此时右边索引的位置(也就是腾出的位置)
// 同时,arr[left]也腾出了一个位置
arr[right] = arr[left];
}
// left等于right说明遍历结束了,把基准元素插入到腾出的位置,也就是arr[left]或者arr[right]
arr[left] = pivotValue;
// 返回基准元素插入的位置
return left;
}
public static void main(String[] args) {
int[] arr = new int[]{19, 28, 8, 23, 10, 21, 9};
log.info("要排序的初始化数据:{}", arr);
//从小到大排序
quickSort(arr, 0, arr.length - 1);
log.info("最后排序后的结果:{}", arr);
}
运行结果:文章来源:https://www.toymoban.com/news/detail-497629.html
要排序的初始化数据:[19, 28, 8, 23, 10, 21, 9]
开始排从【arr[0]】到【arr[6]】数据
返回的基准位置是:3,分区排序后的结果:[9, 10, 8, 19, 23, 21, 28]
开始排从【arr[0]】到【arr[2]】数据
返回的基准位置是:1,分区排序后的结果:[8, 9, 10, 19, 23, 21, 28]
开始排从【arr[4]】到【arr[6]】数据
返回的基准位置是:5,分区排序后的结果:[8, 9, 10, 19, 21, 23, 28]
最后排序后的结果:[8, 9, 10, 19, 21, 23, 28]
结语
只要懂了前面三个部分的分区,那么你理解这个快速排序就容易了,相信我的图已经给你很好的启示了。文章来源地址https://www.toymoban.com/news/detail-497629.html
到了这里,关于(九)Java算法:快速排序(详细图解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!