为什么快速排序算法效率比较高?

快速排序算法是非常高效的一个排序算法,在众多的排序算法里面其无论在时间复杂度还是空间复杂度都是比较低的。因此作为一个程序员,我们很有必要学习和理解快排的原理。

在这之前,我们先来分析下排序算法界里面的Hello World,其就是大名鼎鼎的冒泡排序,这个排序算法因为思想原理和实现都比较简单,所以大部分程序员都信手拈来,但真实情况是这个算法除了名字比较独特外,别的都不值一提,因为其排序的平均时间复杂度是O(n^2),所以在大数据排序时非常之慢。

下面我们用数学方式来推导冒泡排序时间复杂度是如何计算的:

首先冒泡排序是基于比较和交换的,比如我们要对n个数字排序,冒泡排序需要n-1次遍历,比如我们有10个数字,第一趟循环需要比较9次,第二趟循环需要比较8次,第三趟需要比较7次,以此类推,最后一趟需要1次比较。

f(10)=9+8+7+......+1 ,可以转为一个等差数列:

f(n)=(n-1)+(n-2)+(n-3)+......+1= (n-1)*n / 2 = 0.5n^2-0.5n

按照上篇文章中介绍的复杂度的渐近表示,忽略常数系数和第二项变数比较小的情况,冒泡复杂度就近似等于=O(n^2),当然这里是指平均情况。

所以对10个数排序,冒泡排序需要近100次比较(大O表示法,实际50次)

下面我们来分析下快速排序:

快速排序的思想采用的是分治策略,非常类似于老子在道德经里面描述宇宙演变的文字:

道生一,一生二,二生三,三生万物。

快速排序的理论是找到一个基准数,将大于该数的数字全部放在右边,而小于该数字的全部放在左边,如此将一个大数组一切为二,接着在两个小数组里面也采用同样的方法,找基准,大的放右,小的放左,直到分解到子问题里面只有一个数字,这时候把结果及合并就组成了一个有序的集合。

举例子,有如下10个数字:

6,1,2,7,9,3,4,5,10,8

现在我们想要将其按从小到大排序,首先我们要找一个基准pivot,这个数字可以随机取,这里为了方便我们取第一个数字6,然后以6作为界限,将这个大数组分为两半,左边全部小于6,右边全部大于6,具体实现也比较简答,我们定义两个变量i和j,分别从数组的左右出发开始遍历,i=0,j=array.length,在左边向前遍历找到一个大于基准6的数字停下来,这里是7,然后右边向后遍历找到一个小于基准的6的数字5停下来,然后交换数组里面7和5的位置之后继续处理,直到i和j的值相等,我们就结束循环,然后把基准数归位,在分别处理基准左边的数组和基准右边的数组,这里使用递归处理,直到数组里面只剩1个元素就结束处理。

源码如下:

public static void quickSort(int a[],int left,int right ){

        if(left>=right) return;

        int pivot=a[left];
        int i=left;
        int j=right;

        //如果左右指针碰头就代表这一轮迭代结束
        while (i!=j){
            //先从右边开始,找小于pivot点的数字
            //因此,循环的条件是如果大于pivot就继续查找
            //小于pivot就停止
            while(a[j]>=pivot&&i<j){
                count++;
                j--;
            }
            //后从左边开始,找大于pivot的数字
            //因此,循环的条件是如果是小于pivot就继续查找
            //大于pivot就停止
            while(a[i]<=pivot&&i<j){
                count++;
                i++;
            }

            if(i<j) {
                //交换两个数字
                int temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }

        }

        //基准归位
        a[left]=a[i];
        a[i]=pivot;

        quickSort(a,left,i-1);

        quickSort(a,i+1,right);

    }

在main方法调用:

int []a=new int[]{6,1,2,7,9,3,4,5,10,8};
        quickSort(a,0,a.length-1);

快速排序快的主要原因是大大减少了比较和交换的次数,因为按基准数切分的两半数组,在一个数组里面的数据是绝对不会和第二个数组里面的数字产生比较的机会的,所以大幅度降低了做无用功的机会。

下面我们来分析下快排的Ο(nlog2n)的时间复杂度如何得来的,假设我们随机取的基准数总是能把整个数组给平均切成2个子数组:

快排的简化版代码如下:

quick_sort(n){             //数组长度为n
    定位标杆                //比较n-1次
    quick_sort(0,n/2)        //递归快排前n/2个元素
    quick_sort(n/2,array.length)        //递归快排后n/2个元素
}

