foursort.java

计算机算法程序

package liu;

import java.util.Random;

import javax.swing.JOptionPane;

public class FourSort {
    private static int[] a;//存放数的数组
    private static int size;//数组大小
    public FourSort(int size) //初始化数组的值
    {   a = new int[size];
    	Random rand = new Random();
    	System.out.println("生成的数有：");
    	for(int i = 0;i < size - 1;i++)
    	{	
    		a[i] = rand.nextInt(100)+ 1;//随机产生数组的数
    	    System.out.print(a[i]+" - ");
    	}
    	a[size - 1] = rand.nextInt(100) + 1;
    	System.out.println(a[size - 1]);
    }
	public void MaopaoSort(int[] a,int size)  //冒泡排序
	{ 
		int temp,k = 0;//temp存放临时变量，k存放交换标志
		for(int i = 1;i < size ;i++)
		{	k = 0;
			for(int j = 0;j < size - i;j++)
			{ 
				if(a[j]>a[j + 1])   //如果当前节点比后一个节点大，则交换
				{ 
					temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
					k = 1;   //交换标志为1
				}
			}
			if(k ==0) break;  //若无交换，就退出
		}
	}
	public void InsertSort(int[] a,int size,int dk)//插入排序
	{ 
		int temp,k;
		for(int i = dk;i < size;i++)
		{  
	         temp = a[i];		
		     k = i;
	         while(temp < a[k-dk]) //temp和前面的元素比较
			 { 
		         a[k] = a[k-dk];//若小则把前面元素后移一个单位
			     k = k -dk;	
			     if(k <= dk - 1) { break;}
			 }
			a[k] = temp; //把temp放入合适位置 
		}
	}
	public void ChooseSort(int[]a,int size)//选择排序
	{ 
		int min,k;
		for(int i = 0;i < size - 1;i++)
		{
			k = i;
			min = a[i];
			for(int j = i + 1;j < size;j++) //找个最小的元素
			{ 
				if(a[j] < min) { min=a[j];k = j;}
			}
			if(k!=i) {a[k]=a[i];a[i]=min;}
		}	
	}
	public void ShellSort(int[] a,int size) //希尔排序
	{ 
		int dk = size/2;
		while(dk>=1)
		{ 
			InsertSort(a,size,dk);//调用插入函数
			dk = dk/2; //设定dk的值
		}
	}	
	public void Print() //打印排序后的数组
	{ 
		System.out.println("排序后的数据为：");
		for(int i = 0;i < size - 1;i++)
			System.out.print(a[i]+" - ");
		System.out.print(a[size - 1]);
	}
    public static void main(String[] args) {
		// TODO Auto-generated method stub
       int chose;//保存选择餐宿
       String s1 = JOptionPane.showInputDialog("chose the method of sort:\n1.select \n2.maopao \n3.insert \n4.shell");		
  	   chose  = Integer.parseInt(s1); //选择方法
       String s = JOptionPane.showInputDialog("Please input the numble of array:");		
 	   size  = Integer.parseInt(s); //输入节点个数
 	   FourSort shu = new FourSort(size);
 	   switch(chose)
 	   { 
 	       case 1:shu.ChooseSort(a,size);break;
 	       case 2:shu.MaopaoSort(a, size);break;
 	       case 3:shu.InsertSort(a, size, 1);break;
 	       default:shu.ShellSort(a, size);break;
 	   }
       shu.Print();
	}

}