我的算法笔记—快速排序

superw 发布于2019-08-15 15:32 / 1558人阅读

摘要：算法介绍由在年提出，因为此算法而获得图灵奖。它是一种递归算法，核心思想是先找出一个数的应该在的位置，将数列分为左右两部分，左右两部分分别进行排序。

算法介绍

由C.A.R.Hoare在1962年提出，因为此算法而获得图灵奖。它是一种递归算法，核心思想是：先找出一个数的应该在的位置，将数列分为左右两部分，左右两部分分别进行排序。

图片示例

我们先找到 K 的位置，i 指针先向后移动，所指元素如果比K大，就停止，此时再由 j 由队尾向前遍历，如果 j 指向元素比K小，j 停止移动，此时将 i 和 j 指向元素对调。
比如：

此时 i 指向元素R比 K 大，j 指向元素C比K小，对调R，C。

此时 i j 根据上述规则继续移动，一直到指针 j 超过了i ，K 和 j 对调

此时K已经在位置上了，将数列分为左右两边，左右再进行递归排序

实现代码

//主方法
private static void sort(Comparable[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, 0, j - 1);
        sort(a, j + 1, hi);
    }

private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo ;
        int j = hi+1;
//a[lo]即为第一个元素，先将它的位置找到
        while (true){
// 找到 i ，i 小于 a[lo]的话，继续移动
            while (less(a[++i],a[lo])){
                if(i == hi){
                    break;
                }
            }
// j 也类似
            while (less(a[lo],a[--j])){
                if(j==lo){
                    break;
                }
            }
// 两指针擦肩而过的话，就跳出循环
            if(i>=j){
                break;
            }
// 交换 i和j
            change(a,i,j);
        }
// 交换 lo和j
        change(a,lo,j);
        return j;
    }

复杂度推导

假设 Cn 为快速排序N个数需要比较的次数。
找到第一个数所在位置，我们需要比较 N+1次。指针 i 和 j 每移动一次就需要比较一次，一共是 N-1次，加上相遇比较一次，擦肩而过还需要比较一次，所以是N+1次。
这个数会把数组分割成各种情况，会分割成(1,n-1),(2,n-2),(3,n-3).......(n-1,1)各种情况，所以Cn的表达式如下：

平均复杂度为1.39NlgN

缺点与不足

 1. 为了保证性能，快速排序前一定要打乱数组顺序，正序下，快排复杂度需要1/2 
    乘以n的二次方
    

 2. 如果数组存在大量相同的数，性能也是平方级的

第一次写博客，这是我的理解，如果有误请指出，我会立即纠正，谢谢

云服务器 GPU云服务器快速排序算法最好的快速排序算法最快速的排序算法快速排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69118.html

【算法】算法图解笔记_算法简介

摘要：在本书中你将学习比较不同算法的优缺点该使用合并排序算法还是快速排序算法或者该使用数组还是链表。这样的算法包括快速排序一种速度较快的排序算法。在读《算法图解》这本书，这本书有两个优点：手绘风格的图，看着很让人入戏；算法采用Python语言描述，能更好的表达算法思想。关于算法的学习有两点心得：算法思想最重要，理解了思想，算法是很容易写出来的，所以尽量不要把过多精力放在细节上...

tomlingtm 2019-07-31 10:10 评论0 收藏0
算法学习笔记：排序算法(二)

摘要：上一篇中已经介绍了几个简单的排序算法，这一篇文章我将继续向大家介绍排序算法相关的内容，本篇的会介绍希尔排序快速排序归并排序以及分治算法的思想，希望通过本文章能够加深大家对排序算法的理解。上一篇中已经介绍了几个简单的排序算法，这一篇文章我将继续向大家介绍排序算法相关的内容，本篇的会介绍希尔排序、快速排序、归并排序以及分治算法的思想，希望通过本文章能够加深大家对排序算法的理解。希尔排序...

William_Sang 2019-08-23 14:40 评论0 收藏0
【算法】算法图解笔记_选择排序

摘要：选择排序是下一章将介绍的快速排序的基石。需要存储多项数据时有两种基本方式数组和链表。但它们并非都适用于所有的情形因此知道它们的差别很重要。选择排序是一种灵巧的算法但其速度不是很快。选择排序是下一章将介绍的快速排序的基石。内存的工作原理计算机就像是很多抽屉的集合体,每个抽屉都有地址。showImg(https://segmentfault.com/img/bVbpWvv?w=413...

mylxsw 2019-07-31 10:12 评论0 收藏0
【算法】算法图解笔记_快速排序

摘要：再谈大表示法快速排序的独特之处在于其速度取决于选择的基准值。在平均情况下快速排序的运行时间为在最糟情况下退化为。快速排序和合并排序的算法速度分别表示为和，是算法所需的固定时间量被称为常量。分而治之分而治之(divide and conquer,D&C)是一种著名的递归式问题解决方法。只能解决一种问题的算法毕竟用处有限,而D&C提供了解决问题的思路,是另一个可供你使用的工具。 D&C...

YanceyOfficial 2019-07-31 10:14 评论0 收藏0
思维导图整理大厂面试高频数组24: 合并两个有序数组的两种双指针思想, 力扣88

摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所 ...

darkerXi 2021-11-17 09:33 评论0 收藏0