排序算法比较_java课程设计_刘阳辉.doc

刘阳辉 08软件工程3班 080107031120 个人技术博客：目 录一、课程设计目的.02二、设计内容和要求.02三、程序开发环境.02四、程序内容.02五、设计原理.02六、技术亮点.02七、程序流程图.03八、程序模拟运.03九、程序代码.05十、设计体会.18一、 设计目的 1 掌握各种排序的基本思想。 2 掌握各种排序方法的算法实现。 3 掌握各种排序方法的优劣分析及花费的时间的计算。 4 掌握各种排序方法所适应的不同场合。 二、 设计内容和要求 利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。三、开发环境开发平台：windows XP开发环境：MyEclipse 8.5 jdk 6.0开发语言：java四、程序内容第一部分：显示用户界面；第二部分：输入希望产生的随机数的数量；第三部分：点击获取数据按钮，根据用户输入的随机数的数量产生相应的随机数，并显示出来；第四部分：点击排序按钮，将产生的随机数进行排序后重新显示出来，并计算显示每种排序算法所用的想用时间。五、设计原理首先使用随机函数产生相应的随机数并保存在整型数组中，并将整型数组里面的元素显示到用户界面，点击排序按钮后，将整形数组以传地址的方式传到排序类中进行排序，排序完后将再次显示整形数组里面的所有元素。六、技术亮点1为提高程序效率，在使用七种排序算法时采用多线程技术同时执行七个排序线程，从而提高程序执行效率；2自定义动态数组，在程序执行的过程中根据用户输入的随机数的量来产生相应大小的整形数组；3.更人性化的随机数，根据用户输入的随机数的数量(max)来产生的随机数的范围为0至max；七、程序流程图八、程序模拟运行(截图描述)1开始运行界面，并输入初始测试数据量，我输入数据量为30000；2.点击获取数据按钮，随机出30000条随机数并显示出来，可以看出这些数还是没有排序的随机数据；3.点击排序按钮，这时会启动七个线程，排序完毕后显示排序后的数据以及花费时间；4.点击关于按钮，显示一些个人信息；九、程序代码1.主方法类package gui;/* * Author:刘阳辉 * Describe:各种算法花费时间比较器 * Web: (本人技术博客,算是做个广告吧) * JDK:1.60 * Date:2010-09-07 */import java.awt.BorderLayout;import java.awt.Color;import java.awt.FlowLayout;import java.awt.Font;import java.awt.GridLayout;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.util.Date;import java.util.Random;import javax.swing.JButton;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JOptionPane;import javax.swing.JPanel;import javax.swing.JScrollPane;import javax.swing.JTextArea;import javax.swing.JTextField;import javax.swing.border.LineBorder;import javax.swing.border.TitledBorder;import Sort.SortUtil;public class mainForm implements ActionListenerprivate JFrame frame;private JTextArea jta;private JScrollPane jsp;private JLabel jlbNum;private JLabel jlbcr;private JLabel jlbmp;private JLabel jlbxz;private JLabel jlbks;private JLabel jlbd;private JLabel jlbgb;private JLabel jlbsl;private JTextField jtfNum;private JTextField jtfcr;private JTextField jtfmp;private JTextField jtfxz;private JTextField jtfks;private JTextField jtfd;private JTextField jtfgb;private JTextField jtfsl;private JButton jbtnNum;private JButton jbtnSort;private JButton jbtnAbout;private JButton jbtnExit;private JPanel panel1;private JPanel panel2;private JPanel panel3;private JPanel panel4;boolean flag=false;public int num1=null;public int num2=null;public int num3=null;public int num4=null;public int num5=null;public int num6=null;public int num7=null;public Date dateStart=null;public Date dateCr=null;public Date dateMp=null;public Date dateXz=null;public Date dateKs=null;public Date dateD=null;public Date dateGb=null;public Date dateSl=null;public mainForm()frame=new JFrame(排序算法比较器v1.2);jta=new JTextArea(15,30);jta.setLineWrap(true);jsp=new JScrollPane(jta);panel1=new JPanel();panel2=new JPanel();panel3=new JPanel();panel4=new JPanel();jlbNum=new JLabel(输入测试数据量:);jlbcr=new JLabel( 插 入 排 序:);jlbmp=new JLabel( 冒 泡 排 序:);jlbxz=new JLabel( 选 择 排 序:);jlbks=new JLabel( 快 速 排 序:);jlbd=new JLabel( 堆 排 序:);jlbgb=new JLabel( 归 并 排 序:);jlbsl=new JLabel( 希 尔 排 序:);jtfNum=new JTextField(600,6);jtfcr=new JTextField();jtfmp=new JTextField();jtfxz=new JTextField();jtfks=new JTextField();jtfd=new JTextField();jtfgb=new JTextField();jtfsl=new JTextField();jbtnNum=new JButton(获取数据);jbtnSort=new JButton(排 序);jbtnAbout=new JButton(关 于);jbtnExit=new JButton(退 出);addAction();init();public void init()/界面初始化panel1.add(jlbNum);panel1.add(jtfNum);panel1.add(jbtnNum);panel2.setLayout(new GridLayout(7,2);panel2.setBorder(new TitledBorder(new LineBorder(Color.GRAY),算法花费时间(单位:ms);panel2.add(jlbcr);panel2.add(jtfcr);panel2.add(jlbmp);panel2.add(jtfmp);panel2.add(jlbxz);panel2.add(jtfxz);panel2.add(jlbks);panel2.add(jtfks);panel2.add(jlbd);panel2.add(jtfd);panel2.add(jlbgb);panel2.add(jtfgb);panel2.add(jlbsl);panel2.add(jtfsl);panel3.setLayout(new FlowLayout();panel3.add(jbtnSort);panel3.add(jbtnAbout);panel3.add(jbtnExit);panel4.setLayout(new BorderLayout();panel4.add(panel1,BorderLayout.NORTH);panel4.add(panel2,BorderLayout.CENTER);panel4.add(panel3,BorderLayout.SOUTH);frame.add(jsp,BorderLayout.WEST);frame.add(panel4,BorderLayout.EAST);jta.setFont(new Font(黑体,Font.BOLD,18);frame.setSize(620,300);frame.setResizable(false);frame.setLocation(300, 300);frame.setVisible(true);frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);public void addAction()/添加监听器jbtnNum.addActionListener(this);jbtnSort.addActionListener(this);jbtnAbout.addActionListener(this);jbtnExit.addActionListener(this);public void actionPerformed(ActionEvent e) if(e.getActionCommand().equals(获取数据)getNum();if(e.getActionCommand().equals(排 序)sort();if(e.getActionCommand().equals(关 于)JOptionPane.showMessageDialog(null, 作者：刘阳辉n学号：080107031120n专业：08软件工程3班n博客：n时间：2010-09-07);if(e.getActionCommand().equals(退 出)System.exit(0);/获取随机数据函数public void getNum()int max=Integer.parseInt(jtfNum.getText().trim();myInt(max);if(max100000)JOptionPane.showMessageDialog(null, 数据错误！n请输入1-100000之间的整数！);jtfNum.setText();elseRandom rnd=new Random();if(flag)jta.setText();flag=false;for(int i=0;imax;i+)num1i=rnd.nextInt(max);num2i=rnd.nextInt(max);num3i=rnd.nextInt(max);num4i=rnd.nextInt(max);num5i=rnd.nextInt(max);num6i=rnd.nextInt(max);num7i=rnd.nextInt(max);jta.append(String.valueOf(num1i)+|);frame.repaint();flag=true;/排序函数public void sort()/创建各排序算法的线程Thread tCr=new cr();Thread tMp=new mp();Thread tXz=new xz();Thread tKs=new ks();Thread tD=new d();Thread tGb=new gb();Thread tSl=new sl();/启动排序算法线程dateStart=new Date();tCr.start();tMp.start();tXz.start();tKs.start();tD.start();tGb.start();tSl.start();/下面是各种排序算法的调用线程class cr extends Threadpublic void run() new SortUtil();SortUtil.sort(num1,1);jta.setText();for(int i=0;inum1.length;i+)jta.append(num1i+|);dateCr=new Date();jtfcr.setText(String.valueOf(dateCr.getTime()-dateStart.getTime()+ ms);class mp extends Threadpublic void run() new SortUtil();SortUtil.sort(num2,2);dateMp=new Date();jtfmp.setText(String.valueOf(dateMp.getTime()-dateStart.getTime()+ ms);class xz extends Threadpublic void run() new SortUtil();SortUtil.sort(num3,3);dateXz=new Date();jtfxz.setText(String.valueOf(dateXz.getTime()-dateStart.getTime()+ ms);class ks extends Threadpublic void run() new SortUtil();SortUtil.sort(num4,5);dateKs=new Date();jtfks.setText(String.valueOf(dateKs.getTime()-dateStart.getTime()+ ms);class d extends Threadpublic void run() new SortUtil();SortUtil.sort(num5,9);dateD=new Date();jtfd.setText(String.valueOf(dateD.getTime()-dateStart.getTime()+ ms);class gb extends Threadpublic void run() new SortUtil();SortUtil.sort(num6,7);dateGb=new Date();jtfgb.setText(String.valueOf(dateGb.getTime()-dateStart.getTime()+ ms);class sl extends Threadpublic void run() new SortUtil();SortUtil.sort(num7,4);dateSl=new Date();jtfsl.setText(String.valueOf(dateSl.getTime()-dateStart.getTime()+ ms);/自定义可变数组 public void myInt(int n) num1=new intn; num2=new intn; num3=new intn; num4=new intn; num5=new intn; num6=new intn; num7=new intn; public static void main(String args) new mainForm();2.各种排序算法类=package Sort;/冒泡排序 public class BubbleSort implements SortUtil.Sort public void sort(int data) int temp; for(int i=0;ii;j-) if(datajdataj-1) SortUtil.swap(data,j,j-1); =package Sort;/堆排序public class HeapSort implements SortUtil.Sort public void sort(int data) MaxHeap h=new MaxHeap(); h.init(data); for(int i=0;idata.length;i+) h.remove(); System.arraycopy(h.queue,1,data,0,data.length); private static class MaxHeap void init(int data) this.queue=new intdata.length+1; for(int i=0;idata.length;i+) queue+size=datai; fixUp(size); private int size=0; private int queue; public int get() return queue1; public void remove() SortUtil.swap(queue,1,size-); fixDown(1); private void fixDown(int k) int j; while (j = k 1) = size) if (j size & queuejqueuej) /不用交换 break; SortUtil.swap(queue,j,k); k = j; private void fixUp(int k) while (k 1) int j = k 1; if (queuejqueuek) break; SortUtil.swap(queue,j,k); k = j; =package Sort; import gui.mainForm;/插入排序 public class InsertSort implements SortUtil.Sort public void sort(int data) int temp; for(int i=1;i0)&(datajdataj-1);j-) SortUtil.swap(data,j,j-1); =package Sort;/归并排序public class MergeSort implements SortUtil.Sort public void sort(int data) int temp=new intdata.length; mergeSort(data,temp,0,data.length-1); private void mergeSort(int data,int temp,int l,int r) int mid=(l+r)/2; if(l=r) return ; mergeSort(data,temp,l,mid); mergeSort(data,temp,mid+1,r); for(int i=l;i=r;i+) tempi=datai; int i1=l; int i2=mid+1; for(int cur=l;curr) datacur=tempi1+; else if(tempi11) quickSort(data,i,k-1); if(j-k)1) quickSort(data,k+1,j); private int partition(int data, int l, int r,int pivot) do while(data+lpivot); SortUtil.swap(data,l,r); while(lr); SortUtil.swap(data,l,r); return l; =package Sort;/选择排序 public class SelectionSort implements SortUtil.Sort public void sort(int data) int temp; for (int i = 0; i i; j-) if (dataj 2;i/=2) for(int j=0;ji;j+) insertSort(data,j,i); insertSort(data,0,1); private void insertSort(int data, int start, int inc) int temp; for(int i=start+inc;i=inc)&(datajdataj-inc);j-=inc) SortUtil.swap(data,j,j-inc); =package Sort;public class SortUtil public final static int INSERT = 1; public final static int BUBBLE = 2; public final static int SELECTION = 3; public final static int SHELL = 4; public final static int QUICK = 5; public final static int IMPROVED_QUICK = 6; public fin