纵横多路并行归并算法

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

利用决策树对比较排序算法复杂性的分析

本文首先对算法复杂性进行了定义和描述,在此基础上借助于决策树,以排序过程中的比较次数作为复杂性的度量进行了比较排序算法复杂性的分析。     

合并排序算法的平均情形复杂性分析及其应用

在合理的“概率分布”假设下,分析了两个有序表合并排序算法的平均情形复杂性,并将此结果应用于个元素的二分排序算法中,最后对二分排序算法的平均情形复杂性进行了估计。     

链式归并排序法

介绍一种链式存储的逐步归并排序算法,其最佳时间复杂度为O(n),空间复杂度为O(1).     

内部排序算法的分析与比较

通过分析直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序等常用的内部排序算法的思想,统计各种算法的时间、空间复杂性、比较次数、移动次数以及稳定性,以期能够掌握这些算法及其特点,在实际应用中能够结合具体问题设计出正确而高效率的数据排序程序。     

排序算法的选择

影响排序效率的首要因素是算法，但算法时间复杂性的“O”表示法仅反映了渐近特性，不能作为依据来选择排序算法。本文指出了影响排序效率的一些其它因素，在实际中还需要根据这些因素选择不同的算法；文章还给出了几种排序程序的实验数据，这些数据表明当待排序数据较多时，分配排序的程序在执行时间上具有明显的优势。     

一种新的并行归并排序算法

文章提出了一种新的并行归并排序算法。算法充分利用并行系统中各个处理机中数据排序后序列长度相等的特点,计算出归并段对中的一个元素和最后一个元素的位置,然后再从相应的位置进行归并排序。该算法可使排序后的数据分布完全达到平衡,具有较高的负载平衡性、可扩展性和排序稳定性。文章最后给出了基于PC集群的实验结果,并把该结果与PSRS算法作了比较。     

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

文中提出了一种新的多种归并排序网络,该网络基于倾斜与振荡多路归并排序算法。     

链表递增归并排序算法

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

链表递增归并排序算法

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

基于队与栈结合排序算法实现及性能分析

排序有许多经典的算法,如插入排序、交换排序、选择排序等。这些排序算法的性能包括时间复杂度、空间复杂度以及稳定性各有优劣。笔者在这里给出一种全新的排序算法——队与栈排序。这种算法打破传统以交换或移动为主要排序的做法,而是借助栈和队这两种数据结构来实现排序。     

循环插入排序法

文章提出了一种循环插入的排序方法。给出了算法思想、算法描述、算法分析和实验结果。其理论意义是改进了一类时间复杂度为O(N2)排序法的时间复杂度,其实用价值是该排序法在一类时间复杂度为O(N2)排序法中排序效率较高的,其平均排序速度比直接插入排序法、选择排序法、冒泡排序快50%～63%。     

一种改进的中文字符串排序方法

对中文字符串排序,最快算法的时间复杂度是O（nlgn）。基数排序算法是目前最快的排序方法之一,时间复杂度是O（dn）,但其一般适用于相同长度的整型数据排序。提出了一种快速的变换方法,将字符串转换为与之等长的整型数组,使用基数排序算法对代表字串的整型数组排序,用以实现对字符串的快速排序。实验表明,提出的算法能快速地进行中文字符串排序,比快速排序算法具有更好的性能,且排序时间与数据规模之间是线性关系,算法的时间复杂度为O（dn）。     

求有限域的极小多项式的搜索算法

给出了求一个有限域的极小多项式的搜索算法，并由此算法求出了一类有限域，它们具有相同的极小多项式，并讨论了算法复杂性。     

4路插入排序法

提出一种4路插入的排序方法。给出了算法思想、算法描述、算法分析和实验结果。其理论意义是改进了一类时间复杂度为O（N^2）排序法的时间复杂度，其实用价值是该排序法存一类时间复杂度为O（N^2）排序法中排序效率较高的，其平均排序速度比直接插入排序法、选择排序法、冒泡排序快66％以上。     

快速插入排序法

设法用减少插入序列长度的办法，提出一种快速插入的排序方法。给出了算法思想、算法描述、算法分析和实验结果。其理论意义是改进了插入排序法的时间复杂度，其实用价值是该排序法的排序效率比直接插入排序法提高43％左右。     

Kolmogorov-Chaitin Complexity of Digital Controller Implementations

The complexity of linear, fixed-point arithmetic digital controllers is investigated from a Kolmogorov-Chaitin perspective. Based on the idea of Kolmogorov-Chaitin complexity, practical measures of complexity are developed for state-space realizations, parallel and cascade realizations, and for a newly proposed generalized implicit state-space realization. The complexity of solutions to a restricted complexity controller benchmark problem is investigated using this measure. The results show that from a Kolmogorov-Chaitin viewpoint, higher-order controllers with a shorter word-length may have lower complexity and better performance, than lower-order controllers with longer word-length.     

小间隔数据的地址映射链接排序算法研究

本文结合小间隔数据的特点,提出了一种谓之地址射链接的新排序方法,给出了百序算法的描述、时间复杂度分析及用ＰＡＳＣＡＬ语言、Ｃ语言编写程序进行算法比较的实验结果。     

A new complexity bound for the least-squares problem

For a least-squares problem of m degree polynomial regression with n measured values (n ≥ m + 1), the traditional methods need O(n²m) arithmetic operations. We prove that the arithmetic complexity of this problem does not exceed O(nlog²₂m).