归并排序算法解析

对于基本的排序算法,前面介绍了冒泡,选择,插入和希尔(增强版本的插入), 还有快速排序,现在还剩下最后一种基本的排序算法,那就是归并排序。归并排序像快速排序一样采用递归算法对列表进行分而治之,每次平均一分为二,分到只有一个元素为止。如果列表为空或只有一个元素时,那么从定义上来说它就是有序的; 当然归并排序的拆分最终不会有空列表的情况。拆分成一个个元素后再往回归并,归并是指将两个较小的有序列表归并为一个有序列表的过程。比如说两个单元素列表归并为两个元素的有序列表,两个双元素的列表归并为四个元素的有充列表,不断往上进行,最后形成一个有序的完整列表。

从维基百科的词条 Merge sort 找到下图,很深刻的描绘了归并排序的完整过程,红色箭头拆分,绿色箭头归并 阅读全文 >>

类别: Algorithm. 标签: , . 阅读(35). 评论(0) »

希尔(Shell) 排序 - 增强版插入排序算法

前面讲过的几种排序多是以排序逻辑来命名的,例如冒泡,选择和插入排序,以及其他如归并排序,当然还有觉得自己足够牛 X 快速排序命名。而本文要学习的排序算法叫做希尔排序是以其设计者 Donlad Shell 命令的排序算法,该算法在 1959 年公布,能以作者来命名的算法应该是很不错的,令设计者引以为傲的。最初写出冒泡和选择排序的就没以作者来命名,可能不好意说,更可能是公共思维。

那么什么是希尔排序呢?它实际上是插入排序算法的增强版本,又称递减增量排序算法。它对待排序列表进行间隔式分段插入处理,从而总体上减少了元素的移动次数而达到性能的大大提升。那么理解希尔排序之前一定要先了解插入排序。那么为什么说希尔排序既是递减又是增量呢? 阅读全文 >>

类别: Algorithm. 标签: , . 阅读(44). 评论(0) »