丹蓓姿,孙升模,纸玄网
java jdk里面容器类的排序算法使用的主要是插入排序和归并排序,可能不同版本的实现有所不同,关键代码如下:
// merging
// if arrays are already sorted - no merge
if (((comparable<object>) in[med - 1]).compareto(in[med]) <= 0) {
system.arraycopy(in, start, out, start, len);
return;
}
int r = med, i = start;
// use merging with exponential search
do {
comparable<object> fromval = (comparable<object>) in[start];
comparable<object> rval = (comparable<object>) in[r];
if (fromval.compareto(rval) <= 0) {
int l_1 = find(in, rval, -1, start + 1, med - 1);
int tocopy = l_1 - start + 1;
system.arraycopy(in, start, out, i, tocopy);
i += tocopy;
out[i++] = rval;
r++;
start = l_1 + 1;
} else {
int r_1 = find(in, fromval, 0, r + 1, end - 1);
int tocopy = r_1 - r + 1;
system.arraycopy(in, r, out, i, tocopy);
i += tocopy;
out[i++] = fromval;
start++;
r = r_1 + 1;
}
} while ((end - r) > 0 && (med - start) > 0);
// copy rest of array
if ((end - r) <= 0) {
system.arraycopy(in, start, out, i, med - start);
} else {
system.arraycopy(in, r, out, i, end - r);
}
}
比如{1,2,3,5,8,13}使用下列集合表示:
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
伪代码如下:
for (i in [0~n-1]) bit[i] = 0;
for(i in [0~n-1])
if (i in input file)
bit[i] = 1
for(i in [0~n-1])
if(bit[i] == 1)
output i
用java 代码尝试下,效率果然不错:
public static void main(final string[] args) {
list<integer> firstnum = new arraylist<integer>();
list<integer> secondnum = new arraylist<integer>();
for (int i = 1; i <= 1000000; i++) {
firstnum.add(i);
secondnum.add(i);
}
collections.shuffle(firstnum);
collections.shuffle(secondnum);
getstarttime();
collections.sort(firstnum);
getendtime("java sort run time ");
getstarttime();
secondnum = uniquesort(secondnum);
getendtime("uniquesort run time ");
}
public static list<integer> uniquesort(final list<integer> uniquelist) {
javauniquesort.templist.clear();
for (int i = 0; i < javauniquesort.temp.length; i++) {
javauniquesort.temp[i] = 0;
}
for (int i = 0; i < uniquelist.size(); i++) {
javauniquesort.temp[uniquelist.get(i)] = 1;
}
for (int i = 0; i < javauniquesort.temp.length; i++) {
if (javauniquesort.temp[i] == 1) {
javauniquesort.templist.add(i);
}
}
return javauniquesort.templist;
}
public static void getstarttime() {
javashuffle.start = system.nanotime();
}
public static void getendtime(final string s) {
javashuffle.end = system.nanotime();
system.out.println(s + ": " + (javashuffle.end - javashuffle.start) + "ns");
}
}
运行时间:
java sort run time : 1257737334ns
uniquesort run time : 170228290ns
java sort run time : 1202749828ns
uniquesort run time : 169327770ns
public static void main(final string[] args) {
random random = new random();
list<integer> firstnum = new arraylist<integer>();
list<integer> secondnum = new arraylist<integer>();
for (int i = 1; i <= 100000; i++) {
firstnum.add(i);
secondnum.add(i);
firstnum.add(random.nextint(i + 1));
secondnum.add(random.nextint(i + 1));
}
collections.shuffle(firstnum);
collections.shuffle(secondnum);
getstarttime();
collections.sort(firstnum);
getendtime("java sort run time ");
getstarttime();
secondnum = uniquesort(secondnum);
getendtime("uniquesort run time ");
}
public static list<integer> uniquesort(final list<integer> uniquelist) {
javaduplicatesort.templist.clear();
int[] temp = new int[200002];
for (int i = 0; i < temp.length; i++) {
temp[i] = 0;
}
for (int i = 0; i < uniquelist.size(); i++) {
temp[uniquelist.get(i)]++;
}
for (int i = 0; i < temp.length; i++) {
for (int j = temp[i]; j > 0; j--) {
javaduplicatesort.templist.add(i);
}
}
return javaduplicatesort.templist;
}
public static void getstarttime() {
javashuffle.start = system.nanotime();
}
public static void getendtime(final string s) {
javashuffle.end = system.nanotime();
system.out.println(s + ": " + (javashuffle.end - javashuffle.start) + "ns");
}
}
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
apollo与springboot集成实现动态刷新配置的教程详解
网友评论