排序算法图解（五）：快速排序分步刨析

布满荆棘的人生 2023-09-23 14:11 108阅读 0赞

### 文章目录 ###

*  1 快速排序简介
 *  2 思路简介及图解
 *  3 实现代码及运行结果
 *  写在最后

--------------------

# 1 快速排序简介 #

快速排序是对冒泡排序的一种改进。基本思想为：通过一趟排序将要排序的数据分割为独立的两个部分，其中一部分的所有数据比另外一部分的所有数据要小，然后按照此方法对这两部分分别进行快速排序，整个过程可以递归进行，以此达到整个数据变成有序序列。

--------------------

# 2 思路简介及图解 #

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：  
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。  
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。  
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。  
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

**光看思路简介其实还不是很好理解，下面来举例说明**

一般情况下，我们会把数组中的一个数当作基准数（方便起见，会将数组最左边的当作基准数），然后从两边进行检索。按照如下步骤进行：

*  先从右边检索比基准数小的
 *  再从左边检索比基准数大的
 *  一旦检索到，就停下，并将检索到的两个元素进行交换
 *  重复上述步骤，直到检索相遇，则替换基准数，并更新区间，递归进行
 *  最终序列会变得有序

**思路图解：**

该图出自网络，方便起见就以序列：`{6，1，8，0，0，9，5，3，7}` 为例子  
![在这里插入图片描述][4c3b9675d5aa465091ee61f58b8e74df.png]  
具体分析一下第一趟排序：**以6为基准数的步骤**

1.  红色块标识基准数，left、right初始位置如图所示：  
    ![在这里插入图片描述][3cbd0a26277945b0856511f16a018103.png]
2.  right不断向左移动，寻找比基准数小的数，如图所示，找到了3  
    ![在这里插入图片描述][1de9e2fd5540499f93b8c6c811859c65.png]
3.  此时left开始移动，不断向右移动，寻找比基准数大的数，找到了8，这时，left、right都找到了对应的数，进行交换：  
    ![在这里插入图片描述][140ff47b5adb446f9ac53d4b0e7d7360.png]
4.  right继续向左寻找比基准数6小的数，找到后，left继续向右寻找比基准数大的数，当left与right都找到对应的数后，再次进行交换。  
    ![在这里插入图片描述][e52fa990419448af9872a56110b18108.png]
5.  重复上述步骤，right继续向左走，但是此时，left与right相遇，指向了5的位置，则将基准数与该位置的数进行交换，这样就可以观察到，6的左边都是比6小的，右边都是比6大的。  
    ![在这里插入图片描述][8ef6ff238bbc43cf870e4e28a4d3cbff.png]
6.  该过程需要递归进行，直到序列有序。即以5为基准数，递归6左边的区间，再递归右边的，反复进行，直到left >right退出。

# 3 实现代码及运行结果 #

import java.util.Arrays;
    
    /**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 快速排序
     */
    public class QuickSort {
        
    
        public static void main(String[] args) {
        
            int[] arr = {
        6,1,8,0,0,9,5,3,7};
            quickSort(arr, 0, arr.length-1);
            System.out.println("排序后: " + Arrays.toString(arr));
        }
    
        //快速排序
        public static void quickSort(int[] arr, int left, int right) {
        
            //边界条件
            if (left > right){
        
                return;
            }
    
            //定义基准数和左右指针
            int l = left;
            int r = right;
            int base = arr[left];
    
            //循环，将比基准数小的放在左边，比基准数大的放在右边
            while (l != r){
        
                //先从右边找比基准数小的，停下
                while (arr[r] >= base && l < r){
        
                    r--;
                }
                //从左边找比基准数大的，停下
                while (arr[l] <= base && l < r){
        
                    l++;
                }
                //此时已经找到对应的l 和 r，进行交换
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
            //至此，基准数两边都按照需要排好了，只需要将基准数与lr相遇的位置进行交换
            arr[left] = arr[l];
            arr[l] = base;
            //打印中间结果
            System.out.println(Arrays.toString(arr));
            //先向左找
            quickSort(arr, left, r-1);
            //向右递归
            quickSort(arr, l+1, right);
        }
    }

**实现结果：**  
![在这里插入图片描述][a6d561ef9db54cdfa2c2ad740cbfce8b.png]

--------------------

# 写在最后 #

**本文被 [Java数据结构][Java] 收录[点击订阅专栏][Java]** ， 持续更新中。  
 创作不易，如果你有任何问题，欢迎私信，感谢您的支持！

![在这里插入图片描述][7e0ff0501697426a84cd0a1f4eecfdc1.gif_pic_center]

[4c3b9675d5aa465091ee61f58b8e74df.png]: https://img-blog.csdnimg.cn/4c3b9675d5aa465091ee61f58b8e74df.png
[3cbd0a26277945b0856511f16a018103.png]: https://img-blog.csdnimg.cn/3cbd0a26277945b0856511f16a018103.png
[1de9e2fd5540499f93b8c6c811859c65.png]: https://img-blog.csdnimg.cn/1de9e2fd5540499f93b8c6c811859c65.png
[140ff47b5adb446f9ac53d4b0e7d7360.png]: https://img-blog.csdnimg.cn/140ff47b5adb446f9ac53d4b0e7d7360.png
[e52fa990419448af9872a56110b18108.png]: https://img-blog.csdnimg.cn/e52fa990419448af9872a56110b18108.png
[8ef6ff238bbc43cf870e4e28a4d3cbff.png]: https://img-blog.csdnimg.cn/8ef6ff238bbc43cf870e4e28a4d3cbff.png
[a6d561ef9db54cdfa2c2ad740cbfce8b.png]: https://img-blog.csdnimg.cn/a6d561ef9db54cdfa2c2ad740cbfce8b.png
[Java]: https://blog.csdn.net/m0_60353039/category_12062687.html
[7e0ff0501697426a84cd0a1f4eecfdc1.gif_pic_center]: https://img-blog.csdnimg.cn/7e0ff0501697426a84cd0a1f4eecfdc1.gif#pic_center