【 python 学习笔记 -- 数据结构与算法 】快速排序 Quick Sort

栏目: Python · 发布时间: 6年前

内容简介:【 python 学习笔记 -- 数据结构与算法 】快速排序 Quick Sort

【快速排序】:

利用递归算法, 首先选择一个基准值(pivot value),这里我们选列表的第一个值作为例。这个基准值的作用是协助列表的分割。

这个基准值在正序列表中的正确位置,我们称之为分割点(split point)。这个点用于将列表分成两个部分,然后再对每个部分做快速排序。

分割过程如下:

首先我们选择列表首个元素作为基准值,这个例子中即为54

【 python 学习笔记 -- 数据结构与算法 】快速排序 Quick Sort

接下来寻找分割点,在这个过程中同时会将小于基准值的元素移动到分割点左边,将大于基准值的元素移动到分割点右边。

为了完成上述操作,我们设置两个标记符leftmark和rightmark来追踪扫描各个元素的过程:

当leftmark位置的元素小于或等于基准值时,leftmark向右移动一个位置继续扫描;当leftmark位置的元素大于基准值时停止扫描。

同理,当rightmark位置的元素大于或等于基准值时,rightmark向左移动一个位置继续扫描;当rightmark位置的元素小于基准值时停止扫描。

停止扫描后,我们比较leftmark和rightmark的大小,如果rightmark<leftmark,rightmark就是基准值应该存放的位置,也就是分割点,我们将基准值交换到这个位置,返回分割点位置以便下一步递归操作;否则交换两个位置的元素。

【 python 学习笔记 -- 数据结构与算法 】快速排序 Quick Sort

将基准值存放到正确的位置后,我们看到现在的列表中,在基准值左侧的元素都小于基准值,在右侧的元素都大于基准值。所以我们以基准值为分割点,将列表分成左右两个子列表,再继续对子列表做快速排序,直到子列表的长度为0或1。

【 python 学习笔记 -- 数据结构与算法 】快速排序 Quick Sort

【 implementation of quick sort 】

【 python 学习笔记 -- 数据结构与算法 】快速排序 Quick Sort

【 performance analysis】

和归并 排序 相比,快速排序不需要多余的空间;但缺点是列表有可能不是平均分割的,将导致效率降低。

最坏的情况就是每次分割都是将列表分成一个长度为0的子列表和一个长度为n-1的子列表, 这种情况下,时间复杂度为O(n 2 )。

我们可以通过改变基准值的选取方法来减弱这种不平均分割的现象,一种方法是选取列表第一个元素,中间元素,最后一个元素中数值大小处于中间的那个值作为基准值。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

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

KK三部曲

KK三部曲

(美)凯文·凯利(Kevin Kelly) / 张行舟 / 中信出版社 / 2015-12-12 / 80.00元

《失控 全人类的*终命运和结局》这是《黑客帝国》主要演员的必读物之一,这本关于机器、系统、生物和社会的“大部头”,揭示了社会进化、特别是互联网发展的“先知预言”,从这本书里,人们可以窥探到SNS的今天和未来。 《失控 全人类的*终命运和结局》涉猎:天文、化学、生物、计算机、控制论、运筹学、社会学…… 同时又堪比《黑客帝国》中洞悉未来的“神谕”,正在兴起的“云计算”、“物联网”等都可以在......一起来看看 《KK三部曲》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具