在《算法导论》第三版101页,可见快速排序的递推式为:T(n)=max(T(q) + T(n-q-1)) +O(n),q为切分长度,如果每次切分都刚好切分成两半,则 q==n-q-1, T(q)==T(n-q-1) ,则简化为 T(n)=2T(n/2)+O(n)。换一下加法项的位置,T(n)=O(n)+2T(n/2),不正是上面的规律吗?第一次比较 9 次,因此 T(10)=9+2T(5),而 T(5)=5+2T(2.5)。因此 T(10)=9+2(4.5+2T(2.5)),即 T(10)=19+2T(5)+4*T(2.5),最终得到上述分析出的规律。 快速排序每次都会以2为低做裂变分解数组,所以最终推出来的渐近复杂度:Ο(nlog2n)

下面我们以随机生成1万个数字,分别用冒泡排序和快速排序来测试:

根据时间复杂度推算:

冒泡排序需要比较次数:1万的平方阶/2=5千万次

快速排序需要比较次数: 10000 * log2 10000 =14*10000=14万次。

下面看1万次测试结果:

排序总个数:10000
===============
总遍历次数:153570
快排耗时:3ms
===========
总遍历次数:49995000
冒泡耗时:19ms

接着看一个10万次的测试结果:

排序总个数:100000
===============
总遍历次数:2146607
快排耗时:79ms
===========
总遍历次数:704982704
冒泡耗时:1305ms

结果符合预期,注意在n越大的情况下,冒泡排序的耗时越长,当量级达到千万级别冒泡排序可能需要半年的时间才能算出来,而快排则在几十秒左右。

平方阶与线性对数阶的图示如下,我们可以看到曲线的倾斜程序相差很大:

当然快排虽然在大多数时候表现很出色,但在一些极端情况下复杂度也会达到O(n^2),比如已经升序拍好的数组,降序排序好的数组,全部重复的数组,当然针对这些case都有优化的方式,重点在于基准数的选择,此外还有两点关于快排的注意事项,第一快排是不稳定的,比如数组原始顺序a=9,b=9,c=10,在快排排序完可能出现b,a,c,而冒泡排序则是稳定的,因为冒泡是相邻的两个元素比较,完全可以自己掌握需不需要交换,如果等于的时候,而快排则没法做到,因为快排不是相邻的两两比较的。第二个需要注意的是快排里面如果采用递归处理,需要注意程序的栈空间是否够用,因为递归调用很容易出现栈溢出的异常。关于快排的一些优化手段我们再后续的文章再分析一下。

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2018-09-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏cs

递归算法

据说凡是可以循环的步骤,都可以递归表示出来。 递归的关键有二点: 1.0 递归公式,即递推式。 2.0 递归出口。 ---- 递归求数组的和 package...

40050
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单...

31740
来自专栏开发与安全

算法:快速排序以及第k小元素的线性选择算法

简要介绍下快速排序的思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行...

249100
来自专栏玄魂工作室

Python黑帽编程2.9 面向对象编程

Python黑帽编程2.9 面向对象编程 我个人认为,计算机语言的发展,有两个方向,一个是从低到高的发展过程,在这个过程中,语言的思考和解决问题的方式是面向硬件...

30570
来自专栏青青天空树

成绩大排队

其中姓名和学号均为不超过10个字符的字符串,成绩为0到100之间的一个整数,这里保证在一组测试用例中没有两个学生的成绩是相同的。

9120
来自专栏海天一树

NOIP 2018提高组初赛C/C++答案详解

分析: 二进制化八进制:从低位(右)往高位(左),每三位直接换成八进制即可。 (1001101011)2 = (10 0110 1011)2 = (26B)...

68940
来自专栏python读书笔记

《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

22160
来自专栏我是攻城师

理解递归算法的原理

递归(Recursion)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法,其核心思想是分治策略。 递归式方法可以被用于解决很多的计算机科...

3.5K20
来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列5

一、是否可以继承String类? String类是final类故不可以继承。 二、面向对象的特征有哪些方面 1.抽象: 抽象就是忽略一个主题中与当前目标无关的...

36150
来自专栏大史住在大前端

野生前端的数据结构练习(9)冒泡排序,选择排序,插入排序

bubble sort的是最基本的算法,被誉为永远会被考从来不被用的算法,基本原则是大数右移,每轮遍历后最右侧的数是最大的,所以下一轮循环时可不予考虑,时间复杂...

8420

扫码关注云+社区

领取腾讯云代金券