计算机应用 ›› 2013, Vol. 33 ›› Issue (04): 1039-1042.DOI: 10.3724/SP.J.1087.2013.01039

• 先进计算 • 上一篇    下一篇

深度优先稳定原地归并排序的高效算法

白宇,郭显娥   

  1. 山西大同大学 数学与计算机科学学院,山西 大同 037009
  • 收稿日期:2012-10-08 修回日期:2012-11-13 出版日期:2013-04-01 发布日期:2013-04-23
  • 通讯作者: 白宇
  • 作者简介:白宇(1976-),男,山西大同人,讲师,硕士,主要研究方向:图论算法、并行算法、云计算;郭显娥(1964-),女,山西大同人,教授,主要研究方向:概念格、数据挖掘、知识发现。

Efficient algorithm of depth-first stable in-place merge sort

BAI Yu,GUO Xiane   

  1. School of Mathematics and Computer Science, Shanxi Datong University, Datong Shanxi 037009, China
  • Received:2012-10-08 Revised:2012-11-13 Online:2013-04-01 Published:2013-04-23
  • Contact: BAI Yu

摘要: 基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试。实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51%的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题。

关键词: 归并排序, 原地排序, 稳定排序, 分治策略, 深度优先

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.

Key words: merge sort, in-place sort, stable sort, divide and conquer strategy, depth-first

中图分类号: