专栏首页一个爱吃西瓜的程序员每天学习一点儿算法--快速排序

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

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。

那么分而治之(D&C)是一种怎样的策略呢?

分而治之

分而治之(D&C)的要点只有两个:

  • 找出简单的基线问题
  • 确定如何缩小问题的规模,使其符合基线条件

D&C不是一种解决问题的算法,而是一种解决问题的思路。比如看下面这个例子: 这是一个数字数组:

你需要将这些数字相加,并返回结果。使用循环可以很轻松地解决这个问题:

def sum(arr):    
    """一个数组元素相加的循环"""
    total = 0
    for i in arr:
        total += i    
    return total

print(sum([2, 4, 6]))

但是如何使用递归函数来完成这种任务呢?

  • 第一步:找出基线条件。如何一个数组只包含一个或者零个元素,那计算总和将会非常容易:

这就是基线条件

  • 第二步:缩小问题规模,使其符合基线条件。如果递归调用都使其里空数组更近了一步,那么这就缩小了问题规模。

下面用代码实现这个过程:

def sum(arr):    
    """计算列表的各元素总和"""
    if arr == []:        
        return 0
    else:        
        return arr[0] + sum(arr[1:])

s = sum([2, 4, 6])
print(s)

说了这么多,却好像还是在说递归的知识,这和快速排序有什么关系呢?

快速排序

对于排序算法来说,最简单的数组是什么样的?对,没错,最简单的数组就是不需要排序的数组:

因此,在涉及多个元素的数组进行排序的时候,我们可以利用分而治之策略:将数组分解,直到满足基线条件为止。

简要叙述一下快速排序的基本思想:

  • 首先,从数组中选取一个元素,这个元素被称为基准值
  • 将数组分为两个子数组:小于基准值的元素和大于基准值的元素
  • 对这两个子数组进行快速排序

可能有小伙伴到这里又懵了,这不还是没有说清楚快速排序到底是怎么排的嘛。

客官别急,下面来说快速排序的具体实现步骤:

  • 设置两个变量i、j,排序开始的时候:i=0,j=N-1
  • 以第一个数组元素作为关键数据,赋值给key,即key=A[0]
  • 从j开始向前搜索,即由后开始向前搜索(j—),找到第一个小于key的值A[j],将A[j]和A[i]互换
  • 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换
  • 重复第3、4步,直到i=j

用一个例子来说明:

下面用代码实现快速排序:

def quicksort(array):    
    """快速排序"""
    if len(array) < 2:        
        return array  # 基线条件:为空或者只包含一个元素的数组是有序的
    else:
        pivot = array[0]  # 递归条件
        less = [i for i in array[1:] if i <= pivot]  # 由所有小于或等于基准值的元素组成的子数组

        greater = [i for i in array[1:] if i > pivot]  # 由所有大于基准值的元素组成的子数组

        return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

再谈大O表示法

快速排序的独特之处在于,其速度取决于选择的基准值。这也就产生了最佳情况和最糟情况之分。

在最佳情况下,快速排序的运行时间为O(n ㏒n)。 在最糟情况下,快速排序的运行时间为O(n²)。

说明:最佳情况也是平均情况。

我们一般使用大O表示法都是指的算法的平均情况,所以我们一般认为快速排序的运行时间为O(n ㏒n)。至于何为最佳情况和最糟情况,这里不再过多阐述了。

小结

  • 大O表示法指的是算法的平均时间
  • 大O表示法省略了常数
  • 快速排序的平均运行时间为O(n ㏒n)
  • 使用D&C处理列表时,基线条件一般是空数组或只包含一个元素的数组

每天学习一点点,每天进步一点点。

本文分享自微信公众号 - 小白客(youcoding),作者:爱吃西瓜的番茄酱

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-11

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每天学习一点儿算法--选择排序

    很多算法只有在数据经过排序后才管用,比如我们之前学习的二分查找。当然,很多语言都内置了排序算法,比如Python中的sort()函数和sorted()函数。我们...

    爱吃西瓜的番茄酱
  • 学习SQL【7】-函数

    终于可以开原创标识和留言功能了,开心。我坚信努力总会有收获的。 不仅SQL, 对所有的编程语言来说,函数都起着至关重要的作用。函数就像是编程语言的“道具箱”...

    爱吃西瓜的番茄酱
  • 常用SQL语句和语法汇总

    近几年数据库发挥了越来越重要的作用,这其中和大数据、数据科学的兴起有不可分割的联系。学习数据库,可以说是每个从事IT行业的必修课。你学或不学,它就在那里;你想或...

    爱吃西瓜的番茄酱
  • 经典算法巡礼(二) -- 排序之选择排序

    选择排序,如冒泡排序一样,从名字中即可大概猜测其排序的原理。其工作原理就是从未排序的数组中选出最大(小)的元素,将其放置至数组的首(尾)部,重复此过程直至没有未...

    jiezhu
  • Matlab系列之数组的基本操作

    本篇记录的是基本的数组操作,将包括数组元素的寻址、查找和排序,本来是打算本矩阵的基本操作也介绍下,不过时间比较感觉不太够,就留到下一篇再进行记录了,先把上一篇和...

    狂人V
  • 算法基础:五大排序算法Python实战教程

    排序是每个软件工程师和开发人员都需要掌握的技能。不仅要通过编程面试,还要对程序本身有一个全面的理解。不同的排序算法很好地展示了算法设计上如何强烈的影...

    加米谷大数据
  • 面试汇总(九):数据结构与算法常见面试总结(二)——堆与栈、数组、排序

      上一篇文章我们介绍了在面试中数据结构中树的常见的面试题。这篇文章我们继续给大家介绍常见的问题。

    stefan666
  • C语言中你必须知道的几大排序算法

    在实际使用数组的过程中,数组不仅可以存储多个同类型的数据,而且要求这些数据按照某种特征进行排序。例如,学生的成绩,需要按照从高到低的顺序排列,这就需要使用排序算...

    诸葛青云
  • 算法一看就懂之「 选择排序 」

    上一篇文章咱们已经聊过「 冒泡排序 」和「 插入排序 」了,今天我们来看一看「 选择排序 」。「 选择排序 」虽然在实际应用中没有「 插入排序 」广泛,但它也是...

    奎哥
  • LeetCode | 66.加一

    这道题目的思路比较符合我们平时列竖式的思路,这道题目我使用 C 语言进行完成,看我下面的分析。

    码农UP2U

扫码关注云+社区

领取腾讯云代金券