python 快速排序_算法 | 快速排序原理及python实现

发布于:2021-06-21 04:38:49

快速排序,简称快排,基本上被认为是相同数量级的所有排序算法中,*均性能最好的。今天就学*一下如何实现,希望对你的学*或工作有参考价值



原理:


对于给定的记录,选择一个基准数(为了方便通常选择第一个数),通过一趟排序后,将原序列分为两部分,使得前面的比后面的小,然后再依次对前后进行拆分进行快速排序,递归该过程,直到序列中所有记录均有序。


这是典型的分治思想,或者叫分治法,把问题分为一个个的小部分来分别解决,再把结果组合起来。


步骤:

1选取基准数取第一个元素 p,使p 元素归位。2分隔列表一趟排序之后,列表被 p 分成两部分,左边的都比 p 小,右边的都比 p 大。3递归对左边的与右边的列表分别递归再次进行排序,递归到最底部的判断条件是序列的大小是零或一,此时该数列已经有序。


快速排序的思想还是比较简单的,也有多种实现思路。


代码:


下面就以序列[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]来看看下面这种实现代码:


def quick_sort(li, left, right): ? ?if left < right: ? ? ? ?mid = partition(li, left, right) ? ? ? ?quick_sort(li, left, mid - 1) ? ? ? ?quick_sort(li, mid + 1, right)def partition(li, left, right): ? ?tmp = li[left] ? ?while left < right: ? ? ? ?while left < right and li[right] >= tmp: ? ? ? ? ? ?right -= 1 ? ? ? ?li[left] = li[right] ? ? ? ?while left < right and li[left] <= tmp: ? ? ? ? ? ?left += 1 ? ? ? ?li[right] = li[left] ? ?li[left] = tmpreturn left
lis = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]quick_sort(lis, 0, len(lis) - 1)print(lis)

运行结果:



说明:


    先把 基数 3 取出,left 下标左边为 0,right 下标右边取 14

    先把 right 下标对应的数取出与基数 3 比较,如果比它大则不动,并把right 下标往左移动一格,从 right 处取数继续比较;

    如果比基数小,则将该数放到左边 li[left]处,并把 left 下标往右移动一格,从left 处取数继续比较

    当基数 3 归位,处于列表中间

    左右两边的子列表通过递归继续


特点及性能:


快速排序是在冒泡排序的基础上改进而来的,冒泡排序每次只能交换相邻的两个元素,而快速排序是跳跃式的交换,交换的距离很大,因此总的比较和交换次数少了很多,速度也快很多。



*均时间复杂度为:O(nlogn)


*均空间复杂度为:O(logn)


快速排序的最坏运行情况是 O(n?),比如说顺序数列的快排。


但它的*摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。


所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。


以上~


?
END?

相关推荐

最新更新

猜你喜欢