程序设计导论：Python语言实践

4.2.3　归并排序算法

为了开发一个快速排序方法，我们使用递归（具体参见二分查找算法）和一种分而治之（divide-and-conquer）的方法来设计算法。希望每一个程序员都能理解这种算法。该算法是指解决问题的一种方法或思想，即把问题分解为独立的部分，然后分别独立解决问题，最后使用部分问题的解决方案形成整个问题的解决方案。为了使用这种策略排序一个可比较键值的数组，我们把数组分解成两部分，分别独立排序这两部分，然后把结果合并为一个完整数组。这种算法称为归并排序（mergesort）算法。归并排序过程演示如图4-2-8所示。

图4-2-8　归并排序过程演示

处理一个给定数组的连续子数组时，我们使用a[lo，hi）表示a[lo]，a[lo+1]，…，a[hi-1]（采用二分查找算法中所使用的相同规则表示不包含a[hi]的半开区间）。我们使用如下递归策略对a[lo，hi）进行排序：

·基本情况：如果子数组的长度为0或1，则排序完毕。

·递归步骤：否则，计算mid=（hi+lo）/2，（递归地）排序两个子数组a[lo，mid）和a[mid，hi)，然后合并它们。

程序4.2.6（merge.py）是这种算法的一种实现。数组元素通过递归调用后的代码重新排列，合并通过递归调用排序后数组的两个部分。通常，理解归并过程最简单的方法是研究归并过程中数组内容的跟踪信息。代码包含索引i（前半部分）和索引j（后半部分），第三个索引k用于存储结果的辅助数组aux[]。归并实现是一个单循环，把aux[k]设置为a[i]或a[j]（然后递增k和值的索引）。如果i到达子数组的末端，则aux[k]设置为a[j]。如果j到达子数组的末端，则aux[k]设置为a[i]。否则，aux[k]设置为a[i]或a[j]中的较小值。当两个子数组中的所有元素都拷贝到aux[]后，排序好的数组被拷贝回原始数组。请读者务必花点时间仔细研究一下如图4-2-9所示的跟踪信息，以更好地理解代码总是可以正确合并两个排序子数组，从而实现排序整个数组的原理。 ...