给定数字列表,您将按照非递减的 顺序对它们进行排序。输入CodeChef TurboSort(使用int对整数进行排序)
t - 列表中的数字的数量,然后t行遵循[t < = 10^6]。 每行包含一个整数:N [0 < = N < = 10^6]输出
以非递减顺序输出给定的数字。实施例
输入:5 5 3 6 7 1输出:1 3 5 6 7
使用文字INT值,并使用该排序使用快速排序的文字的Arrays.sort()函数首先执行ALGO(最坏的情况下N^2,平均情况 - nlogn)
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
int num = in.nextInt();
int[] n = new int[num];
for (int i = 0; i < n.length; i++) {
n[i] = in.nextInt();
}
Arrays.sort(n);
for (int i = 0; i < n.length; i++) out.println(n[i]);
out.close();
}
}
class InputReader {
private BufferedReader reader;
private StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
下实现存储和排序中的int文字作为整型对象,并使用Arrays.sort()甲基OD,现在排序使用归并ALGO,保证nlogn性能
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
import java.io.InputStream;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
int T = in.nextInt();
Integer[] ARR = new Integer[T];
for (int i = 0; i < T; i++) ARR[i] = in.nextInt();
Arrays.sort(ARR);
for (int i : ARR) out.println(i);
out.close();
}
}
class InputReader {
private BufferedReader reader;
private StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
然而现在的问题是,按照逻辑,归并ALGO(即,整数对象排序实现)应该采取小于或等于时间的整数对象与IE浏览器中的int文字排序实现对于快速排序算法中)正在采取较小的时间...
Integer对象分类实施 - 0.94sec INT文字排序执行 - 0.53sec
我错过了什么吗? 这个多余的时间是什么原因? 是不是因为自动装箱和autounboxing的?!是这个剩余时间的原因...
顺便说一句,你知道你的元素是整数且<10^6,你可以用线性复杂度对其进行排序。 –
可能是因为你没有测量你认为你正在测量的东西。您可能正在测量HotSpot编译时间,JVM启动时间,磁盘吞吐量等。请先阅读本文,然后发布新的基准测试结果:http://stackoverflow.com/questions/504103/how-do-i-write -a-correct-micro-benchmark-in-java –