CodeChef TurboSort（使用 int 与 Integer 排序）
CodeChef TurboSort (Sorting using int vs Integer )
Given the list of numbers, you are to sort them in non decreasing
order. Input
t – the number of numbers in list, then t lines follow [t <= 10^6].
Each line contains one integer: N [0 <= N <= 10^6] Output
Output given numbers in non decreasing order. Example
Input: 5 5 3 6 7 1 Output: 1 3 5 6 7
第一个实现使用文字 int 值并使用 Arrays.sort() 函数使用快速排序算法对文字进行排序（最坏情况 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 文字作为 Integer 对象进行存储和排序，并使用 Arrays.sort() 方法现在使用保证 nlogn 性能的 MergeSort 算法对 Integer 对象进行排序
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());
}
}
然而，现在的问题是，根据逻辑，合并排序算法（即整数对象排序实现）相对于快速排序算法花费的时间应该更少或相等），即 int 文字排序实现花费的时间更少。 ..
整数对象排序实现 - 0.94 秒
int 文字排序实现 - 0.53sec
我错过了什么吗？
这个多余时间的原因是什么？
是因为自动装箱和自动拆箱吗？！这是多余时间的原因吗...
对于初学者来说，归并排序和快速排序在实践中具有相似的性能。事实上，对于随机数据，快速排序通常略胜于它。但是，即使归并排序稍好一些，对整数进行排序也总是要慢得多，因为对对象进行排序比原始排序更难。它们不适用于您的缓存和原语。
排序需要更长的时间，主要是因为使用 Integer，你存储的是一个对象，这是一个很大的开销。
我想谢谢你提醒我，我有一个 codechef 帐户，我已经放弃了很长时间 back.Here 是我当时做的解决方案，我花了 .20 秒才 运行代码有点大希望你觉得这有用谢谢..
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.lang.reflect.Field;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
class Reader
{
private static final int BUFSIZE = 0x10000;
private final byte[] buffer = new byte[BUFSIZE];
private final ByteBuffer bb = ByteBuffer.wrap(buffer);
private final FileChannel channel;
int bufSize = -1; // non empty buffer
int bufOffset = 0; // non valid buffer
private FileInputStream getFileInputStream(InputStream in)
{
try
{
if (in instanceof BufferedInputStream)
{
Field field = in.getClass().getSuperclass().getDeclaredField("in");
field.setAccessible(true);
return (FileInputStream) field.get(in);
}
}
catch (Throwable e)
{
e.printStackTrace();
}
return (FileInputStream) in;
}
Reader(InputStream in) throws IOException
{
this.channel = this.getFileInputStream(in).getChannel();
}
void fetchBuffer() throws IOException
{
bb.clear();
bufSize = channel.read(bb);
bufOffset = 0;
}
boolean isFinished()
{
return bufSize <= 0;
}
private int peek() throws IOException
{
if (bufOffset < bufSize)
return buffer[bufOffset];
fetchBuffer();
if (bufSize > 0)
return buffer[0];
return -1;
}
private void skipSpace() throws IOException
{
int v = peek();
while (v <= ' ' && v != -1)
{
bufOffset++;
v = peek();
}
}
void nextLine() throws IOException
{
int v = peek();
while (v != -1 && v != '\n' && v != '\r')
{
bufOffset++;
v = peek();
}
if (v == '\r')
{
bufOffset++;
v = peek();
if (v == '\n')
bufOffset++;
}
else if (v == '\n')
{
bufOffset++;
v = peek();
if (v == '\r')
bufOffset++;
}
}
int readInt() throws IOException
{
skipSpace();
int result = 0;
int v = peek();
while (v > ' ')
{
result = result * 10 + v - '0';
bufOffset++;
v = peek();
}
return result;
}
}
class Writer
{
private static final int BUFSIZE = 0x10000;
private final FileOutputStream fos;
private final byte[] buffer = new byte[BUFSIZE];
private int offset = 0;
private FileOutputStream getFileOutputStream(PrintStream out)
{
try
{
Field field = out.getClass().getSuperclass().getDeclaredField("out");
field.setAccessible(true);
OutputStream os = (OutputStream) field.get(out);
if (os instanceof BufferedOutputStream)
{
BufferedOutputStream bos = (BufferedOutputStream) os;
field = bos.getClass().getSuperclass().getDeclaredField("out");
field.setAccessible(true);
return (FileOutputStream) field.get(bos);
}
return (FileOutputStream) field.get(out);
}
catch (Throwable e)
{
e.printStackTrace();
}
return null;
}
Writer(PrintStream out) throws IOException
{
fos = getFileOutputStream(out);
}
private static final int[] boundaries = new int[]
{
9, 99, 999, 9999, 99999, 999999, 9999999,
99999999, 999999999
};
private static final int[] divs = new int[]
{
1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000
};
private static final byte[] numbers = "0123456789".getBytes();
void writeln(int number) throws IOException
{
if (offset > BUFSIZE - 100)
flush();
int index;
for (index = 0; index < boundaries.length; index++)
if (number <= boundaries[index])
break;
for (; index >= 0; index--)
{
int mult = number / divs[index];
buffer[offset++] = numbers[mult];
number -= mult * divs[index];
}
buffer[offset++] = '\n';
}
void flush() throws IOException
{
if (offset > 0)
{
fos.write(buffer, 0, offset);
offset = 0;
}
}
}
class Solution {
public static void main(String[] args) throws java.lang.Exception {
Reader r=new Reader(System.in);
Writer w=new Writer(System.out);
int x,k;
int[] arr2 = new int[1000000];
x = r.readInt();
for (int i = 0; i < x; i++) {
arr2[r.readInt()]++;
}
for (int i = 0; i < 1000000; i++) {
k= arr2[i];
while(k-- > 0){
w.writeln(i);
}
}
w.flush();
}
}
Given the list of numbers, you are to sort them in non decreasing order. Input
t – the number of numbers in list, then t lines follow [t <= 10^6]. Each line contains one integer: N [0 <= N <= 10^6] Output
Output given numbers in non decreasing order. Example
Input: 5 5 3 6 7 1 Output: 1 3 5 6 7
第一个实现使用文字 int 值并使用 Arrays.sort() 函数使用快速排序算法对文字进行排序（最坏情况 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 文字作为 Integer 对象进行存储和排序，并使用 Arrays.sort() 方法现在使用保证 nlogn 性能的 MergeSort 算法对 Integer 对象进行排序
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());
}
}
然而，现在的问题是，根据逻辑，合并排序算法（即整数对象排序实现）相对于快速排序算法花费的时间应该更少或相等），即 int 文字排序实现花费的时间更少。 ..
整数对象排序实现 - 0.94 秒 int 文字排序实现 - 0.53sec
我错过了什么吗？ 这个多余时间的原因是什么？ 是因为自动装箱和自动拆箱吗？！这是多余时间的原因吗...
对于初学者来说，归并排序和快速排序在实践中具有相似的性能。事实上，对于随机数据，快速排序通常略胜于它。但是，即使归并排序稍好一些，对整数进行排序也总是要慢得多，因为对对象进行排序比原始排序更难。它们不适用于您的缓存和原语。
排序需要更长的时间，主要是因为使用 Integer，你存储的是一个对象，这是一个很大的开销。
我想谢谢你提醒我，我有一个 codechef 帐户，我已经放弃了很长时间 back.Here 是我当时做的解决方案，我花了 .20 秒才 运行代码有点大希望你觉得这有用谢谢..
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.lang.reflect.Field;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
class Reader
{
private static final int BUFSIZE = 0x10000;
private final byte[] buffer = new byte[BUFSIZE];
private final ByteBuffer bb = ByteBuffer.wrap(buffer);
private final FileChannel channel;
int bufSize = -1; // non empty buffer
int bufOffset = 0; // non valid buffer
private FileInputStream getFileInputStream(InputStream in)
{
try
{
if (in instanceof BufferedInputStream)
{
Field field = in.getClass().getSuperclass().getDeclaredField("in");
field.setAccessible(true);
return (FileInputStream) field.get(in);
}
}
catch (Throwable e)
{
e.printStackTrace();
}
return (FileInputStream) in;
}
Reader(InputStream in) throws IOException
{
this.channel = this.getFileInputStream(in).getChannel();
}
void fetchBuffer() throws IOException
{
bb.clear();
bufSize = channel.read(bb);
bufOffset = 0;
}
boolean isFinished()
{
return bufSize <= 0;
}
private int peek() throws IOException
{
if (bufOffset < bufSize)
return buffer[bufOffset];
fetchBuffer();
if (bufSize > 0)
return buffer[0];
return -1;
}
private void skipSpace() throws IOException
{
int v = peek();
while (v <= ' ' && v != -1)
{
bufOffset++;
v = peek();
}
}
void nextLine() throws IOException
{
int v = peek();
while (v != -1 && v != '\n' && v != '\r')
{
bufOffset++;
v = peek();
}
if (v == '\r')
{
bufOffset++;
v = peek();
if (v == '\n')
bufOffset++;
}
else if (v == '\n')
{
bufOffset++;
v = peek();
if (v == '\r')
bufOffset++;
}
}
int readInt() throws IOException
{
skipSpace();
int result = 0;
int v = peek();
while (v > ' ')
{
result = result * 10 + v - '0';
bufOffset++;
v = peek();
}
return result;
}
}
class Writer
{
private static final int BUFSIZE = 0x10000;
private final FileOutputStream fos;
private final byte[] buffer = new byte[BUFSIZE];
private int offset = 0;
private FileOutputStream getFileOutputStream(PrintStream out)
{
try
{
Field field = out.getClass().getSuperclass().getDeclaredField("out");
field.setAccessible(true);
OutputStream os = (OutputStream) field.get(out);
if (os instanceof BufferedOutputStream)
{
BufferedOutputStream bos = (BufferedOutputStream) os;
field = bos.getClass().getSuperclass().getDeclaredField("out");
field.setAccessible(true);
return (FileOutputStream) field.get(bos);
}
return (FileOutputStream) field.get(out);
}
catch (Throwable e)
{
e.printStackTrace();
}
return null;
}
Writer(PrintStream out) throws IOException
{
fos = getFileOutputStream(out);
}
private static final int[] boundaries = new int[]
{
9, 99, 999, 9999, 99999, 999999, 9999999,
99999999, 999999999
};
private static final int[] divs = new int[]
{
1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000
};
private static final byte[] numbers = "0123456789".getBytes();
void writeln(int number) throws IOException
{
if (offset > BUFSIZE - 100)
flush();
int index;
for (index = 0; index < boundaries.length; index++)
if (number <= boundaries[index])
break;
for (; index >= 0; index--)
{
int mult = number / divs[index];
buffer[offset++] = numbers[mult];
number -= mult * divs[index];
}
buffer[offset++] = '\n';
}
void flush() throws IOException
{
if (offset > 0)
{
fos.write(buffer, 0, offset);
offset = 0;
}
}
}
class Solution {
public static void main(String[] args) throws java.lang.Exception {
Reader r=new Reader(System.in);
Writer w=new Writer(System.out);
int x,k;
int[] arr2 = new int[1000000];
x = r.readInt();
for (int i = 0; i < x; i++) {
arr2[r.readInt()]++;
}
for (int i = 0; i < 1000000; i++) {
k= arr2[i];
while(k-- > 0){
w.writeln(i);
}
}
w.flush();
}
}