关于使用Java中Arrays.sort()方法TLE

最近一直在练用Java写题（链接），今天无意发现一道很简单的二分题，我一开始是直接开int[]数组调用Arrays.sort()去排序，没想到TLE了，原来是因为jdk中对于int[]的排序是使用快速排序的，jdk中相关调用源码如下

1     public static void sort(int[] a) {
2         DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
3     }

View Code

而测试数据恰好有反快排的数据，因此被卡。

解决方法也不少，比较简单的是使用包装类Integer去调用Arrays.sort，jdk对之的实现是基于timsort的，可以从如下的源码看到相关调用。

1     public static void sort(Object[] a) {
2         if (LegacyMergeSort.userRequested)
3             legacyMergeSort(a);
4         else
5             ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
6     }

View Code

或者也可以用List，然后调用Collections.sort()。

当然还可以先shuffle一下打乱数组，再调用排序，不过其实理论上来说还是有风险。

CF上有一篇博文可以参考：http://codeforces.com/blog/entry/7108

关于使用Java中Arrays.sort()方法TLE

原文：http://www.cnblogs.com/micrari/p/5573071.html