06 2009 档案

     摘要: 引子:这篇文章以前写过,最近复习排序算法,觉得以前的代码还可以改进,因此有了此文。

归并排序算法以O(NlogN)最坏情形运行时间运行,而所使用的比较次数几乎是最优的。

该算法中最基本的操作是合并两个已排序的表,这只需要线性的时间,但同时需要分配一个临时数组来暂存数据。

归并排序算法可以用递归的形式实现,形式简洁易懂。如果N=1,则只有一个元素需要排序,我们可以什么都不做;否则,递归地将前半部分数据和后半部分数据各自归并排序,然后合并这两个部分。

归并排序算法也可以用非递归的形式实现,稍微难理解一点。它刚好是递归分治算法的逆向思维形式,在使用递归分治算法时,程序员只需考虑将一个大问题分成若干个形式相同的小问题,和解的边界条件,具体如何解决这些小问题是由计算机自动完成的;而非递归形式要求程序员从最基本的情况出发,即从解决小问题出发,一步步扩展到大问题。

我这里两种形式都给出。

另外,很多人在写递归形式的归并排序算法时,临时数组是在MergeSort函数中分配的,这使得在  阅读全文

posted @ 2009-06-09 08:25 梦想飞扬 阅读(7623) | 评论 (4)  编辑 |