JAVA泛型排序算法设计思想

网络出版时间：2011-11-13 00:06

网络出版地址：http://www.77cn.com.cn/kcms/detail/12.1151.TP.20111113.0006.009.html

软件2011年第32卷 第7期

Software

国际IT传媒品牌

JAVA泛型排序算法设计思想

金百东

（辽宁师范大学计算机与信息技术学院，辽宁,大连, 116081）

摘　要:论述了JAVA泛型排序设计思想。通过移植C++标准模板库的partial_sort、nth_element函数算法，可方便实现java下给定基本数据类型数组、对象数组、基本序列容器元素局部排序、求第nth元素功能，是对JAVA固有sort函数有效补充。并可运用spring框架加以封装，形成强大的排序组件管理功能。

关键词:java

泛型排序；局部排序；spring框架

中图分类号：TP301.6　　　　　文献标识码：A　　　　　　DOI: 10.3969/j.issn.1003-6970.2011.07.009

Thinking about general sort algorithm in JAVA

JIN Bai-dong

(School of computer and information technology,Liaoning normal university,Dalian 116081, China)

The topic discusses the thinking about java general sort. It is convenient to implement the partial sort and the nth function 【Abstract】

at basis data array, object array and basis sequence contain by plant the partial_sort and nth_element of C++ standard template library into java, and it is valid supplement to JAVA sort function. We can encapsulate the sort component by spring frame, that will lead to possess the the more stronger management function.

java general sort; partial sort; spring frame【Key words】

0　引　言

众所周知，排序是程序设计中经常用到的功能，非常讲究时间效率。常用的排序有3种类型：全局排序、局部排序、求第nth元素。JAVA语言中全局排序是由固有函数sort来完成的，没有固有的局部排序及求第nth元素函数。但是在实际中这两种排序是经常存在的。例如：求一个班成绩最好的3名同学信息，按成绩由高到低排列。其实，只需要通过某算法保证前3位同学有序且符合条件，后面所有同学没有必要是有序的，这就是局部排序。如果利用sort函数进行全排序，前3位即所求，当然是可以的。但无形中提高了时间开销。再如：求一个班成绩第5名同学信息。其实，只要保证第5名同学成绩低于前4名，高于其后同学成绩即可，没有必要保证除第5名之外的所有同学成绩都是有序排列的，这就是求第nth元素功能。因此，局部排序及求第nth元素功能是对JAVA固有sort函数的有益补充，是本文讨论的中心所在。

的相应排序功能，这即是本文所论述排序功能总体设计思想。1.1.1局部排序算法

VC6.0中局部排序关键源码如下所示。

void _Partial_sort(_RI _F, _RI _M, _RI _L, _Pr _P, _Ty *)

{

make_heap(_F, _M, _P);

for (_RI _I = _M; _I < _L; ++_I)

if (_P(*_I, *_F))

_Pop_heap(_F, _M, _I, _Ty(*_I), _P, _Dist_sort_heap(_F, _M, _P);}

可以看出，局部排序主要是堆排序的灵活应用，执行后[_F,_M)指向元素是有序的，是所求结果，而[_M,_L)指向元素未必是有序的，按表意形式该算法描述如下所示。

type(_F));

1　局部排序及求第nth元素设计思想

1.1　总体设计思想

关键是设计好两种排序算法。可以借鉴c++标准模板库中的partial_sort算法及nth_element算法。这两种算法都是专家级的，因此只要把它们移植到java中，就能实现专家级

作者简介:金百东（1969-）,讲师,硕士,主要研究方向:系统分析与应用。

图1　局部排序算法

按图1算法后[_F,_M)中指向任意元素与[_M, _L)相比，均满足函数_P关系。1.1.2　求第nth元素算法

VC6.0中该函数关键源码如下所示。 const int _SORT_MAX=16;

void _Nth_element(_RI _F, _RI _Nth, _RI _L, _Pr _P, _Ty *)

{

for (; _SORT_MAX < _L - _F; )

{_RI _M = _Unguarded_partition(_F, _L, _Median(_

有共同的父接口List。有巧妙的方法可实现图3中partial_sort(List<T> t, int nth)及nth_element(List<T> t, int nth)函数功能，以前者为例，函数流程图如图4所示。

流程图

toArray()函数，Comparator，在该接口不需关于堆操作public void partial_sort(int nth){

　make_heap(0, nth);

　int total = t.length;//t是成员变量　int pos = nth+1;　while(pos < total)　{

　　if(http://www.77cn.com.cnpare(t[0], t[pos])==1)　　{

　　　pos ++;　　　continue;　　}

　T mid = t[0];

子序列元素数少于16个（_SORT_MAX）,则不必再划分，直接对该子序列进行直接插入排序即可。

1.2总体实现框图

C++标准模板库中partial_sort、nth_element是泛型函数，可适用基本数据类型及对象。但是java中泛型参数只支持类对象，不能是基本数据类型。因此在java中：对基本数据类型而言只能一对一编程；对类而言，可采用泛型参数。本文主要讨论后者，其框图如图3所示。

(1)成员函数中前5个函数与局部排序功能相关，后5个函数与求第nth元素功能相关。

(2)成员变量中有一个泛型数阻t[],可知成员函数主要是以其为操作对象的。，对于基本序列容器，如对象存储在Vector、ArrayList、LinkedList等容器中，由于这些容器都

　t[0] = t[pos];　t[pos] = mid;

　adjust_heap(0, nth, 0);　pos++; 　}

sort_heap(0, nth);}

可以看出，该函数应用了2.1.1中所描述局部排序的算法。(2)partial_sort(List<T> v, int nth)代码public void rand(List<T> c){

　Object o[] = c.toArray();　t = (T[])o; //t是成员变量　partial_sort(nth); 　int n = 0;

　ListIterator<T> it = c.listIterator();　while(it.hasNext())　{

　　it.next();　　it.set(t[n]);　　n ++; 　} }

{

　public int compare(Integer t1, Integer t2) {　return t1<t2?1:0;}}

3　灵活管理排序功能模块

本文以图3中接口MyAlgoIntr内容来论述的，仅有一个实现类MyAlgo。若MyAlgoIntr接口有多个实现类，每个类中又需要许多自定义比较器类，很明显需要工厂模式来管理这些类对象。其实采用spring框架就可以完成所需功能，避免了人为的低层次的工厂类的开发。

例如，某sort.xml配置文件如下所示。<?xml version="1.0" encoding="utf-8"?><beans>

　　<bean id="MySort"　　　class="MyAlgo"　　</bean>

　　<bean id="MyLess"　　class="MyLess"　</bean></beans>

通过此配置文件可加载功能类MyAlgo及自定义比较器类MyLess。例如：若求某Vector<String> v中最小的3个字符串(不必排序，算法采用nth_element),则调用端关键代码如下所示。

Vector<String> v = new Vector();…… //向v中添加字符串

ApplicationContext c=new FileSystemXmlApplicationContext("sort.xml");

MyAlgoIntr o= (MyAlgoIntr)c.getBean("MyAlgo");MyLess m = (MyLess)c.get …… 此处隐藏：3587字，全部文档内容请下载后查看。喜欢就下载吧 ……