基于满二叉树的原地快速排序

In-place quicksort based on full binary tree

介绍了一种基于满二叉树的原地快速排序算法。与经典快速排序算法相比,新算法每趟划分采用动态枢轴而不是静态枢轴,同时新算法利用满二叉树的特点计算下一趟划分的枢轴位置和元素范围,避免使用递归或开辟内存堆栈。实验表明,新算法的时间性能优于目前最好的原地排序—堆排序。原地快速排序二叉树的概念对排序算法的研究和改进具有很好的理论和实用参考价值。

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 inplace heapsort. The concept of in place quicksort binary tree has great theoretical and practical reference value to the research and improvement of sorting algorithm.