图解快速排序算法

作者：敲代码の流川枫

博客主页：流川枫的博客

专栏：和我一起学java

语录：Stay hungry stay foolish

工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网

点击免费注册和我一起刷题吧

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两个下标如图

1. L从左向右移动，一旦发现比Pivot大的数字，将它放在该序列右边；R从右向左移动，一旦发现有数字小于Pivot，则把数字放到该序列左边，最终LR会在某个位置相遇重合，将Pivot放在这个位置，至此第一次排序结束。此时左边的数全小于Pivot，右边的数全大于Pivot，形成左右子序列

R指向8，8<25，将它放到序列左边L处

L和R交替移动，L指向100，100>25，将它移动到序列右边R处

R和L交替移动，R向左移动，指向1，1<25，将它移动到序列左边L处

L和R交替移动，L指向9，9<25，将它放在原位，L继续移动

L向左移动指向20，20<25，将他放在原位，L继续左移

L和R相遇，将Povit放在相遇的位置，并且分出来了左右子序列如图：

1. 现在对左子序列和右子序列进行同样的操作，因为右子序列只有一个数，默认有序

1. 对右子序列继续排序：

1. 至此排序完成：

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();
    }
}

结果：

4. 快排特点及性能

特点：

快速排序是在冒泡排序的基础上改进而来的，冒泡排序每次只能交换相邻的两个元素，而快速排序是跳跃式的交换

快速排序是一个不稳定的算法，在经过排序之后，可能会对相同值的元素的相对位置造成改变

快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的

性能：

时间复杂度

快速排序在最坏情况下的时间复杂度和冒泡排序一样，是

O(n2)

，实际上每次比较都需要交换，但是这种情况并不常见，思考一下如果每次比较都需要交换，那么数列的平均时间复杂度是

O(nlogn)

，事实上在大多数时候，排序的速度要快于这个平均时间复杂度。这种算法实际上是一种分治法思想，也就是分而治之，把问题分为一个个的小部分来分别解决，再把结果组合起来

空间复杂度

快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的空间复杂度为

O(logn)

，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为

O(n)

。所以我们一般认为快速排序的空间复杂度为

O(logn)

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