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

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

如何在快速排序算法中定义“趟”的概念

<正> 快速排序算法是在实际中应用十分广泛的一种内排序方法,因此我们在教学过程中通常向学生介绍得比较详细。但国内的教科书目前通常将重点放在对子表进行划分过程的介绍上,而对整个排序过程的介释显得不够深入,同时某些教材对“趟”概念引用得不够严谨,很容易使学生对整个排序过程产生误解。以清华大学编《数据据构》(1987)为例,其快速排序的递归算法如下:     

一种基于数据块交换的快速稳定原地归并算法

与其它排序算法相比,二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个有序子表,经典算法有2种。第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动。第二种算法是原地的,但完成归并需要O(m+n)次比较和O(m×n)次移动。提出了一种基于块交换的快速稳定原地二路归并算法。实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数。     

一种基于数据块交换的快速稳定原地归并算法

与其它排序算法相比.二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个 有序子表,经典算法有2种/第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动/第 二种算法是原地的.但完成归并需要O(m+n)次比较和O(m*n)次移动,提出了一种基于块交换的快速 稳定原地二路归并算法.实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数.     

一种快速线性原地二路归并算法

将内部缓冲技术、浮洞技术与分治技术相结合．提出了一种快速线性原地二路归并算法。归并长度分别为m和n的2个有序子表(m≤n)，该算法最多需要2．5m 1．5n 4．5√m n次比较和7m 6n-√m n次移动。如进一步降低系数，并与其他好的排序算法有机结合，理论上的原地二路归并算法必将成为比快速排序更实用的算法。因此该线性原地二路归并算法具有较高的理论和实用价值。     

数据结构中基于分治策略的排序算法探讨

讨论了数据结构中基于分治策略的排序算法：合并排序和快速排序，给出了算法步骤，设计了算法实现的一般模式，并介绍了它们的几种改进算法。     

修正枢轴选取的并行排序

本文利用修正枢轴选取,给出一种适合所有基本排序算法的并行化方法,对均匀数据模型排序具有理想的并行加速及效率。     

二维数组的快速排序算法

在一维数组快速排序算法的基础上，给出了二维数组的快速排序算法，理论分析和大量的数值实验结果表明，其算法的平均计算时间仍然是Ｏ（ｎｌｏｇ２ｎ），一般所需的栈空间仍为Ｏ（ｌｏｇ２ｎ），是有效而可靠的快速排序算法。     

一种快速线性原地二路归并算法

将内部缓冲技术、浮洞技术与分治技术相结合-提出了一种快速线性原地二路归并算法。归并长度 分别为m和n的2个有序子表（m≤n）该算法最多需要　2.5m＋1.5n＋次比较和7m+6n+ 5041次移动。如进一步降低系数-并与其他好的排序算法有机结合-理论上的原地二路归并算法必将成 为比快速排序更实用的算法。因此该线性原地二路归并算法具有较高的理论和实用价值。     

基于二叉树的位排序算法

利用二叉树的结构性质 ,给出了一个基于二叉树的位排序算法 (BBS算法 ) .并证明了 BBS算法是生成二叉树的这组数据按排序码升序的排序 ,最后 ,我们讨论了该算法的算法复杂性 .     

一种新型快速排序算法的设计与实现

本给出了一种具有比传统快速排序算法性能更高的排序方法，该方法既不需要关键字之间的比较，也不需要记录的移动，全给出了该算法的描述，时间/空间复杂度分析和实验比较数据，实验表明，该算法特别适合于大数据量大记录的排序工作。     

基于平衡因子判定完全二叉树的算法

完全二叉树是数据结构中讨论的重要内容之一,目前对完全二叉树的判定方法较为单一,通过分析和研究完全二叉树和平衡二叉树中平衡因子的性质,得出了基于平衡因子判定完全二叉树的方法及判定算法。     

顺序存储的满二叉树中序遍历的非递归算法

从中序遍历的定义出发以及满二叉树的自身特点出发，得出了关于顺序存储的满二叉树中序遍历的性质，从而推导出一种全新的、逻辑结构非常清晰的、与递归解完全等效的非递归、不需使用堆栈的算法，以及该算法在其他问题上的应用和推广。     

在数据库上实现一种高效显示的任意树形结构

根据树形结构的显示特征和线索二叉树的访问顺序,提出了一种新的表结构用来保存树,并在此表结构的基础上提出了新的树形结构显示算法,同时给出了增减节点以及求某个节点的所有子孙节点的算法。     

基于二叉树的位排序算法

利用二叉树的结构性质,给出一个基于二叉树的位排序算法（ＢＢＳ算法）。并证明了该算是生成二叉树的这组数据按排序码升序的排序,最后,讨论了该算法的复杂性。     

直观显示二叉树结构的算法

在数据结构课程的教学中,一般是通过遍历二叉树抽象地显示1棵二叉树结构,这样学生不容易理解.为此提出了在TC环境下实现的一种直观显示二叉树结构的算法,该算法可以帮助学生加深对二叉树的理解,且对于学生掌握二叉树的运用有极大帮助,同时也是对数据结构课程教学的改进与提高.     

二叉树的最小面积画树算法的研究

本文提出了后序插入算法用于绘制二叉树,并使所绘制的二叉树所占用面积达到最小。并给出该算法在C#中的实现及绘制效果。     

改进的二进制查询树的RFID标签防碰撞算法

在射频识别系统中,存在阅读器与多个标签同时通信的碰撞问题,标签的防碰撞算法是解决数据冲突的关键。文章详细阐述了已有的典型的二进制查询树的防碰撞算法,并在此基础上提出了一种新的防碰撞算法;该算法利用二时隙的方法,使阅读器的询问次数和标签识别所需的数据流大大减少,提高了标签的识别效率。从仿真实验中表明,该算法比已有的二进制查询树算法具有更明显的优势。     

由先序序列和结点的层数构造严格二叉树的高效算法

提出一种新的通过一棵严格二叉树的先序序列和这棵严格二叉树的结点的层数构造这棵严格二叉树的非递归算法.举例说明新算法的执行过程.对于有n个结点的严格二叉树,新算法的时间复杂度为O(n),比相应的递归算法的低,新算法的最差情况空间复杂度为O(n),与相应的递归算法的相同.