Python中怎么实现快速排序

今天就跟大家聊聊有关Python中怎么实现快速排序，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

归并排序的思路：分裂再合并，在合并的过程中完成排序

快速排序的思路：分拣再分裂

依据一个“中值”数据项，将数据表分成两半，小于中值的一半和大于中值的一半，然后每个部分递归地进行快速排序

如果希望左右两个部分的数据项个数相同，则应该找到数据表的中位数，然而找到中位数需要付出大量的计算开销，通常选择将第一个元素作为中值

快速排序代码思路：

• 设置第一个元素为中值，从第二个元素开始，分好两部分元素

• 将第一个元素（中值）放到合适的位置

递归三要素：

• 基本结束条件：数据表仅有一个元素，则代表已经排序好了

• 缩小规模：根据中值，将数据表分成两部分

• 调用自身：两部分分别调用自身进行快速排序

将数据表分成两部分的方法：

设置左右标号（left和right），将第一个元素作为中值

• 左标（left）从第二个元素开始向右移动，碰到比中值大的则停止

• 右标（right）从末尾开始向左移动，碰到比中值小的则停止

• 判断左标是否已经超过了右标

• 若没有，交换左右标所指的数据

• 若left>right则停止移动，此时right位置就是中值位置，将中值交换到right处
  

完成分裂的过程其实也就完成了排序的一部分工作，由于while循环要执行结束后才会继续后面的程序（即left和right要停止才会结束），故要先判断是否已经 left>right

快速排序过程分为两部分：分裂和移动

• 分裂过程：若两部分规模相当则时间复杂度O(logn)

• 移动过程：时间复杂度O(n)

综上所述，快速排序的时间复杂度O(nlogn)

并且快速排序运行过程中不需要额外的存储空间

但是，如果运气不好，中值所在的分裂点过于偏离中部，造成左右两部分数量不平衡，极端情况下，有一部分始终没有数据，这样时间复杂度就退化到了O(n^2)

看完上述内容，你们对Python中怎么实现快速排序有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注亿速云行业资讯频道，感谢大家的支持。