这个活动在说什么?

在已排序的数据中寻找信息会比较容易,比如电话薄、字典和书籍索引都是用字母来排序的。试想如果它们经过这样的排序,我们要找相关信息时就会麻烦很多。若是将一串数字(例如一些支出)由小到大进行排序,就可以轻易的在排序的两端找到最大和最小的数字,如果有数字重复的话那也是一目了然,因为它们一定会被排在一起。

计算机通常会花很多时间将数据进行排序,所以,找到一个快速又有效率的排序方法一直是计算机科学家的重要工作之一。一些比较慢的方法如插入排序法、选择排序法和冒泡排序法在特定的情况下还是很有用的,但是在待排序的物件群规模很大的情况下,就需要用快速排序法、合并排序法这些速度较快的排序法。举例来说:如果有十万个资料要排序,快速排序法大概比选择排序法要快上2000倍。如果总数上升到一百万份资料(很多网站拥有上百万的访客量,甚至在一张照片上也有超过一百万的像素要处理);选择不同的算法可能会造成一秒钟和5个小时的处理时间的差异。而且不只是时间的延长让人无法忍受,还有其他的成本,比如要消耗20000倍的电力(浪费电力不止有悖于环保,而且也会减少可携式电池的寿命)。所以,选择合适的算法非常重要。

快速排序法用到了一种方法叫做分治法。在快速排序法中,我们不断的把物件群组分成较小的两个群组,然后再对这些较小的部分执行快速排序法。最后,整个物件群被反复的分割,直到它们小到可以被简易的排序。在快速排序法中,物件群被分割到只剩下一个物件——只有一个物件,那还需要排序吗?虽然这些步骤看似很复杂,但在实际运行中,快速排序法却戏剧性地比其他方法更高效。分治法所使用的这种观念称为递归(Recursion),就是算法里会反复呼叫自己来解决问题。这听起来很奇怪,但实际上非常管用。

results matching ""

    No results matching ""