【排序算法】—— 更快的排序

【排序算法】—— 更快的排序

在上篇【Python 排序算法】—— 基本排序算法中,介绍的 3 中排序算法都拥有 $O(n^2)$ 的运行时间。这些排序算法还有几种变体,其中的稍微快一些。但是,在最坏的情况和平均情况下,它们的性能还是 $O(n^2)$。然而,我们可以利用一些复杂度为 $O(nlogn)$ 的更好的算法。这些更好的算法的秘诀就是,采用分而治之$(divide-and-conquer)$的策略。也就是说,每一个算法都找了一种方法,将列表分解为更小的子列表。随后,这些子列表在递归地排序。理想情况下,如果这些子列表的复杂度为 $log(n)$,而重新排列每一个子列表中的数据所需的工作量为 $n$,那么,这样的排序算法总的复杂度就是 $O(nlogn)$。

阅读更多
【排序算法】—— 基本排序算法
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×