详解快速排序

2020年4月13日15:16:45算法评论44阅读模式

基本思想

本文的思路是以从小到大为例讲的。
快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个,最后一个,也可以是中间任何一个),习惯将其称为pivot,枢轴元素;
将所有比枢轴元素小的放在其左边;
将所有比它大的放在其右边;
形成左右两个子表;
然后对左右两个子表再按照前面的算法进行排序,直到每个子表的元素只剩下一个。文章源自随机的未知-https://sjdwz.com/11133.html

可见快速排序用到了分而治之的思想。
将一个数组分成两个数组的方法为:
先从数组右边找到一个比枢轴元素小的元素,将数组的第一个位置赋值为该元素;
再从数组的左边找到一个比枢轴元素大的元素,将从上面取元素的位置赋值为该值;
依次进行,直到左右相遇,把枢轴元素赋值到相遇位置。文章源自随机的未知-https://sjdwz.com/11133.html

例子

输入数组
arr 为 [39 , 28 , 55 , 87 , 66 , 3 ,17 ,39]
为了区别两个相同元素,将最后一个加上 * ;
初始状态如下图:
详解快速排序
定义一枢轴元素pivot,初始化为第一个元素得值,即39;
查询左边的元素的变量为left,初始值为第一个元素的索引,0;
查询右边的元素的变量为right,初始值为第一个元素的索引,7。
如下图:文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
初始化

演示第一轮排序过程
从右边开始,从右边找到一个比枢轴元素小的,如果没找到right一直自减1;文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
然后把当前left所在元素赋值为该值;
这里right所指元素并没有空,只是为了好演示,设置为空(下同);文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
第一轮排序状态2

然后从左边开始找一个比枢轴元素pivot大的元素;如果没找到left一直自增1;文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
第一轮排序状态3

将当前right所指元素设为该值;文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
第一轮排序状态4

然后从右边找到一个比枢轴元素小的,如果没找到right一直自减1;文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
第一轮排序状态5

将当前left所指元素设为该值;文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
第一轮排序状态6

然后从左边开始找一个比枢轴元素pivot大的元素;如果没找到left一直自增1;文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
第一轮排序状态7

将当前right所指元素设为该值;文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
第一轮排序状态8

然后从右边找到一个比枢轴元素小的,如果没找到right一直自减1;文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
第一轮排序状态9

这时left和right相遇了,将枢轴元素赋值给当前位置。文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
第一轮排序动态过程:文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
然后将数组分成了文章源自随机的未知-https://sjdwz.com/11133.html

[17,28,3] 与 [66, 87, 55, 39*]两部分;再对这两部分进行上述环节即可。
反反复复,直到只剩下一个元素。文章源自随机的未知-https://sjdwz.com/11133.html

排序全过程文章源自随机的未知-https://sjdwz.com/11133.html

详解快速排序
排序全过程

代码

对每一个数组进行分化的代码如下:
初始化pivot为数组第一个元素;
只要left还小于right就进行循环;
外层循环内部如下:
先从右边找一个比枢轴元素小的元素;
将当前left所指元素赋值为找到的元素;
再从左边找一个比枢轴元素大的元素;
将当前right所指元素赋值为找到的元素;
当left和right相等将枢轴元素赋值在此。
最后返回中间元素的索引。文章源自随机的未知-https://sjdwz.com/11133.html

public static int partition(int[] arr,int left,int right){
        int pivot = arr[left];
        while(left < right){
            while(left<right && arr[right] >= pivot)
                right--;
            arr[left] = arr[right];
            while(left < right && arr[left]<= pivot)
                left++;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }

快排代码:
第一个是快排的重载,直接传数组;
然后调用另一个重载函数,传数组,left为第一个元素索引0,right为最后一个元素索引数组长度减去1;
主要介绍传三个参数的快排函数:
定义一个将来划分为两个数组的中间元素的索引;
如果left比right小,进行一次划分,将返回来的值赋值给middle;
对left到middle - 1的部分进行一次快排(递归进行);
对middle + 1到right的部分进行一次快排(递归进行)。文章源自随机的未知-https://sjdwz.com/11133.html

public static void quickSort(int[] arr){
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int left,int right){
        int middle;
        if(left < right){
            middle = partition(arr,left,right);
            quickSort(arr,left,middle-1);
            quickSort(arr,middle+1,right);
        }
    }

完整代码:文章源自随机的未知-https://sjdwz.com/11133.html

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        quickSort(new int[]{39,28,55,87,66,3,17,39});
    }

    public static void quickSort(int[] arr){
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int left,int right){
        int middle;
        if(left < right){
            middle = partition(arr,left,right);
            quickSort(arr,left,middle-1);
            quickSort(arr,middle+1,right);
        }
    }

    public static int partition(int[] arr,int left,int right){
        int pivot = arr[left];
        while(left < right){
            while(left<right && arr[right] >= pivot)
                right--;
            arr[left] = arr[right];
            while(left < right && arr[left]<= pivot)
                left++;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }
}

时间复杂度

理想的情况:
每次划分所选择的中轴元素恰好将当前序列几乎等分,经过趟划分,便可以排序完毕。这样,所以理想状态下整个算法的时间复杂度为。
最坏的情况是,每次所选的中间数是当前序列中的最值元素,这时每次划分的两个子表一个长度是0,一个是当前数组长度减去1。这样的话,长度为n的数组需要经过n趟划分,这时的时间复杂度为;
为改善最坏情况下的时间性能,可以在最枢轴元素的原则中进行优化,选第一个元素,最后一个元素,中间元素中的中位数即可。
这时,快速排序的时间复杂度即为。文章源自随机的未知-https://sjdwz.com/11133.html

稳定性

如下面的数组
相同元素用 * 标出
[ 2 , 3 , 1, 1* ]
第一次排序为
[1* , 1, 2, 3]
第二次为
[1* , 1 , 2 , 3]
相对顺序发生了变化,所以是不稳定的。文章源自随机的未知-https://sjdwz.com/11133.html

欢迎关注

欢迎大家的关注文章源自随机的未知-https://sjdwz.com/11133.html

扫描下方的二维码关注我的微信公众号:code随笔
详解快速排序文章源自随机的未知-https://sjdwz.com/11133.html

文章源自随机的未知-https://sjdwz.com/11133.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
算法最后更新:2022-2-24
  • 本文由 发表于 2020年4月13日15:16:45
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11133.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定