插入排序和希尔排序执行效率的比较

现在晚上睡觉之前都会看一会讲算法的书。因为大三的时候,没有怎么好好学习过算法,而之前C/C++也一直没认真上过课,所以这次看书也像新学一样从头开始看。最先讲的算法肯定是排序算法。冒泡算法还是一看就明白了,插入也能看明白,但希尔算法看了两个晚上也没能搞明白。今天终于通过代码实现了。希尔算法也是基于插入排序算法的,但比简单的插入排序效率要高很多。当待排序数目更多时,效率高得更明显。以下是完整C源代码:

 

去除代码注释可以查看每次排序后的结果。

当数组规模为10时,希尔排序数据移动次数只有插入排序的一半;当数组规模为100时,插入排序需要移动次数大概是希尔排序的5倍;当数组规模为100时,插入排序需要移动次数大概是希尔排序的30倍。

(原博客发布时间:2011-10-27 14:03:51)

发表评论