建设部网站江苏金安,合肥网站开发 合肥网站优化,寻找好项目网,怎么在工商局网站做股东变更原文#xff1a;https://stackabuse.com/quicksort-in-python/作者#xff1a;Marcus Sanatan译者#xff1a;老齐欢迎在 bilibili 搜索 freeCodeCamp 官方账号或者直接访问 https://space.bilibili.com/335505768 观看我们的技术视频介绍快速排序是一种流行的排序算法https://stackabuse.com/quicksort-in-python/作者Marcus Sanatan译者老齐欢迎在 bilibili 搜索 freeCodeCamp 官方账号或者直接访问 https://space.bilibili.com/335505768 观看我们的技术视频介绍快速排序是一种流行的排序算法经常与归并排序一起使用。快速排序是一个高效的排序算法平均复杂度为 O(nlogn)。它受欢迎的部分原因还在于易于实施。在本文中我们将先使用整数集合演示快速排序算法然后会用自定义对象深入探讨这种算法的实现方式。在分治法、原地排序和非稳定排序中都有快速排序算法。- 在分治法中对大数组使用递归进行排序之前使用快速排序算法将数组拆分为更小的数组直到最后得到一个空数组或只有一个元素的数组。- 在原地排序中快速排序不创建数组的任何副本它在内存中完成所有的操作。- 稳定排序指相同的值在数组中的顺序也是相同的非稳定的排序算法不能保证这一点只能说这样的顺序当然有可能出现但不能保证。这在针对对象排序而不是对基本类型排序时变得很重要。例如假设有几个自定义的 Person 类实例具有相同的 age即 21 岁的 Dave 和 21 岁的 Mike。如果要对包含 Dave 和 Mike 的集合使用快速排序法按年龄排序则无法保证每次运行算法时 Dave 都会出现在 Mike 之前反之亦然。快速排序快速排序算法的执行流程如下- 将集合分成两个(大致)相等的部分取一个伪随机元素并将其用作主元(注“主元”原文中 pivot在多数介绍快速排序算法的中文资料中并不对齐单独命名只简单说成是“分割点”即划分集合的元素但本文作者使用了 pivot 这个词来表示“分割点”译者认为很便于理解和表述并将其翻译为“主元”)。- 小于主元的元素将移动到其左侧大于主元的元素将移动到其的右侧。- 分别对于主元左侧和右侧的元素重复此上述直到对整个数组完成排序。当我们将某个元素描述为比另一个元素“大”或“小”时并不一定意味着这些元素是整数我们可以自定义对象并根据选择的任何属性进行排序。假设有一个自定义类 Person每个实例都有 name 和 age 属性我们可以按姓名(词典顺序)或按年龄(升序或降序)进行排序。快速排序算法的原理对于快速排序算法很多时候数组是不能等分的这是因为整个过程取决于如何选择主元。我们需要选择一个主元使其比一半的元素大比另一半的元素小。尽管这个过程看起来很直观但很难做到。想一想如何为数组选择合适的主元关于这个问题的解决方法在快速排序算法的发展史上有过好多种。如果随机选择是行不通的因为这不能保障主元是合适的随机选择的代价会非常“昂贵”。此外还曾经有人提出从中间选择一个元元素或者选择第一个、或者后半部分中间的设置用更复杂的递归公式选择等等。最直接的最简单的方法是选择第一个(或最后一个)元素作为主元具有讽刺意味的是这会导致快速排序法对已经排序(或几乎排序了)的数组执行效果非常糟糕。但是大多数人还是用这种方法来实现快速排序算法因为它很简单而且这种选择主元的方式是一种非常有效的操作(我们需要重复执行)这也正是我们下面要做的。既然我们选择了一个主元接下来该用它做些什么同样有几种方法可以处理各个分区。我们要设置三个指针有一个指向主元另外两个分别指向“较小”元素和“较大”元素。然后移动元素使所有小于主元的元素都在左侧而所有较大的元素都在右侧。更小或更大的元素不一定会被排序我们只希望它们位于主元的适当的一侧。然后用递归方法遍历主元的左侧和右侧。一步一步来看看我们计划要做的事情从而理解以上所说的快速排序算法的执行过程。使用下面显示的数组我们选择了第一个元素作为主元(29)low 表示指向较小元素的指针最右边的 high 表示指向较大元素的指针。- 29 是第一主元low 指向 99high 指向 4429 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (high)- high 从右向左移动直到找到一个小于主元的值29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44- 现在 high 指向了 21它是一个比主元小的元素我们想在数组的开头附近找到一个值使之可以用于与 21 交换。用一个比主元还小的值交换是没有意义的所以如果 low 指向一个更小的元素我们试着找到一个更大的元素。- 将 low 变量向右移动直到找到一个大于主元的元素。幸运的是 low 已经定位在 99它就比主元大- 交换 high 和 low 指向的元素29 | 21 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,99 (high),44- 在我们这样做之后就将 high 继续向左移动将 low 向右边移动(21 和 99 现在所处的位置是正确的)。- 再次将 high 向左移动下一个数字就是小于主元的 12。- 现在我们通过将 low 向右移动来找一个大于主元的值就是 41 了它是第一个这样的值不断重复上述过程直到 low 指针和 high 指针最终在某个元素相遇29 | 21,27,12,19,28 (low/high),44,78,87,66,31,76,58,88,83,97,41,99,44- 不再使用 29 作为主元了所以剩下唯一要做的就是交换主元和 high 所指元素 28然后我们就完成了这个递归步骤28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,41,99,44如你所见我们已经让小于 29 的所有值现在都在 29 的左侧大于 29 的所有值都在右侧。然后算法对 28、21、27、12、19(左侧)集合和44、78、87、66、31、76、58、88、83、97、41、99、44(右侧)集合执行相同的操作。实现对数组排序快速排序是一种自然递归算法将输入数组分成较小的数组将元素移动到主元的适当一侧然后重复。让我们来看看几个递归调用- 当第一次调用算法时我们考虑所有的元素——从索引 0 到 n-1其中 n 是数组中的元素数量。- 如果主元最终位于位置 k那么我们将对从 0 到 k-1 和从 k1 到 n-1 的元素重复该过程。- 在将元素从 k1 排到 n-1 时当前主元将在某个位置 p 结束。然后我们将元素从 k1 序到 p-1从 p1 排序到 n-1依此类推。也就是说我们将使用两个函数partition() 和 quick_sort()。quick_sort() 函数将首先用 partition() 函数对集合分组然后在每组上递归调用自己。下面从 partition() 函数开始def partition(array, start, end): pivot array[start] low start 1 high end while True: # If the current value were looking at is larger than the pivot # its in the right place (right side of pivot) and we can move left, # to the next element. # We also need to make sure we havent surpassed the low pointer, since that # indicates we have already moved all the elements to their correct side of the pivot while low high and array[high] pivot: high high - 1 # Opposite process of the one above while low high and array[low] pivot: low low 1 # We either found a value for both high and low that is out of order # or low is higher than high, in which case we exit the loop if low high: array[low], array[high] array[high], array[low] # The loop continues else: # We exit out of the loop break array[start], array[high] array[high], array[start] return high最后让我们实现 quick_sort() 函数def quick_sort(array, start, end): if start end: return p partition(array, start, end) quick_sort(array, start, p-1) quick_sort(array, p1, end)有了这两个函数就可以对一个简单的数组执行 quick_sort()array [29,99,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44]quick_sort(array, 0, len(array) - 1)print(array)输出[12, 19, 21, 27, 28, 29, 31, 41, 44, 44, 58, 66, 76, 78, 83, 87, 88, 97, 99]由于此算法是非稳定的所以不能保证这两个 44 的顺序总是这样的也许会交换 —— 虽然这在整数数组中意义不大。对自定义对象进行排序有几种方法可以重写此算法以便在 Python 中对自定义对象进行排序。一种非常典型的 Python 方法是实现给定类的比较运算符这意味着我们实际上不需要更改算法实现因为 、、 等也可以应用于类对象。另一个选择是以参数的方式给函数传入一个比较函数用这个方法来执行对象的实际比较。用这种方式重写算法函数以用于自定义对象是相当简单的。但是请记住算法并不稳定。让我们从 Person 类开始class Person: def __init__(self, name, age): self.name name self.age age def __str__(self): return self.name这是一个非常基本的类只有两个属性name 和 age。我们希望使用 age 作为排序键这将通过为排序算法提供自定义 lambda 函数来实现。但首先让我们看看如何在函数中实现算法。我们没有直接使用 或 运算符进行比较而是在函数中来判断哪个 Person 实例的年龄更高def partition(array, start, end, compare_func): pivot array[start] low start 1 high end while True: while low high and compare_fun(array[high], pivot): high high - 1 while low high and not compare_fun(array[low], pivot): low low 1 if low high: array[low], array[high] array[high], array[low] else: break array[start], array[high] array[high], array[start] return highdef quick_sort(array, start, end, compare_func): if start end: return p partition(array, start, end, compare_func) quick_sort(array, start, p-1, compare_func) quick_sort(array, p1, end, compare_func)现在让我们对这些实例对象的集合进行排序。你可以看到在 quick_sort 函数的参数中有 lambda 函数它会对 age 属性的值进行实际的比较:p1 Person(Dave, 21)p2 Person(Jane, 58)p3 Person(Matthew, 43)p4 Person(Mike, 21)p5 Person(Tim, 10)array [p1,p2,p3,p4,p5]quick_sort(array, 0, len(array) - 1, lambda x, y: x.age for person in array: print(person)输出是TimDaveMikeMatthewJane通过这种方式实现算法只要提供适当的比较函数它就可以用于我们选择的任何自定义对象。优化快速排序算法考虑到快速排序独立地对给定数组的“一半”进行排序那么它就非常便于实现并行计算。我们可以用一个单独的线程对数组的每个“一半”进行排序理想情况下可以将排序所需的时间减半。但是如果我们在选择主元时特别不走运快速排序法可能会递归太深此时即使用并行计算其效率也不如归并排序。对小数组进行排序时建议使用非递归算法。即使是像插入排序这样的简单操作在小数组上也比快速排序更有效。因此理想情况下我们可以检查排序对象是否只有少量元素(大多数建议是 10 个或更少)如果是这样就用插入排序代替。快速排序的一个流行变体是多主元快速排序它使用 n-1 个主元将原始数组分解为 n 个较小的数组。然而大多数情况下只使用两个主元而不是更多。有趣的事实Java 7 的排序实现中使用了双主元快速排序针对较小数组的则是插入排序。结论正如我们前面提到的快速排序的效率很大程度上取决于主元的选择——它可以成就或突破算法时间(和堆栈空间)的复杂度。在使用自定义对象时算法的非稳定性也是一个潜在的问题。然而尽管如此快速排序的平均时间复杂度 O(nlogn) 和相对低的内存使用、简单的实现方法使它成为一种非常有效和流行的算法。推荐阅读30 行 Python 代码实现 Twitch 主播上线实时通知从软件工程专业思考到的大前端技术栈非营利组织 freeCodeCamp.org 自 2014 年成立以来以“帮助人们免费学习编程”为使命创建了大量免费的编程教程包括交互式课程、视频课程、文章等。线下开发者社区遍布 160 多个国家、2000 多个城市。我们正在帮助全球数百万人学习编程希望让世界上每个人都有机会获得免费的优质的编程教育资源成为开发者或者运用编程去解决问题。你也想成为 freeCodeCamp 社区的贡献者吗欢迎了解 招募丨freeCodeCamp 翻译计划。点击【在看】与朋友交流?
