！修改成从键盘输入的了，输入数字的时候要每次输入一个数后敲一下回车，因为用的是readLine方法
呵呵，我上学期算法设计与分析的实验
使用的是快速排序算法，不需要对原数列进行排序便可求出第k个元素
实验6 快速排序算法求第K个元素
问题描述
利用快速排序的方法，在不将所有数据排序的情况下找出数据中第K小元素。
设计思想
利用快速排序的方法，将数列A[i..j]分成A[i..p],A[p+1..j]2部分，并使的A[i..p]中的每个元素的键值都不大于A[p+1..j]中的每个元素的键值，这样如果k<=p,则第K个元素一定在数组A[i..p]中，如果k>p,则第K个元素一定在数组A[p+1..j]，此时，第K个元素在A[p+1..j]中为第k-q个元素(其中q为A[i..p]数组中元素的个数)。依次递归下去便可以找到第K个元素。
时间复杂度
设T(n)为在长度为n的数组中选择一个元素的时间，则可以得到递归式
T(n)≤(1/n)T(max(1,n-1))+ +O(n)
由此可得T(n) ≤Cn.
所以时间复杂度为O(n)
实验源程序
import java.util.Random;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
public class FindK
{
int[] arr;//存放数列
int size;//数列的容量
FindK(int size)
{//在数列arr中查找第k个元素
this.size=size;
//Random ran=new Random();
arr=new int[size];
System.out.println("请输入"+size+"个数字:");
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String temp = "1";
for(int i=0;i<size;i++)
{//从键盘上读入数列，数字之间以回车分隔
try
{
temp=bf.readLine();
}
catch(IOException ioe){}
try
{
arr[i]=Integer.parseInt(temp);
}
catch(NumberFormatException nfe)
{
System.out.println("你的输入不合法");
}
}
}
int quickSort(int p,int r,int k)
{//进行快速排序
int q;
int m;
int temp;
if(p==r) return(arr[p]);
q=partition(p,r,arr[p]);
temp=q-p+1;
if(k<=temp){m=quickSort(p,q,k); return m;}
else {m=quickSort(q+1,r,k-temp); return m;}
}
int partition(int p,int r,int keyword)
{//进行划分
int i,j;
int temp;
i=p;
j=r;
while(true)
{
for(;arr[j]>keyword;j--){}
for(;arr[i]<keyword;i++){}
if(i<j){temp=arr[i];arr[i]=arr[j];arr[j]=temp;}
else return(j);
}
}
void display()
{
String str="";
for(int i=0;i<size;i++)
{
str+=str.format("%8d",arr[i]);
}
System.out.println(str);
}
public static void main(String args[])
{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String sSize = "1";
int iSize = 1;
while(true)
{
System.out.println("请输入数列的容量:");
try
{
sSize = bf.readLine();//从键盘读入数列容量
}catch(IOException ioe){}
try
{
iSize = Integer.parseInt(sSize);
}catch(NumberFormatException nfe)
{
System.out.println("你的输入不合法");
continue;//进入下次循环
}
break;
}
FindK fk=new FindK(iSize);
int k=1;
long t;
fk.display();
String sn = "1";
while(true)
{
System.out.println("你要查找第几个元素？");
try
{
sn=bf.readLine();
}
catch(IOException ioe){}
try
{
k=Integer.parseInt(sn);
}
catch(NumberFormatException nfe)
{
System.out.println("你的输入不合法");
continue;
}
if(k<1||k>fk.size)
{//输入不合法
System.out.println("你的输入不合法");
continue;
}
break;//输入合法则结束循环
}
t=System.currentTimeMillis();
int result = fk.quickSort(0,fk.size-1,k);
t=System.currentTimeMillis()-t;
System.out.println("第"+k+"小元素是 ： "+result);
System.out.println("查找时间为 ： "+t+"ms");
}
}
温馨提示：答案为网友推荐，仅供参考