Java实现数据排序算法

数据结构描述的是数据之间的关系。C++数据结构的存储方式有顺序、链接、索引、散列等形式，对数据的处理通常包括输入、输出、查找、更新、排序、插入、删除等，当数据的存储方式不同时，相应的处理实现算法也不尽相同。如何采用一种简便明了的方法分析C++的数据结构特点及各种存储方式、处理方式之间的异同成为了计算机应用专业教育的一个难点。针对远程开放教学学生大多数通过网络课件自学这一特点，采用当今流行的跨平台程序设计语言java实现对C++数据结构算法的模拟，可以很好地解决对数据存储方式、处理方式的具体化问题。利用java语言程序设计的灵活性及交互性，实现数据的动态输入，自动、分步、循环执行存储处理过程，并在internet上发布。 　　1、实现的功能

　　使用Java技术编写的Java applet 程序，在网页上发布，可以方便与用户交互，用户可以初始化算法元素，可以选择执行方式（自动执行或单步执行）；可以起止程序的执行；显示当前程序运行的状态；同步显示算法描述与算法过程的变化。这里我们以直接选择排序（升序）为例子，来分析采用Java技术实现算法的摸拟演示。效果图：
　　

　　说明："直接排序数据"，文本框用来接收用户输入的数据。"排序数据个数"，显示用户输入的数据数。"当前最小值"，当前程序执行时的最小值。"运行状态"，显示当前程序运行状态。"确定输入"，接收用户的输入。"自动执行"，根据用户的输入自动进行排序演示。"单步执行"，根据用户的输入，用户可以手动控制程序的执行过程。"结束演示"，结束演示，等待下一次演示。"列表框"，在程序执行过程中与图形变化同步显示相对应的算法描述。
2、分析算法并将其转化为图形符号

　　直接选择排序的基本思想是：每一趟 (例如第 i 趟，i = 0, 1, …, n-2) 在后面 n-i 个待排序对象中选出关键码最小的对象, 作为有序对象序列的第 i 个对象。待到第 n-2 趟作完，待排序对象只剩下1个，就不用再选了。

　　它的基本步骤是：在一组对象v[i]～v[n-1]中选择具有最小关键码的对象；若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调； 在这组对象中剔除这个具有最小关键码的对象，在剩下的对象v[i+1]～v[n-1]中重复执行前两步，直到剩余对象只有一个为止。
下面将用一系列的图形符号表示出该算法的执行过程。假设将对

　　36 25 48 12 65 43 20 58

　　这一组数据进行直接排序
　　



　　向上箭头前面为已排好序的数据，为一有序表；向上箭头后面的数据为待排序区间，是一无序表；双向向下箭头表示两数据交换。根据对排序过程分析，可以用下面图形符号表示算法中的元素：
　　



5、对演示过程的控制

　　对演示过程的控制在这里用按钮方式主要实现程序的起始、自动执行、单步执行。这里采用的线程，在程序中定义一线程Thread allinone，所以我们将用一个run()过程放置程序主体部分-----包括对数据的排序和图形、列表的对应显示。可以用allinone.start()来开始程序，用allinone.stop()来结束程序。可以用allinone.start()来开始程序并自动执行run()中的程序体，执行过程较快，可以用Thread.sleep(100 )来暂停1秒。在run()中设置了变量step,当step==1时，即进入单步执行。这时使用suspend() 使线程挂起,暂停运行。当执行下一步时，使用resume() 恢复挂起的线程,使处于可运行状态。

　　6、程序对异常的实现

　　对于程序的异常处理，可以采用 try {} catch(InterruptedException e){}来捕捉，并执行相应的处理。

　　7、程序的发布

　　java applet 可以插入普通网页中。利用普通web服务器进行对外发布，在网页中采用插入：＜applet code="文件名.class" codebase = 文件相对路径 width="" height=""＞＜/applet＞ html语句来实现。

　　8、结束语

　　通过以上几步，再按照java applet程序的一般结构完整程序，就可基本实现利用java对C++数据结构算法描述的模拟，虽然这里只举了直接选择排序的例子，但其他描述的模拟也可以使用以上方法实现。望本文能起到抛砖引玉作用，使java技术能在工作、生活中更多的应用。


　　其中，向下箭头表示当前正在排序区间内查找的元素，向上箭头为当前排序区间的开始位置。

　　3、输入输出处理的实现

　　为了增强模拟程序的交互性，在程序中将引入元素的用户输入、程序执行过程中算法描述同步执行、程序运行状态的显示。在程序界面上定义一个单行文本框来让用户输入元素，并将定义初始元素（定义可以放在init()中）：


TextField edit1;
edit1 = new TextField(22);
add(edit1);
edit1.setText("36 25 48 12 65 43 20 58");

　　在程序中定义StreamTokenizer类和array[]数组来接收用户输入的数据。 StreamTokenizer即令牌化输入流的作用是将一个输入流变成令牌流。这里使用的是StreamTokenizer.TT_NUMBER: 表示读到的令牌是数字，数字的值是double型，可以从实例变量nval中读取。


StringTokenizer stringt = new StringTokenizer(edit1.getText());
array = new int[stringt.countTokens() + 1];//定义数组
for(int i = 1; stringt.hasMoreTokens(); i++)//数组赋值
array[i] =Integer.valueOf(stringt.nextToken()).intValue();

　　定义一个列表框list1用于对程序执行过程时算法描述的同步显示，并将算法描述按执行顺序分步初始化给列表：


list1 = new java.awt.List();
add(list1);
list1.addItem("template 〈class Type〉 void Sort(datalist〈Type〉 &list){"};
……
list1.addItem(")");

　　当程序执行时，采用list1.select()来选中相应的算法描述语句。在程序界面上定义一单行文本框edit5用于运行状态的显示:


TextField edit5; Edit5 = new TextField(22); add(edit5);

　　利用其edit5.setText(string)来显示当前程序运行状态。

　　4、用java语言描述图形符号

　　在java 中，可以利用其方便的绘图语句来实现以上图形符号。包括表中元素的移动，两种箭头的移动。在表元素移动时可以将表与元素分离，表在元素移动时不需重绘，元素移动时也只需将元素按照排序的需要使用repaint()进行重绘。 构建一个表中图形实现元素移动，语句放在public void paint(Graphics g){}中执行：


for(int i = 1; i 〈 array.length; i++)
{ g.drawString(String.valueOf(array[i]),X, Y);}

　　元素的重绘根据排序的需要执行，下面语句实现了元素的排序及元素的移动（在run()中实现）：


nowup_p = 3;
nowdown_p = 1;
for(nowdown_p = 1; nowdown_p 〈 array.length - 1; nowdown_p++)
{ int aa = array[nowdown_p];int aap = nowdown_p;
for(nowup_p = nowdown_p + 1; nowup_p 〈 array.length; nowup_p++)
{ repaint();
if(aa 〉 array[nowup_p])
{ aa = array[nowup_p];aap = nowup_p;}
Thread.sleep(100);}
array[aap] = array[nowdown_p];array[nowdown_p] = aa;
repaint();}
nowup_p = nowdown_p = 0;
repaint();}

　　箭头的移动，利用了上述程序体中nowdown_p、nowdown_p的改变，利用g.drawline（）、g.setColor()语句来完成。


摘自：ZDnet　　　时间：2003年9月11日 　

原文转自：http://www.ltesting.net