学习活动单：分治法（Divide and Conquer）

快速排序法（Quicksort）

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

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

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

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

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

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

整个过程需要比较几次？

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

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

活动变化与延伸

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

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

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

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