学习活动单:分治法(Divide and Conquer)

快速排序法(Quicksort)

快速排序法比选择排序法还要迅速,对于大型的表单则更加明显。事实上,这是目前最好的排序方法之一。以下是快速排序法执行的方法。

从全部的物件中随机挑选出一个物件,然后把它放在天平的一端。

然后将它与其他剩余的物件——比较,将较轻的放在左侧,随机选出的物件放在中间,较重的则放在右侧。(有可能在结束时,两边物件的数量不一样)

选择其中一侧,将该侧所有物件重复上面的步骤。再将另一侧的物件也做一样的处理。

记得记住一开始选择的物件要保持在中间。

在剩余的物件里一直重复这些步骤,直到每一组都只剩一个物件。一旦所有物件组都只剩一个物件,所有物件便会被分成由最轻到最重的顺序。

整个过程需要比较几次?

我们可以发现,快速排序法比选择排序法更有效率,除非你一开始就选择到最轻或者最重的那个物件。如果你够幸运,一开始就选到中间的重量,相较于需要28次才能完成的选择排序法,快速排序法能以14次比较来完成排序。在任何情况下,快速排序法都不会比选择排序法差,甚至更快速!

高手挑战:假如快速排序法意外的一直选到最轻的物件,则需要几次比较来获得结果?

活动变化与延伸

排序还有很多种不同的方法,你还可以用以下这些方法来试着把重量排序:

插入排序法是从尚未排序的物件群中挑出一个物件,把它插入已排序物件群中正确的位置(见下图)。随着一次次的“挑出物件->插入已排序物件群”,未排序物件群的规模越来越小,而已排序物件群的规模越来越大,直到所有物件都排序完成。我们玩扑克牌时就常常利用这个方法来理牌。

冒泡排序法是一次又一次从头到尾检查整个物件群,如果两个相邻的物件顺序不对就把它们交换,整个物件群检查完之后,再重头开始检查一次。如果没有任何物件在检查名单时被交换,就表示排序完成了。这个方法并不是很有效率,但是对某些人来说这种方法较容易理解。

合并排序法是另一种利用“分治法”来排序物件的方法。首先,将名单随机分成大小相同的两个物组(总数为奇数个时,则分成大小相近的两份)。两个物组都要分别做排序,最后再将两个物组合并。合并两个群组的做法相当容易——比较两个群组最轻的物件,把较轻的那个跳出来放入排序群组中。在下图中,两组的最前面的物件分别是40和60克,所以下一个就把40克的物件挑出来放入已排序群组中。那么,最开始分成两个群组以后,要怎么分别排序呢?简单——用合并排序法!最后,所有的群组会被分成只剩下一个物件,所以你不需要担心永远分不完。

results matching ""

    No results matching ""