一种基于数据分块的快速原地归并算法

与其它排序算法相比,二路归并最适合于对两个有序子表进行排序.归并长度分别为m和n的两个有序子表,经典算法有两种.第一种算法完成归并需要○(m+n)的附加空间,○(m+n)次比较和移动.第二种算法是原地的,但完成归并需要○(m+n)次比较和○(m×n)次移动.经过长期研究,提出了一种基于数据分块的快速原地归并算法.新算法通过将数据分块、对数据块排序等方法最多用○((m+n)log2√m+n次比较和○((m+n)3/2)次移动完成两个有序子表的原地归并.实验证明,该算法与经典的原地算法相比,极大地降低了元素的移动次数和算法的运行时间.     

链表递增归并排序算法

归并排序是一种稳定．高效的排序算法。归并排序算法一般是用顺序存储结构实现的。如Sun公司JDK中Java Collection库中对数组、List的排序。使用顺序存储结构实现归并排序需要空间复杂度为O(n)的辅助存储空间，对于链表来说，还需要转换为顺序存储结构，所以共需要2n的辅助存储空间。本文提出一种链表非递归归并排序算法，可以对链表进行原地(In Place)排序，只需要O(logn)辅助存储空间，时间复杂度不变。     

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

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

纵横多路并行归并算法

基于倾斜与振荡法多路归并排序算法,提出了纵横多路并行归并算法,与已有方法递归应用两路归并过程不同·该算法直接对m×k的矩阵(m,k为任意整数)进行排序,消除了对两路递归过程的依赖,是一种新的多路归并排序算法·通过和倾斜与振荡法多路归并排序算法和高效的任意路并行归并算法的性能分析比较,当3k40时,该算法的时间复杂性低于同类算法·同时,该算法在专用硬件实现的设计复杂性上也具有明显的优势·     

背包问题的一种自适应算法

背包问题是经典的NP-hard组合优化问题之一，由于其难解性，该问题在信息密码学和数论研究中具有极重要的应用．基于求解背包问题著名的二表算法和动态二表算法，利用归并原理和4个非平衡的子表，提出一种求解该问题的自适应算法，算法可根据计算资源和问题实例规模的大小，允许使用O(2^n/2-ε)的存储空间(1≤ε≤n／4)，在O(ε(2^n/2))的时间内求解背包问题．对算法性能的理论分析和数值实验结果表明，自适应算法可显著扩大背包实例的求解规模，从时间和空间上改进背包问题现有算法的性能．     

链表递增归并排序算法

归并排序是一种稳定,高效的排序算法。归并排序算法一般是用顺序存储结构实现的。如Sun公司JDK中Java Collection库中对数组、List的排序。使用顺序存储结构实现归并排序需要空间复杂度为O(n)的辅助存储空间,对于链表来说,还需要转换为顺序存储结构,所以共需要2n的辅助存储空间。本文提出一种链表非递归归并排序算法,可以对链表进行原地(In Place)排序,只需要O(logn)的辅助存储空间,时间复杂度不变。     

一种新的多路归并排序网络

文中提出了一种新的多路归并排序网络,该网络基于倾斜与振荡多路归并排序算法．该网络有两个主要特点．一是其基本构件为ｋ－ｓｏｒｔｅｒｓ,即ｋ个数的排序器,ｋ为任意素数,而传统的排序网络的基本构件为两个数的排序,即２－ｓｏｒｔｅｒｓ．二是该网络的延迟可以小于传统的基于２－ｓｏｒｔｅｒｓ的Ｂａｔｃｈｅｒ排序网络．文中给出了该排序网络的具体实现;作为实例给出了Ｎ＝２７,ｋ＝３时的排序网络;分析了该网络的时间延迟;通过具体设计排序网络的基本构件２－ｓｏｒｔｅｒｓ和３－ｓｏｒｔｅｒｓ,表明这种新的多路归并排序网络和Ｂａｔｃｈｅｒ排序网络相比是一种高速的排序网络．     

基于散列和归并技术的有效并行排序方法

本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法：将长度为ｎ的待排序数据划分成ｐ个长度为ｎ／ｐ的子序列，引入散列技术并行地对这ｐ个子序列的数据进行二次散列排序，这一阶段所需的平均时间为Ｏ（ｎ／ｐ）；最后并行地将ｐ个有序子序列归并成一个长度为ｎ的有序序列，归并阶段所需的时间为Ｏ（ｎ－ｎ／
／ｐ）。整个排序算法的并行执行代价为Ｏ（ｎｐ）。本排序方法可以拓以网络并行机群环境。     

一种三路划分快速排序的改进算法

快速排序是一种经典的排序算法,它的平均性能非常突出。针对快速排序在某些特殊情况下(如数据已有序或重复数据较多时)效率较低的问题进行了研究,对三路快速排序进行改进,使快速排序在特殊情况下也能保持较好的效率。通过大量的数据测试发现,该算法在最好情况下其性能在几个数量级上优于普通快速排序,在最坏情况下,其性能较普通快速排序无明显差距。改进后的三路快速排序是一种通用高效的排序算法,因此在某些情况下选用、该算法会获得更好的效率。     

分档定位排序以及向分档定位查找的发展

分析了“王向阳二次分档排序”的不足．给出了等概分档映射算法，对已知分布函数的n个任意数据，仅需遍历计算一次，就可以分为m档，实现档之间有序化(档内仍无序)．令m≥n，可以使得每档数据量期望值不大于1，待排序序列已经接近有序化了，只需用很少的时耗即可完成档内排序，从而建立一个有序且等概分档的查找表．在此基础上，提出了分档定位查找算法，其优势是：①对于待查找的某个数，不需要进行“比较”，而只要进行“计算”，就可以直接在该查找表中确定一个数据“档”作为查找目标；②可以在该“档”范围内使用折半查找等高效查找；③适用于任意数据且数据量很大的查找表；④在避免了全程查找的同时也避免了“冲突”现象．