快速排序的Python实现

上一篇 / 下一篇  2020-11-14 18:18:30 / 个人分类:算法

目录

  • 快速排序的介绍
  • 快速排序的Python实现

快速排序的介绍

快速排序(quick sort)的采用了分治的策略。

  • 分治策略指的是:
    将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
  • 快排的基本思想是:
    在序列中找一个划分值,通过一趟排序将未排序的序列排序成 独立的两个部分,其中左边部分序列都比划分值小,右边部分的序列比划分值大,此时划分值的位置已确认,然后再对这两个序列按照同样的方法进行排序,从而达到整个序列都有序的目的。
  • 快速排序的Python实现

    先来看一个 我更想称之为伪快排的快排代码:

    defquick_sort(array):iflen(array)<2:returnarrayelse:pivot=array[0]less_than_pivot=[xforx inarrayifx<=pivot]more_than_pivot=[xforx inarrayifx>pivot]returnquick_sort(less_than_pivot)+[pivot]+quick_sort(more_than_pivot)

    这段代码最关键的是pivot这个参数,这段代码里取序列的第一个元素,然后以这个元素为分组的基准,利用列表解析式使得它左边的值都比它小,右边的值都比它大。然后再分别对这些序列进行递归排序。

    这段代码虽然短小利于理解,但是其效率很低,主要体现在以下方面:

    • 分组基准的选取过于随便,不一定可以取到列表的中间值
    • 空间复杂度大,使用了两个列表解析式,而且每次选取进行比较时需要遍历整个序列。
    • 若序列长度过于小(比如只有几个元素),快排效率就不如插入排序了。
    • 递归影响性能,最好进行优化。

    下面用Python写一个C风格的快排(这里可以体会到快排的精髓):

    defquick_sort(L):returnq_sort(L,0,len(L)-1)defq_sort(L,left,right):ifleft<right:pivot=Partition(L,left,right)q_sort(L,left,pivot-1)q_sort(L,pivot+1,right)returnL
    
    defPartition(L,left,right):pivotkey=L[left]whileleft<right:whileleft<rightand L[right]>=pivotkey:right-=1L[left]=L[right]whileleft<rightand L[left]<=pivotkey:left+=1L[right]=L[left]L[left]=pivotkeyreturnleftL=[5,9,1,11,6,7,2,4]printquick_sort(L)

    快速排序需要提供三个参数:待排序序列序列最小下标值left序列最大下标值right。让用户提供这三个参数很麻烦。这里写个函数进行封装:

    defquick_sort(L):returnq_sort(L,0,len(L)-1)

    下面看一下q_sort函数:

    defq_sort(L,left,right):ifleft<right:pivot=Partition(L,left,right)q_sort(L,left,pivot-1)q_sort(L,pivot+1,right)returnL

    这个函数的核心是pivot = Partition(L, left, right),在执行它之前,列表的值为[5, 9, 1, 11, 6, 7, 2, 4],而Partition函数做的事情是找到一个分组标准,然后进行分组,让它左边的值比它小,右边的值比它大。
    在经过Partition函数分组后,列表变为[4, 2, 1, 5, 6, 7, 11, 9],并把5的下标值(也就是3)返回给pivot,此时列表变成两个小列表[4, 2, 1]和[5, 6, 7, 11, 9] ,之后调用q_sort,就是调用q_sort(L,0, 2)q_sort(L, 4 ,7),对其进行Partition操作,直到整个列表有序为止。

    下面看看关键的Partition函数是如何做的:

    defPartition(L,left,right):pivotkey=L[left]whileleft<right:whileleft<rightand L[right]>=pivotkey:right-=1L[left]=L[right]whileleft<rightand L[left]<=pivotkey:left+=1L[right]=L[left]L[left]=pivotkeyreturnleft

    以一趟排序为例[5, 9, 1, 11, 6, 7, 2, 4]

    • 开始排序时,left=0,right=7,首先用表的第一个下标值作为 分组关键字pivot,


                                                                     第一趟排序过程
    进行while left < right and L[right] >= pivotkey:判断,其中L[right]=4 不满足条件,跳出循环,执行L[left] = L[right],执行后列表变成:

                            第一趟排序结果

    然后进行while left < right and L[left] <= pivotkey:,L[left] = 4 <= 5,条件成立,left向右边移动,然后L[left] = 9 不满足条件,执行L[right] = L[left],执行后列表变为:
                                                     第一趟排序过程
    然后进行while left < right判断,条件成立,继续进行判断while left < right and L[right] >= pivotkey:,L[right] = 9,满足条件,right向左移动1,继续判断,不满足条件,执行L[left] = L[right],执行后列表变为:
                        第一趟排序过程
    然后进行while left < right and L[left] <= pivotkey:判断,L[left] = 2,满足条件,left向右移动,然后L[left] = 1,满足条件,left向右移动,L[left] = 11,不满足条件,执行L[right] = L[left],执行后列表变为:
                                    第一趟排序过程
    然后进行while left < right判断,条件成立,继续进行判断:while left < right and L[right] >= pivotkey:,满足条件,right向左移动,一直移动到这样的状态:

                                         第一趟排序过程
    此时不满足条件:left < right,跳出循环。然后执行L[left] = pivotkey,并返回left下标值。此时序列变为:
                                           第一趟排序结果


    接下来就是用递归分别对子列表进行排序。读者可以自己试试。

    问题的优化

    • 分组基准
      对于上面的代码,分组基准的选取只是取列表的第一个值,太过于随便,当取到序列的中间值时,快排效率是最高的,第一个值未必是列表的中间值。为了解决这个问题,我们可以选取列表中的几个值进行简单的比较,然后取这几个值的中间值 作为分组基准。 这里就不写代码了,读者可以自己实现。

    • 空间使用大。
      上面的代码已经解决了比较次数的问题。

    • 若序列长度过于小(比如只有几个元素),快排效率就不如插入排序了。
      我们可以设置一个列表元素大小的临界值,若小于这个值,就用插入排序,大于这个值用快排。



    作者:一根薯条
    链接:https://www.jianshu.com/p/2b2f1f79984e
    来源:简书



    TAG:

     

    评分:0

    我来说两句

    显示全部

    :loveliness: :handshake :victory: :funk: :time: :kiss: :call: :hug: :lol :'( :Q :L ;P :$ :P :o :@ :D :( :)

    Open Toolbar