归并排序
归并排序是建立在归并操作（Merging）上的一种排序方法，它是采用分治法的一个非常典型的应用。归并是指将两个或两个以上的有序表合并成一个新的更大的有序表，归并排序则是递归的先将待排序列分割成n个序列，然后从最小的有序序列（只含一个元素）开始不断调用归并操作进行合并直到最后都合并成一个大的完整的有序表为止。
归并排序的C/C++代码实现：
- void merge(int array[], int low, int m, int high)
- {
- int i, j, k;
- static int temp[ARRAY_SIZE];
- for (i = low, j = m + 1, k = 0; k < high - low + 1; ++k) {
- if (i > m) {
- temp[k] = array[j++];
- continue;
- }
- if (j > high) {
- temp[k] = array[i++];
- continue;
- }
- temp[k] = array[i] < array[j] ? array[i++] : array[j++];
- }
- for (k = 0; k < high - low + 1; ++k)
- array[low+k] = temp[k];
- }
- void merge_sort(int sort_array[], int low, int high)
- {
- if (low < high) {
- int i = (low + high) / 2;
- merge_sort(sort_array, low, i);
- merge_sort(sort_array, i + 1, high);
- merge(sort_array, low, i, high);
- }
- }
归并排序的时间复杂度是O(n㏒n)，并且和输入数据无关。这点和堆排序一样，是归并排序最吸引人的特性之一（虽然这有时候也可能成为缺点，如在某些特殊的情况下（如已基本有序）连简单的排序方法运行时间也可以为线性，但归并和堆还是只能为O(n㏒n)）。
归并排序还有一个特性是它的执行过程中基本是按顺序访问数据的，这点在某些情况下会很重要。例如，链表排序中只可以按顺序访问数据，这时就可以选用归并排序。
归并排序主要的缺点就是需要与n成比例的额外内存空间。虽然可以克服这个障碍，但通常比较复杂而且花费很大，一般并不值得这么做，特别是还可以选择堆排序时。
归并排序是一种稳定的排序方法，与归并排序竞争的算法，如快速排序和堆排序，是不稳定的。虽然使这些算法也变成稳定有很多方法，但需要额外的内存空间。因此当稳定性是基本的要求时，归并排序中需要额外内存空间这个缺点就变得没那么重要了。
竞争的排序算法
如上所述，和归并排序竞争的是快速排序和堆排序。归并排序和堆排序的时间复杂度一样，它内部循环的长度在快速排序和堆排序之间，因此当运行速度很重要（去堆排序），不能有最坏的运行情况（去快速排序），又有足够的空间可以使用时，可以考虑使用归并排序。
文章若无注明则属原创，转载请以链接形式注明出处。
本文地址：http://www.juliuschen.com/archives/13.html
