折腾来折腾去

pikipity的blog

Algorithms: Design and Analysis Part 1 – Programming Questions (Week1 and Week 2 Summary)

这里主要记录下来在 “Algorithms: Design and Analysis Part 1” 的Programming Questions 中的算法、实现和作业中的困难。我是用的是 Python。Week 1 Programming Question 在这里。Week 2 Programming Question 在这里。由于 Week 1 和 Week 2 都是讨论排序问题,所以在这里做下小结-比较一下之前实现过的方法的运行时间。

具体代码可以到这里查看和下载。非常简单的比较了之前在 Week 1 和 Week 2 实现过的4排序方法和 Python 自带函数 sorted 对同一个数列运行1000次的时间。结果如下:

  1. Week 1 的 Merge Sort 方法:113.557s
  2. Week 2 的 QuickSort(第一个元素做 Pivot):93.443s
  3. Week 2 的 QuickSort(最后一个元素做 Pivot):95.201s
  4. Week 3 的 QuickSort(中间元素做Pivot):94.088s
  5. sorted 函数:19.413s

sorted函数使用 “Timsort” 方法,而且是使用 C 编写的,所以速度远远快于用 Python 编写的其他算法。所以想要速度快,还是用 C 比较好。



Comments