Question

谁能帮忙写一个java的合并排序和二分查找的程序？

作业要求比较线性查找和二分查找用时，对10万个随机数排序，不想用n方的排序法，谁写个n*log2 n的？

Answer 1

10万个数统计时间太短，我多写个循环给你吧
public class Testchazhao{
public static void main(String[] args){
int[] array = new int[100000];
int i = 0;
int j = 0;
int[] count = {0};
for(i = 0;i < 100000;i++){
array[i] = (int)(Math.random()*100000000);
}
int test = (int)(Math.random()*100000);
long start = System.currentTimeMillis();
for(j = 0;j < 100000;j++){
for(i = 0;i < 100000;i++){
if(array[i] == test){
break;
}
}
}
long end = System.currentTimeMillis();
long time1 = end-start;
System.out.println(time1);
fen(array,0,100000);
start = System.currentTimeMillis();
for(j = 0;j < 100000;j++){
erfen(array,0,99999,test,count);
}
end = System.currentTimeMillis();
long time2 = end - start;
System.out.println(time2);
}

public static void fen(int[] array,int p,int r){
if(p < r){
int q = (p+r)/2;
fen(array,p,q);
fen(array,q+1,r);
he(array,p,q,r);
}
}

public static void he(int[] array,int p,int q,int r){
int i = 0;
int j = 0;
int k = 0;
int lenthleft = q-p;
int lenthright = r-q;
int[] arrayleft = new int[lenthleft+1];
int[] arrayright = new int[lenthright+1];
for(i = 0;i < lenthleft;i++){
arrayleft[i] = array[p+i];
}
for(j = 0;j < lenthright;j++){
arrayright[j] = array[q+j];
}
arrayleft[lenthleft] = arrayright[lenthright] = 2000000000;
i = j = 0;
for(k = p;k < r;k++){
if(arrayleft[i] <= arrayright[j]){
array[k] = arrayleft[i];
i++;
}
else{
array[k] = arrayright[j];
j++;
}
}
}
public static void erfen(int[] array,int qian,int hou,int key,int[] count){
int temp = 0;
if(key >= array[qian]&&key <= array[hou]&& count[0] != 1){
if(qian < hou){
temp = (qian+hou)/2;
if(key == array[temp]||key == array[qian]||key == array[hou]){
count[0] = 1;
}
else if(key < array[temp]){
erfen(array,qian,temp,key,count);
}
else{
erfen(array,temp,hou,key,count);
}
}
}
}
}