图解快速排序算法

灰太狼 2023-10-10 14:47 48阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 2]

![57044f4b64f64ef592168224f1fff0b1.png][]

![f66f4c9cc88045eda9d045bf311594d6.png][]

**文章目录**

1. 算法思想

2. 算法图解

3. 代码实现

4. 快排特点及性能

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

## 1. 算法思想 ##

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列

> 步骤：
> 
> 1. 选定Pivot为中心轴
> 
> 2. 将大于Pivot的数字放在Pivot的右边
> 
> 3. 将小于Pivot的数字放在Pivot的左边
> 
> 4. 分别对左右子序列重复前三步操作

## 2. 算法图解 ##

>     int[] array = {25,100,9,20,1,8};
> 
> 以数组array为例图解快速排序
> 
> 1. 为了方便起见，我们每次都选取最左边的数字为中心轴Pivot，要把小于19的数字放在19左边，把大于19的数字放在19右边，如何达到目的呢？我们设置了L和R两个下标如图
> 
> ![81b692d783264502a1348dd5d160fed2.png][]

> 2. L从左向右移动，一旦发现比Pivot大的数字，将它放在该序列右边；R从右向左移动，一旦发现有数字小于Pivot，则把数字放到该序列左边，最终LR会在某个位置相遇重合，将Pivot放在这个位置，至此第一次排序结束。此时左边的数全小于Pivot，右边的数全大于Pivot，形成左右子序列
> 
> R指向8，8<25，将它放到序列左边L处
> 
> ![d7366d1fbe244e868fc7f6b417ae028c.png][]
> 
> L和R交替移动，L指向100，100>25，将它移动到序列右边R处
> 
> ![40bfdafbbea540a895d053a47863d9c2.png][]
> 
> R和L交替移动，R向左移动，指向1，1<25，将它移动到序列左边L处
> 
> ![549cb92904f14f489f86d4cdb9cdbf37.png][]
> 
> L和R交替移动，L指向9，9<25，将它放在原位，L继续移动
> 
> ![03781b806a44457a88fa5a44891f804e.png][]
> 
> L向左移动指向20，20<25，将他放在原位，L继续左移
> 
> ![32d52e1d80c54a8ebb6b42eb9eb81db5.png][]
> 
> L和R相遇，将Povit放在相遇的位置，并且分出来了左右子序列如图：
> 
> ![2a65b7e00ad049e3bc88e4e4405b611a.png][]

> 3. 现在对左子序列和右子序列进行同样的操作，因为右子序列只有一个数，默认有序
> 
> ![38b42780b4a84b019105072de98fa878.png][]
> 
> ![a3cf96c5a6a946bf97d988d7ebff6a2d.png][]
> 
> ![e03159cbcc7742659a4b5880ec8fdee2.png][]
> 
> ![7746b21fc0de4eb5ae7415f6d2cf0e01.png][]
> 
> ![bfc3070c6c18404b9fe094dff6ef20a1.png][]

> 4. 对右子序列继续排序：
> 
> ![58ed849f104140a487b1c4b64cfcd20f.png][]
> 
> ![90765eff2c3a4429a87dda3cdd0dc6ed.png][]

> 5. 至此排序完成：
> 
> ![addfbeb0817b4795b779b17fd5457fd1.png][]

## 3. 代码实现 ##

代码：

public class QuickSort {
        private int[] array;
        public QuickSort(int[] array){
            this.array = array;
        }
        public void sort() {
            quickSort(array,0,array.length-1);
        }
        public void print() {
            for (int i = 0; i < array.length; i++) {
                System.out.println(array[i]);
            }
        }
    
        public void quickSort(int[] array,int left,int right) {
            if(left<right){
                int Povit = array[left];
                int L = left;
                int R = right;
                while(L<R){
                    while(L < R && array[R]>Povit){
                        R--;
                    }
                    if(L < R) {
                        array[L] = array[R];
                        L++;
                    }
                    while(L < R && array[L] < Povit){
                        L++;
                    }
                    if(L < R){
                        array[R] = array[L];
                        R--;
                    }
                }
                array[R] = Povit;
                quickSort(array,left,R-1);
                quickSort(array,R+1,right);
            }
        }
    }
    
    class SortTest {
        public static void main(String[] args) {
            testQuickSort();
        }
        /**
         * 快速排序
         */
        private static void testQuickSort() {
            int[] array = {25,100,9,20,1,8};
            QuickSort quickSort = new QuickSort(array);
            quickSort.sort();
            quickSort.print();
        }
    }

