. Приведенный список номеров, вы должны сортировать их в неубывающем порядке. ВходCodeChef TurboSort (Сортировка с использованием int vs Integer)
t - количество номеров в списке, затем t строк следуют за [t < = 10^6]. Каждая строка содержит одно целое: N [0 < = N < = 10^6] Выход
Вывод данных в неупорядоченном порядке. Пример
Входной сигнал: 5 5 3 6 7 1 Выход: 1 3 5 6 7
первая реализация с помощью литералов Int значения и с помощью функции Arrays.sort(), которая сортирует литералов, используя Quicksort Algo (худший случай п^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 литералов в качестве объектов Integer и используя() метамфетамин Arrays.sort спосо что теперь сортирует объекты Integer с использованием сортировкой слияния 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());
}
}
Однако этот вопрос в настоящее время является то, что согласно логике, слиянию алго (т.е. реализации сортировки объектов Integer) следует принимать меньше или равное время относительно Quicksort алгоритм), т.е. Int буквальной сортировочной реализации занимает меньше времени ...
Integer объект реализация сортировки - 0.94sec ИНТА буквальной сортировки реализация - 0.53sec
Я что-то пропустил? В чем причина этого лишнего времени? Это из-за autoboxing и autounboxing?! Является то, что причина этого лишнего времени ...
btw, как вы знаете, что ваши элементы являются ints и <10^6, вы можете отсортировать их по линейной сложности. –
Возможно, потому, что вы не измеряете то, что, по-вашему, вы измеряете. Вероятно, вы измеряете время компиляции HotSpot, время запуска JVM, пропускную способность вашего диска и т. Д. Сначала прочтите этот пост, а затем опубликуйте новые результаты тестов: http://stackoverflow.com/questions/504103/how-do-i-write -a-correct-micro-benchmark-in-java –