0


图解快速排序算法

ced485cbb11e458d81a746890b32cf3f.gif

作者:敲代码の流川枫

博客主页:流川枫的博客

专栏:和我一起学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)

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

ced485cbb11e458d81a746890b32cf3f.gif


本文转载自: https://blog.csdn.net/chenchenchencl/article/details/126479237
版权归原作者 敲代码の流川枫 所有, 如有侵权,请联系我们删除。

“图解快速排序算法”的评论:

还没有评论