结果：

![5df02c9729a4442a9d0cadc06788d07b.png][]

## 4. 快排特点及性能 ##

> 特点：
> 
> 快速排序是在冒泡排序的基础上改进而来的，冒泡排序每次只能交换相邻的两个元素，而快速排序是跳跃式的交换
> 
> 快速排序是一个不稳定的算法，在经过排序之后，可能会对相同值的元素的相对位置造成改变
> 
> 快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的

> 性能：
> 
> 时间复杂度
> 
> 快速排序在最坏情况下的[时间复杂度][Link 3]和冒泡排序一样，是 `O(n2)`，实际上每次比较都需要交换，但是这种情况并不常见，思考一下如果每次比较都需要交换，那么数列的平均时间复杂度是 `O(nlogn)`，事实上在大多数时候，排序的速度要快于这个平均时间复杂度。这种算法实际上是一种分治法思想，也就是分而治之，把问题分为一个个的小部分来分别解决，再把结果组合起来
> 
> 空间复杂度
> 
> 快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的[空间复杂度][Link 3]为 `O(logn)`，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 `O(n)`。所以我们一般认为快速排序的空间复杂度为 `O(logn)`

> “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

![ced485cbb11e458d81a746890b32cf3f.gif][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[57044f4b64f64ef592168224f1fff0b1.png]: https://img-blog.csdnimg.cn/57044f4b64f64ef592168224f1fff0b1.png
[f66f4c9cc88045eda9d045bf311594d6.png]: https://img-blog.csdnimg.cn/f66f4c9cc88045eda9d045bf311594d6.png
[81b692d783264502a1348dd5d160fed2.png]: https://img-blog.csdnimg.cn/81b692d783264502a1348dd5d160fed2.png
[d7366d1fbe244e868fc7f6b417ae028c.png]: https://img-blog.csdnimg.cn/d7366d1fbe244e868fc7f6b417ae028c.png
[40bfdafbbea540a895d053a47863d9c2.png]: https://img-blog.csdnimg.cn/40bfdafbbea540a895d053a47863d9c2.png
[549cb92904f14f489f86d4cdb9cdbf37.png]: https://img-blog.csdnimg.cn/549cb92904f14f489f86d4cdb9cdbf37.png
[03781b806a44457a88fa5a44891f804e.png]: https://img-blog.csdnimg.cn/03781b806a44457a88fa5a44891f804e.png
[32d52e1d80c54a8ebb6b42eb9eb81db5.png]: https://img-blog.csdnimg.cn/32d52e1d80c54a8ebb6b42eb9eb81db5.png
[2a65b7e00ad049e3bc88e4e4405b611a.png]: https://img-blog.csdnimg.cn/2a65b7e00ad049e3bc88e4e4405b611a.png
[38b42780b4a84b019105072de98fa878.png]: https://img-blog.csdnimg.cn/38b42780b4a84b019105072de98fa878.png
[a3cf96c5a6a946bf97d988d7ebff6a2d.png]: https://img-blog.csdnimg.cn/a3cf96c5a6a946bf97d988d7ebff6a2d.png
[e03159cbcc7742659a4b5880ec8fdee2.png]: https://img-blog.csdnimg.cn/e03159cbcc7742659a4b5880ec8fdee2.png
[7746b21fc0de4eb5ae7415f6d2cf0e01.png]: https://img-blog.csdnimg.cn/7746b21fc0de4eb5ae7415f6d2cf0e01.png
[bfc3070c6c18404b9fe094dff6ef20a1.png]: https://img-blog.csdnimg.cn/bfc3070c6c18404b9fe094dff6ef20a1.png
[58ed849f104140a487b1c4b64cfcd20f.png]: https://img-blog.csdnimg.cn/58ed849f104140a487b1c4b64cfcd20f.png
[90765eff2c3a4429a87dda3cdd0dc6ed.png]: https://img-blog.csdnimg.cn/90765eff2c3a4429a87dda3cdd0dc6ed.png
[addfbeb0817b4795b779b17fd5457fd1.png]: https://img-blog.csdnimg.cn/addfbeb0817b4795b779b17fd5457fd1.png
[5df02c9729a4442a9d0cadc06788d07b.png]: https://img-blog.csdnimg.cn/5df02c9729a4442a9d0cadc06788d07b.png
[Link 3]: http://data.biancheng.net/view/294.html