java CodeChef TurboSort（使用int与Integer进行排序）

Question

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值和数组的实现。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文本存储和排序为整数对象，并使用数组。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-literal排序实现花费更少的时间

整数对象排序实现-0.94秒 整数文本排序实现-0.53秒

我错过了什么吗？ 这段时间过长的原因是什么？ 是因为自动装箱和自动拆箱吗？！这就是为什么会有这么多时间

Answer 1

我想谢谢你提醒我，我有一个codechef帐户，我早就甩了。这是我当时做的解决方案，它花了我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();
    }
} 

Answer 2

排序需要更长的时间，主要是因为使用Integer时，您要存储一个对象，这会带来很大的开销

Answer 3

首先，合并排序和快速排序在实践中都有类似的性能。事实上，对于随机数据，快速排序的性能通常略优于它。但是，即使合并排序稍微好一点，对整数的排序也总是要慢得多，因为排序对象比原语更难。它们不能与缓存以及原语一起工作