java排序,找中值的问题
在用ImageJ做java排序算法,目的是找一个81个元素的数组的中值(第41个值)我做的算法非常非常慢,因为要做大概100万次(有100万个像素),但是用Array.sort就很快。
可是老师不给用Array.sort
因为老师说Array.sort做了无用功,我们只要知道第41个值。
求助大神
什么样的算法适合这种情形? 算法 Java 排序算法 --------------------编程问答-------------------- top k的算法,使用堆 --------------------编程问答-------------------- 你们老师二! --------------------编程问答-------------------- 如果是面试题的话,通用方法是堆排序:
package findAndSort;
import org.junit.Test;
public class HeapSort {
/**
* 用于堆排序的全局变量temp
*/
private int temp;
/**
*调整某个子树
*分叶子、只有左、有左有右三种情况讨论
*/
public void oneHeap(int[] array,int index,int max){
//没有左孩子(即为叶子节点)
if(2*index+1>max){
return ;
}else{
//只有左孩子
if(index*2+1==max){
if(array[index]>array[index*2+1]){
return;
}else{
//父节点比左孩子小,交换;无需再递归
int leftIndex=index*2+1;
temp=array[index];
array[index]=array[leftIndex];
array[leftIndex]=temp;
}
}else{
//既有左孩子,又有右孩子的情况,筛选出关键字最大的孩子节点,并与父节点交换
int left=array[index*2+1];
int right=array[index*2+2];
if(array[index]>left&&array[index]>right){
return;
}else{
if(left>=right){
temp=array[index];
array[index]=left;
array[index*2+1]=temp;
//调整之后,为了符合堆的严格定义、加快下一次筛选速度,最好递归调整左或者右子树。
//不递归的话并不会影响最终结果
//this.oneHeap(array, index*2+1, max);
}else{
temp=array[index];
array[index]=right;
array[index*2+2]=temp;
//this.oneHeap(array, index*2+2, max);
}
}
}
}
}
/**
* 思想:
* 利用大根堆,执行n趟堆排序,把最大的n个值交换到数组末尾。
* 算法平均复杂度为 :
* nLog2(M)
*/
public void findMax(int[] array,int n){
int count=1,i=array.length-1;
while(count<=n){
for(int j=i/2;j>=0;j--){
this.oneHeap(array, j, i);
}
temp=array[0];
array[0]=array[i];
array[i]=temp;
i--;
count++;
}
System.out.println("第"+n+"个最大值为:"+array[array.length-n]);
}
/**
* 生成一些随机数
*/
public void getRandom(int[] array){
for(int i=0;i<=array.length-1;i++){
array[i]=(int) (Math.random()*array.length);
}
}
@Test
public void testHeapSort(){
int[] array=new int[81];
this.getRandom(array);
System.out.println("排序之前:");
for(int i:array){
System.out.print(i+"\t");
}
System.out.println();
this.findMax(array, 41);
}
}
结果:
排序之前:
15 26 57 51 48 3 9 0 12 46 37 14 19 22 15 66 57 70 21 62 7 65 58 14 19 57 0 57 80 42 67 62 45 20 74 33 24 4 52 32 56 4 18 64 45 10 45 15 26 28 53 61 8 76 37 7 36 11 1 66 30 32 45 79 47 5 70 17 44 69 32 56 58 73 65 6 40 74 32 57 56
第41个最大值为:40
--------------------编程问答-------------------- 各位大神好厉害,膜拜
补充:Java , Java相关