k_min.java

利用改进的桶排序算法查找一个无序数组中的第k小元算法java实现

import java.io.*;
import java.util.*;
////////////////////////////////////////////
class Node{
	int iData;
	Node next;
	//------------------
	public void Node(){}
	//------------------
	public void Node(int id){
		iData=id;
	}
	//----------------
	public void insertFirst(Node n){
		n.next=this.next;
		this.next=n;
	}
}
////////////////////////////////////////////
public class K_Min{
	final int n=100;
	Node[] node=new Node[n];
	int[] data=new int[n];
	int[] num=new int[10];
	int k;
	//----------------------
	void generateNum(){
		System.out.println("产生小于10000的随机数序列为: ");
		Random rand=new Random();
		for(int i=0;i<n;i++){
			data[i]=rand.nextInt(10000);
			if(data[i]<1000) {
				i--;
				continue;
			}
			node[i]=new Node();
			node[i].iData=data[i];
			System.out.print(data[i]+"\t");
		}
		
		for(int j=0;j<10;j++)
			num[j]=0;
		System.out.println();
	}
	//-----------------------
	public void kthMin(){
		Node[] first=new Node[10];
		int sum=0;
		for(int i=0;i<10;i++){
			first[i]=new Node();
			first[i].iData=i;
			first[i].next=null;
		}
			
		for(int i=0;i<n;i++){
			first[data[i]/1000].insertFirst(node[i]);
			num[data[i]/1000]++;
		}
		
		System.out.println("所有数字在桶里的分布情况如下：");
		for(int i=0;i<10;i++){
			Node current=first[i];
			System.out.print("桶"+current.iData); 
			current=current.next;
			while(current!=null){
				System.out.print("-->"+current.iData);
				current=current.next;
			}
			System.out.println();			
		}
		
		System.out.println("每个桶里的数字的数目为: ");
		for(int i=0;i<10;i++){
			System.out.print(num[i]+"\t");
		}
		
		System.out.print("请输入你想求第k小元的k值: ");
		try{
			k=Integer.parseInt(new BufferedReader
					(new InputStreamReader(System.in)).readLine());
		}catch(IOException e){}
		
		for(int i=9;i>0;i--){
			if(num[i]!=0)	sum+=num[i];
			else continue;
			if(sum<k)	continue;
			else { 
				sort(first[i],num[i],sum-num[i],k);
				break;
			}
		}
	}
	//-----------------------
	public void sort(Node node,int num,int s,int k){
		int m=0,p=0;
		int temp;
		int[] b=new int[n];
		Node cur=node.next;		
		while(cur!=null){
			b[p]=cur.iData;
			m++;p++;
			cur=cur.next;
		}
		for(int i=1;i<m;i++){
			for(int j=0;j<m-i;j++)
				if(b[j]>b[j+1]){
					temp=b[j];
					b[j]=b[j+1];
					b[j+1]=temp;
				}
		}
		System.out.println("第"+k+"小元是："+b[num+s-k]);
	}
	//-----------------------
	public static void main(String[] args){
		K_Min km=new K_Min();
		km.generateNum();
		km.kthMin();
	}
}