数据结构与算法（19）——快速排序
2021-04-10 08:28
标签：help 左右 交换 img 个数 col highlight mamicode 根据 思想：依据一个中值数据项，把数据表分成两半：小于中值的一半和大于中值的一半，然后把每部分分别进行快速排序(递归)。 其中递归条件： 基本结束条件：数据表仅有一个数据项 缩小规模：根据中值，将数据表分为两半，最好的情况是相等规模的两半 调用自身：将两半分别调用自身进行排序（排序基本操作在分裂过程中） 快速排序的图解过程： 快排包括分裂和移动两个部分：分裂的时间服大肚是O(n) ,移动O(log n)，总的时间复杂度为O(nlog n)，且不需要额外存储空间。 但是快排也有缺点，在极端情况，如果不幸，中值所在的分裂点过于偏离中部，造成左右两部分数据不平衡，且在有一部分始终没有数据的话，这样时间复杂度就退化到O(n^2)。 注意：中值的选取对排序十分重要，因此需要有先验知识对数据的特性选取合适的中值。 数据结构与算法（19）——快速排序 标签：help 左右 交换 img 个数 col highlight mamicode 根据 原文地址：https://www.cnblogs.com/yeshengCqupt/p/13368676.html
def partition(alist, first, last):
pivotvalue = alist[first] #以第一个数作为中值
leftmark = first + 1
rightmark = last
done = False
while not done:
while leftmark = pivotvalue and rightmark >= leftmark: #左移动右标
rightmark -= 1
if rightmark