排序算法是最常见,最基础的算法,作者文集中记录了两种排序算法(插入排序,归并排序)
归并排序实现原理是切刀流,先中间切一刀,再在左右两边的中间切一刀,一刀一刀切下去,最后当子数组只剩一个元素时,将两个子数组采用分别访问的方法进行排序。
以上图片引用自:算法导论原书第三版
附上代码截图
那么这种算法效率如何呢?让它对一个元素个数为5000,由大到小的数组进行从小到大排序,来看一下运行时间
作者的另一篇文章附录了同等情况下插入排序花的时间,是0.9秒左右的时间,而归并排序只花了0.02秒的时间,由此可见算法效率差距之大。
github链接:https://github.com/zizhouwang/MergeSort