Python实现快速排序

内容简介：Python实现快速排序

快速 排序 采用了分治的思想，基本思想是选取数组中一个数为基准数（一般选择数组中的第一个数），一次排序过程中，将比基准数小的都放在它左侧，比基准数大的放在它的右侧。经过这次排序后得到两个数组和一个基准数，数组1中全部元素小于基准数，数组2中的全部元素大于基准数，然后对数组1，2分别进行同样的排序（递归），最后直到剩下一个数字。

下面给出 Python 代码实现

def partiton(li, low, high):

key = li[low]

while low < high:

while low < high and li[high] >= key:

high -= 1

if low < high:

li[low], li[high] = li[high], li[low]

while low < high and li[low] < key:

low += 1

if low < high:

li[high], li[low] = li[low], li[high]

return low

def quickSort(li, low, high):

if low >= high:

return

center = partiton(li, low, high)

quickSort(li, low, center - 1)

quickSort(li, center + 1, high)

关于实现：

快速排序的实现有很多种，这里我给出了比较常规并且好理解的一种.低位，高位两个指针从左右两侧相向遍历list。当高位指针发现了小于基准数的元素时，便停止移动，此时开始移动低位指针，当低位指针发现了大于基准数的元素时，便停止移动，两指针交换元素值，如此循环，直至两指针相遇。

关于时间复杂度：

快速排序具体的运行时间和原始列表本身的排序状态有很大关系，理论上快排的时间复杂度是（nlogn），但是如果运气不好糟糕，比如说初始列表是[5,4,3,2,1]，那么根据上面的方法实现过程是什么样的呢，实现过程如下：

[5,4,3,2,1] -> [4,3,2,1,5] -> [3,2,1,4,5] -> [2,1,3,4,5] -> [1,2,3,4,5]

这样的排序实现过程很眼熟，跟最简单的冒泡排序的实现过程是完全相同的，所以说快排的最坏情况是冒泡排序，时间复杂度是（n ² ）

以上的实现较为通用，如果不使用python，而使用c++，java等其它编程语言实现，代码结构不会相差太多。我想到了一种比较贴合python语法特点，并且能较好的展示快排思想的实现方法。不同点是该方法时间在层递归中需要遍历2次列表，即复杂度为（2nlogn）

def qsort(lst):
    if not lst:
        return []
    return qsort([i for i in lst[1:] if i < lst[0]]) + [lst[0]] + qsort([i for i in lst[1:] if i > lst[0]])

本文永久更新链接地址 ： http://www.linuxidc.com/Linux/2018-01/150313.htm

以上所述就是小编给大家介绍的《Python实现快速排序》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

查看所有标签

猜你喜欢:

• JAVA实现常见排序算法 快速排序
• 用Python实现插入排序和选择排序
• 选择排序——Python实现
• PHP实现选择排序
• PHP实现冒泡排序
• 堆排序（php实现）

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。