CodeChef TurboSort（使用int与整数排序）
给定数字列表，您将按不递减的顺序对它们进行排序。输入
t – 列表中的数字数，则 t 行跟在 [t] 之后
以非递减顺序输出给定的数字。例子
输入:5 5 3 6 7 1输出: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文字存储和排序为整数对象，并使用Arrays.sort（）方法，该方法现在使用MergeSort算法对整数对象进行排序，以保证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());
}
}
然而，现在的问题是，根据逻辑，mergesort算法（即整数对象排序实现）相对于Quicksort算法应该花费更少或相等的时间，即int文字排序实现花费的时间更少......
整数对象排序实现-0.94秒整数文字排序实现-0.53秒
我是不是错过了什么？这个超时的原因是什么？是因为自动装箱和自动装箱吗？！是这个超时的原因吗...
共有3个答案
我想谢谢你提醒我，我有代码厨师帐户，我很久以前就倾倒了。这是我当时做的解决方案，我花了.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();
}
}
排序需要更长的时间，主要是因为使用Integer，你存储的是一个对象，这是一个很大的开销。
首先，合并排序和快速排序在实践中具有相似的性能。事实上，对于随机数据，快速排序通常略胜一筹。但是，即使合并排序稍微好一点，对整数的排序总是会慢很多，因为对对象的排序比原语更难。它们不能像原语一样与您的缓存一起工作。
-
问题内容： 为什么我的打印输出数组未在以下代码中排序？ 问题答案： 您需要两个循环来实现Bubble Sort。 样例代码：
-
我的目标是优化我的应用程序代码。我的代码如下所示： 当我在Netbeans中使用Findbugs进行静态分析时，它显示了一个类似于“方法调用无效的新整数（int）构造函数；使用Integer.valueOf（int）”的警告/错误。 我知道新整数（int）和整数之间的区别。valueOf（int）。 一个创建一个附加对象，另一个不创建。一个不缓存，另一个缓存。 所以我这样修改了我的代码... 但同
-
对于这个项目，我得到了一个字符串数组和一个整数数组。int[1]是字符串[1]的排名。我需要使用mergesort按1到n的顺序对int数组进行排序，我在下面已经完成了这项工作。但是当int数组被移动时，我还需要切换字符串数组的位置，以便它们都被排序，如果这有意义的话？我不知道我的编码有什么问题，甚至我的想法是否真的有效，但我一直在stringSorted[k]=stringRight[j]上得到
-
问题内容： 使用，为什么它对（原始类型）和数组显示不同的列表大小？ a）对于数组，每当我执行以下程序时，列表大小= 1 b）但是，如果我从数组类型更改为array（如），则列表大小为4，我认为这是正确的。 PS ：使用（包装类）数组，则结果很好，但是我不确定为什么在原始数组中列表大小为1。请解释。 问题答案： 由于Java泛型而无法保存原始值（请参阅类似的问题）。因此，当您调用Arrays 时，将
-
主要内容：关于 Python 2.x,整数的不同进制,数字分隔符整数就是没有小数部分的数字， Python 中的整数包括正整数、0 和负整数。 有些强类型的编程语言会提供多种整数类型，每种类型的长度都不同，能容纳的整数的大小也不同，开发者要根据实际数字的大小选用不同的类型。例如C语言提供了 short、int、long、long long 四种类型的整数，它们的长度依次递增，初学者在选择整数类型时往往比较迷惑，有时候还会导致数值溢出。 而 Python 则不同
-
2.2.1 整数类型 int 整数就是没有小数部分的数值，分为正整数、0 和负整数。Python 语言提供了类型 int 用于表示现实世界中的整数信息，如班级里的人数、人的年龄、乒乓球比赛每方的得分等等。 基本数据类型的值都可通过字面值（literal）的形式表示出来，即以字面形式表现值。 整数类型的字面值表示形式和我们在现实世界中的写法一样，例如下列都是合法的整数： 123 -456 0 注意