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 值并使用 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

我错过了什么吗？这个多余时间的原因是什么？是因为自动装箱和自动拆箱吗？!这是多余时间的原因......

Answer 1

对于初学者来说，归并排序和快速排序在实践中具有相似的性能。事实上，对于随机数据，快速排序通常略胜于它。但是，即使归并排序稍好一些，对整数进行排序也总是要慢得多，因为对对象进行排序比原始排序更难。它们不适用于您的缓存和原语。