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

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

【快速排序】：

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

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

分割过程如下：

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

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

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

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

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

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

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

【 implementation of quick sort 】

【 performance analysis】

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

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

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

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

查看所有标签

猜你喜欢:

• 算法与数据结构之递归算法
• Python 数据结构与算法 —— 初识算法
• js实现数据结构及算法之排序算法
• 数据结构和算法面试题系列—递归算法总结
• 数据结构和算法面试题系列—随机算法总结
• 数据结构与算法——常用排序算法及其Java实现

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