| 基于满二叉树的原地快速排序 |
| |
| 引用本文： | 范时平.基于满二叉树的原地快速排序[J].重庆邮电学院学报(自然科学版),2006,18(6):781-783. |
| |
| 作者姓名： | 范时平 |
| |
| 作者单位： | 重庆邮电大学软件学院,重庆400065 |
| |
| 基金项目： | 重庆市教委基金（2005.78）;重庆邮电大学青年教师基金（2005-18） |
| |
| 摘 要： | 介绍了一种基于满二叉树的原地快速排序算法。与经典快速排序算法相比，新算法每趟划分采用动态枢轴而不是静态枢轴，同时新算法利用满二叉树的特点计算下一趟划分的枢轴位置和元素范围，避免使用递归或开辟内存堆栈。实验表明，新算法的时间性能优于目前最好的原地排序一堆排序。原地快速排序二叉树的概念对排序算法的研究和改进具有很好的理论和实用参考价值。
|
| 关 键 词： | 原地 满二又树 快速排序 原地快速排序二叉树 |
| 文章编号： | 1004-5694（2006）06-0781-03 |
| 收稿时间： | 2006-09-13 |
| 修稿时间： | 2006-10-20 |
In-place quicksort based on full binary tree |
| |
| FAN Shi ping.In-place quicksort based on full binary tree[J].Journal of Chongqing University of Posts and Telecommunications(Natural Sciences Edition),2006,18(6):781-783. |
| |
| Authors: | FAN Shi ping |
| |
| Institution: | College of Software, Chongqi g University of Poses and Telecommunications, Chongqing 400065,P. R. China |
| |
| Abstract: | In-place quicksort based on full binary tree is introduced.The new algorithm has two main differences from classic quicksort.The first is that the pivot of the new algorithm is dynamic but the classic's is static in every partition.The second is that the new algorithm computes the scope and the pivot of the next partition,so it can avoid using recursive or using stack.The experiment certifies that the time property of the new algorithm is superior to that of the best in-place heapsort.The concept of in-place quicksort binary tree has great theoretical and practical reference value to the research and improvement of sorting algorithm. |
| |
| Keywords: | in-place full binary tree quicksort in-place quicksort binary tree |
| 本文献已被 CNKI 维普 等数据库收录！ |
