首页 | 本学科首页   官方微博 | 高级检索  
     

深度优先稳定原地归并排序的高效算法
引用本文:白宇,郭显娥. 深度优先稳定原地归并排序的高效算法[J]. 计算机应用, 2013, 33(4): 1039-1042. DOI: 10.3724/SP.J.1087.2013.01039
作者姓名:白宇  郭显娥
作者单位:山西大同大学 数学与计算机科学学院,山西 大同 037009
摘    要:基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试。实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51%的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题。

关 键 词:归并排序  原地排序  稳定排序  分治策略  深度优先  
收稿时间:2012-10-08
修稿时间:2012-11-13

Efficient algorithm of depth-first stable in-place merge sort
BAI Yu , GUO Xian'e. Efficient algorithm of depth-first stable in-place merge sort[J]. Journal of Computer Applications, 2013, 33(4): 1039-1042. DOI: 10.3724/SP.J.1087.2013.01039
Authors:BAI Yu    GUO Xian'e
Affiliation:School of Mathematics and Computer Science, Shanxi Datong University, Datong Shanxi 037009, China
Abstract:Based on divide-and-conquer strategy, the depth-first method was used to design an algorithm of stable in-place merge sort for linear array. Its time complexity was O(n lb n), its auxiliary space complexity was O(1), its space complexity of recursion stack was O(lb n), and the algorithm analysis and experimental testing were completed. By analyzing the experimental results, its efficiency compared with stable in-place merge sort algorithm in the STL has a 67.51% improvement, which solves the high time complexity or high space complexity problem of stable sorting algorithm.
Keywords:merge sort   in-place sort   stable sort   divide and conquer strategy   depth-first
本文献已被 万方数据 等数据库收录!
点击此处可从《计算机应用》浏览原始摘要信息
点击此处可从《计算机应用》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号