美文网首页算法程序员数据结构和算法分析
每天学习一点儿算法--快速排序

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

作者: 爱吃西瓜的番茄酱 | 来源:发表于2018-01-11 10:39 被阅读59次

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

    那么分而治之(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处理列表时,基线条件一般是空数组或只包含一个元素的数组

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

    相关文章

      网友评论

        本文标题:每天学习一点儿算法--快速排序

        本文链接:https://www.haomeiwen.com/subject/etjznxtx.html