内容字号:默认大号超大号

段落设置:段首缩进取消段首缩进

字体设置:切换到微软雅黑切换到宋体

快速排序的Python实现

2018-04-16 17:22 出处:清屏网 人气: 评论(0

目录

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

快速排序的介绍

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

  • 分治策略指的是:
    将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
  • 快排的基本思想是:
    通过一趟排序将 未排序的序列 分割成 独立的两个部分,其中一部分序列 比 另一部分的序列 都小,然后再把这两个序列进行排序,从而达到整个序列都有序的目的。

快速排序的Python实现

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

def quick_sort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less_than_pivot = [x for x in array if x < pivot]
        more_than_pivot = [x for x in array if x > pivot]
        return quick_sort(less_than_pivot) + [pivot] + quick_sort(more_than_pivot)

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

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

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

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

def quick_sort(L):
    return q_sort(L, 0, len(L) - 1)

def q_sort(L, left, right):
    if left < right:
        pivot = Partition(L, left, right)

        q_sort(L, left, pivot - 1)
        q_sort(L, pivot + 1, right)
    return L

def Partition(L, left, right):
    pivotkey = L[left]

    while left < right:
        while left < right and L[right] >= pivotkey:
            right -= 1
        L[left] = L[right]
        while left < right and L[left] <= pivotkey:
            left += 1
        L[right] = L[left]

    L[left] = pivotkey
    return left

L = [5, 9, 1, 11, 6, 7, 2, 4]

print quick_sort(L)

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

def quick_sort(L):
    return q_sort(L, 0, len(L) - 1)

下面看一下 q_sort 函数:

def q_sort(L, left, right):
    if left < right:
        pivot = Partition(L, left, right)

        q_sort(L, left, pivot - 1)
        q_sort(L, pivot + 1, right)
    return L

这个函数的核心是 pivot = Partition(L, left, right) ,在执行它之前,列表的值为 [5, 9, 1, 11, 6, 7, 2, 4] ,而 Partition 函数做的事情是找到一个分组标准,然后进行分组,让它左边的值比它小,右边的值比它大。

在经过 Partition 函数分组后,列表变为 [4, 2, 1, 5, 6, 7, 11, 9] ,并把3的下标值返回给 pivot ,此时列表变成两个小列表[4, 2, 1]和[5, 6, 7, 11, 9] ,之后调用 q_sort ,就是调用 q_sort(L,0, 2)q_sort(L, 4 ,7) ,对其进行 Partition 操作,直到整个列表有序为止。

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

def Partition(L, left, right):
    pivotkey = L[left]

    while left < right:
        while left < right and L[right] >= pivotkey:
            right -= 1
        L[left] = L[right]
        while left < right and L[left] <= pivotkey:
            left += 1
        L[right] = L[left]

    L[left] = pivotkey
    return left

以一趟排序为例 [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下标值。此时序列变为:

    第一趟排序结果

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

问题的优化

  • 分组基准

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

  • 空间使用大。

    上面的代码已经解决了空间和比较次数的问题。

  • 若序列长度过于小(比如只有几个元素),快排效率就不如插入排序了。

    我们可以设置一个列表元素大小的临界值,若小于这个值,就用插入排序,大于这个值用快排。

分享给小伙伴们:
本文标签: 快速排序Python

相关文章

发表评论愿您的每句评论,都能给大家的生活添色彩,带来共鸣,带来思索,带来快乐。

CopyRight © 2015-2016 QingPingShan.com , All Rights Reserved.

清屏网 版权所有 豫ICP备15026204号